小于号重載須注意的問題——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