小于号重载须注意的问题——strict weak ordering

这是今天写程序中遇到的两个诡异的问题。我的

IDE

是

VC++2005 ExpressiEdition

。

第一个问题是关于

map

的。话不多说，以下

20

多行的

C++

代码重现了我遇到的问题：

#include
 
<iostream>


#include
 
<map>


using
 
namespace
 

 
 

struct
 
S {
 

int
 

int xx, int
 

bool operator <(const S& s) const
 

return
 

     }
 

};
 

 
 

map<S, int
 

 
 

int
 
main() {
 

int


 
 

     S test(31, 59);
 

if
 

"Find the value: "
 

else
 

"Find Failure/n"
 

     }
 

return
 

}      

使用

VC++6.0

，

VC++2005 Express Edition, VC++2005 command line compiler(

不带任何编译选项

)

，

g++

测试的结果都相同，最后输出：

Find the value: 59 

这个问题比较隐蔽。多个编译器测试结果相同说明肯定不是编译器版本相关的问题。直接调试进入

find

函数就可以明白：

const
 

// find an element in mutable sequence that matches _Keyval

         iterator _Where = lower_bound(_Keyval);
 

return
 

this
 

                   _Keyval, _Key(_Where._Mynode()))
 

                       ? end() : _Where);
 

         }      

虽然这样调试会遇到一些

STL

内部的细节，但整体实现思路还是可看出来。在

find

函数中，

lower_bound

返回值是结点

(31, 41)

。跟踪进入，发现调用的

_DEBUG_LT_PRED

的定义如下：

#define
 
_DEBUG_LT_PRED(pred, x, y)   _Debug_lt_pred(pred, x, y, __FILEW__, __LINE__)
 

 
 

template
 
<class _Pr, class _Ty1, class _Ty2> inline

bool __CLRCALL_OR_CDECL _Debug_lt_pred(_Pr _Pred, const _Ty1& _Left, const
 

const wchar_t *_Where, unsigned int
 

// test if _Pred(_Left, _Right) and _Pred is strict weak ordering

if
 

return (false
 

else if
 

"invalid operator<"
 

return (true
 

     }
 

(      

注：关于

_Debug_lt_pred

函数有三个重载版本，分别是针对参数

_Left, _Right

的

const

性质的，看这些代码能学到很多东西。另外，如果静态地看这些代码来分析自己程序中的错误，则因为有大量的重载函数，所以静态分析时很难自己确定到底哪一个函数被调用，而动态调试就能一步到位。

)

从这个函数的代码里大致就能看出问题所在了。猜测这里的

_Pred

参数就是自己在

struct

里定义的那个

operator <

，编译器中看到

_Pred

的

value

是

{lessthan

，

type

是

std::less

<S>

，但这里有更大的发现：

strict weak ordering!!!

自己

C++

功底很浅，这是一个新的发现，马上

google

一下

”strict weak ordering”

这个关键词，果然发现大量的专题链接！暂且先放下这个主题。问题猜测肯定是出在

operator <

这个函数上了，因为根据自己的

operator <

定义：

{31, 41} < {31, 59} 

返回值是

false

，

{31, 59} < {31, 41} 

的返回值也是

false

，那么，由这两个比较能得出结论：

{31, 41} == {31, 59} !!!

这也无怪乎程序运行会返回不期望的结果了。

但这也只是猜测，继续调试，看能不能找到

_Pred

函数的真实面目。上面说了从编译器中看出

_Pred

的

type

是

std::less

<S>

，在

MSDN

中找到

less

是

STL

中的一个模板类，以下是在

MSDN

中看到的定义：

less

less

template<class T>

    struct less
 : public binary_function
<T, T, bool> {

    bool operator()
(const T& x, const T& y) const;

    };      

The template class defines its member function as returning ​

​x < y​

​​ . The member function defines a ​​total ordering​​​ , even if ​

​T​

​ is an object pointer type.

我们接着调试，跟踪进入

_Pred

函数，发现它的定义如下：

template

<class

struct

public binary_function<_Ty, _Ty, bool

// functor for operator<

bool operator ()(const _Ty& _Left, const _Ty& _Right) const

// apply operator< to operands

return

         }

     };

它最终比较

_Left

和

_Right

时调用的正是

struct

S

中定义的

operator <

。

至此，问题真相大白。还遗留两个主题：一个是关于

strict weak ordering

，另一个是

STL

中的一些实现方法，因为以上只是跟踪调试过程把沿途看到的东西机械地记录了下来，并不是真正的理解。

无独有偶，今天遇到另一个问题，关于

STL

中的

sort

函数的问题，这个问题是唯独在

VC++ 2005 Express Edition

中才出现的，并且在命令行下使用

cl.exe

不带任何选项编译连接时正常，使用

g++

也正常。问题的表现就是程序在运行时出现异常，信息是：

”invalid operator <”

。这个问题就不再重现调试了，它的解决方法见下列地址：

​​http://support.microsoft.com/kb/949171​​ 

strict weak ordering