這是今天寫程序中遇到的兩個詭異的問題。我的 IDE 是 VC++2005 ExpressiEdition 。
第一個問題是關于 map 的。話不多說，以下 20 多行的 C++ 代碼重現(xiàn)了我遇到的問題：
#include <iostream>
#include <map>
using namespace std;
struct S {
int x, y;
S(int xx, int yy): x(xx), y(yy) {}
bool operator <(const S& s) const {
return x < s.x && y < s.y;
}
};
map<S, int > ms;
int main() {
ms.insert(map<S, int >::value_type(S(31, 41), 59));
S test(31, 59);
if (ms.find(test) != ms.end()) {
cout << "Find the value: " << ms[test] << endl;
} else {
cout << "Find Failure\n" ;
}
return 0;
}
使用 VC++6.0 ， VC++2005 Express Edition, VC++2005 command line compiler( 不帶任何編譯選項 ) ， g++ 測試的結(jié)果都相同，最后輸出：
Find the value: 59
這個問題比較隱蔽。多個編譯器測試結(jié)果相同說明肯定不是編譯器版本相關的問題。直接調(diào)試進入 find 函數(shù)就可以明白：
iterator find(const key_type& _Keyval)
{ // find an element in mutable sequence that matches _Keyval
iterator _Where = lower_bound(_Keyval);
return (_Where == end()
|| _DEBUG_LT_PRED(this ->comp,
_Keyval, _Key(_Where._Mynode()))
? end() : _Where);
}
雖然這樣調(diào)試會遇到一些 STL 內(nèi)部的細節(jié)，但整體實現(xiàn)思路還是可看出來。在 find 函數(shù)中， lower_bound 返回值是結(jié)點 (31, 41) 。跟蹤進入，發(fā)現(xiàn)調(diào)用的 _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 _Ty2& _Right,
const wchar_t *_Where, unsigned int _Line)
{ // test if _Pred(_Left, _Right) and _Pred is strict weak ordering
if (!_Pred(_Left, _Right))
return (false );
else if (_Pred(_Right, _Left))
_DEBUG_ERROR2("invalid operator<" , _Where, _Line);
return (true );
}
( 注：關于 _Debug_lt_pred 函數(shù)有三個重載版本，分別是針對參數(shù) _Left, _Right 的 const 性質(zhì)的，看這些代碼能學到很多東西。另外，如果靜態(tài)地看這些代碼來分析自己程序中的錯誤，則因為有大量的重載函數(shù)，所以靜態(tài)分析時很難自己確定到底哪一個函數(shù)被調(diào)用，而動態(tài)調(diào)試就能一步到位。 )
從這個函數(shù)的代碼里大致就能看出問題所在了。猜測這里的 _Pred 參數(shù)就是自己在 struct 里定義的那個 operator < ，編譯器中看到 _Pred 的 value 是 {lessthan } ， type 是 std::less <S> ，但這里有更大的發(fā)現(xiàn)： strict weak ordering!!! 自己 C++ 功底很淺，這是一個新的發(fā)現(xiàn)，馬上 google 一下 ”strict weak ordering” 這個關鍵詞，果然發(fā)現(xiàn)大量的專題鏈接！暫且先放下這個主題。問題猜測肯定是出在 operator < 這個函數(shù)上了，因為根據(jù)自己的 operator < 定義： {31, 41} < {31, 59} 返回值是 false ， {31, 59} < {31, 41} 的返回值也是 false ，那么，由這兩個比較能得出結(jié)論： {31, 41} == {31, 59} !!! 這也無怪乎程序運行會返回不期望的結(jié)果了。
但這也只是猜測，繼續(xù)調(diào)試，看能不能找到 _Pred 函數(shù)的真實面目。上面說了從編譯器中看出 _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.
我們接著調(diào)試，跟蹤進入 _Pred 函數(shù)，發(fā)現(xiàn)它的定義如下：
template <class _Ty>
struct less
: 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);
}
};
它最終比較 _Left 和 _Right 時調(diào)用的正是 struct S 中定義的 operator < 。
至此，問題真相大白。還遺留兩個主題：一個是關于 strict weak ordering ，另一個是 STL 中的一些實現(xiàn)方法，因為以上只是跟蹤調(diào)試過程把沿途看到的東西機械地記錄了下來，并不是真正的理解。
無獨有偶，今天遇到另一個問題，關于 STL 中的 sort 函數(shù)的問題，這個問題是唯獨在 VC++ 2005 Express Edition 中才出現(xiàn)的，并且在命令行下使用 cl.exe 不帶任何選項編譯連接時正常，使用 g++ 也正常。問題的表現(xiàn)就是程序在運行時出現(xiàn)異常，信息是： ”invalid operator <” 。這個問題就不再重現(xiàn)調(diào)試了，它的解決方法見下列地址：
http://support.microsoft.com/kb/949171 strict weak ordering 是一個數(shù)學上的術語，剛剛給出的這個地址上面有關于 strict weak ordering 的簡明的解釋，貼過來：
The STL algorithms for stable_sort ( ) and sort() require the binary predicate to be strict weak ordering.
For example:
· Strict: pred (X, X) is always false.
· Weak: If ! pred (X, Y) && !pred (Y, X), X==Y.
· Ordering: If pred (X, Y) && pred (Y, Z), then pred (X, Z).