下面的代碼總是運行時掛起。

誰知道為什么？但是如果我將 not2 去掉或者將 VECTOR_SIZE 減至 16 ，就能正常工作了。代碼如下：

#pragma warning(disable:4786)

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

#define VECTOR_SIZE 17

using namespace std;

void main()
{
??? vector<int> vecStrings;
??? for (int i = 0; i < VECTOR_SIZE; i++)
???? ? vecStrings.push_back(4);

?? ? sort(vecStrings.begin(), vecStrings.end(), not2(greater<int>()));
}

有一位名為 "Marco Dalla Gasperina" 的朋友 這么評論道：

“這應該是你的程序的一個 Bug 。

原因是， sort() 希望是一個 Strict Weak Ordering 。但在你的代碼中， not2(greater()) 的意思就是“ not greater ”，相當于“ less than or equal to ”。這不是一個 Strict Weak Ordering 。當兩個元素相等時，這個表達式就會發生一些未知行為。

有兩個方案：

方案 1 ：改為 sort(vecStrings.begin(), vecStrings.end(), not2(greater_equal<int>())); 即可！

方案 2 ：直接寫 sort(vecStrings.begin(), vecStrings.end()) 即可，因為 less<int>() 是默認的 sort 行為。”

?

但是我總覺得不對。

我的思路是這樣的：

首先我可以證明 not2(greater()) 是沒有問題的。在 MSDN(2002 January) 中的 less_equal Function(ms-help://MS.MSDNQTR.2002JAN.1033/vcstdlib/html/vclrf_functional_Lessequal.htm) 中講道：

The binary predicate less_equal<Type> provides a strict weak ordering of a set of element values of type Type into equivalence classes if and only if this Type satisfies the standard mathematical requirements for being so ordered.

而且它下面給的例子就是這么直接用的：

              
                
                  sort( v1.begin( ), v1.end( ), less_equal<int>( ) );
                
              
            

我試過這個例子，完全可以運行。

這就說明 “ less than or equal to ”這種操作用于 sort function 完全沒有問題，這本來就是 Strict Weak Ordering 。

?

其次，我可以證明這種 hang 現象是和特定的 vector 元素有關系的。

仍然采用 less_equal 的例子做實驗，畢竟它比較可信。它原來插入 vector 的元素是：

              
                
                  for ( i = 0 ; i < 5 ; i++ )
                
              
            

              
                
                  
                    ?? 
                  
                  {
                
              
            

              
                
                  
                    ????? 
                  
                  v1.push_back( rand( ) );
                
              
            

              
                
                  
                    ?? 
                  
                  }
                
              
            

              
                
                  
                    ?? 
                  
                  for ( i = 0 ; i < 3 ; i++ )
                
              
            

              
                
                  
                    ?? 
                  
                  {
                
              
            

              
                
                  
                    ????? 
                  
                  v1.push_back( 2836 );
                
              
            

}

也就是說，元素為： ( 41 18467 6334 26500 19169 2836 2836 2836 )

修改 1 ：現在我們改為：

for ( i = 0 ; i < 17 ; i++ )

{

?? v1.push_back( 5 );

}

這樣執行到 sort() 時就掛起了。其實是進入到了一個死循環。

修改 2 ：改為 16 個元素呢：

for ( i = 0 ; i < 16 ; i++ )

{

?? v1.push_back( 5 );

}

就可以了。

可以說，肯定是 STL 的本身問題。

?

那么跟什么有關呢？經過試驗，我們發現好像跟 vector 的元素數目有關系， vector 的元素數不能大于 16 ！

比如：

int nSize = 8;

for ( i = 0 ; i < nSize ; i++ )

?? {

????? v1.push_back( rand( ) );

????? ? ? v1.push_back( 5 );

?? }

中 nSize 只能增長到 8 為止。

?

而

int nSize = 15;

for ( i = 0 ; i < 3 ; i++ )

?? {

????? v1.push_back( rand( ) );

?? }

?? for ( i = 0 ; i < nSize ; i++ )

???????????? v1.push_back( 5 );

中的 nSize 只能增長到 15 為止。

?

跟蹤的結果是：

STL 的頭文件 algorithm 的第 599 行為：

template<class _RI, class _Ty, class _Pr> inline
?void _Sort(_RI _F, _RI _L, _Pr _P, _Ty *)
?{
?? for (; _SORT_MAX < _L - _F; )
? {
????? _RI _M = _Unguarded_partition(_F, _L, _Median(_Ty(*_F),
?????????????? _Ty(*(_F + (_L - _F) / 2)), _Ty(*(_L - 1)), _P), _P);
????? if (_L - _M <= _M - _F)
??????? _Sort(_M, _L, _P, _Val_type(_F)), _L = _M;
????? else
??????? _Sort(_F, _M, _P, _Val_type(_F)), _F = _M;
?? }
? }

這就是 sort function 執行的細節部分。其中的 _SORT_MAX 定義為 16 ，這是在第 16 行定義的。

Sort function 如何執行，將會進行如下的判斷：

template<class _RI, class _Ty, class _Pr> inline

????? void _Sort_0(_RI _F, _RI _L, _Pr _P, _Ty *)

????? { if (_L - _F <= _SORT_MAX)

???????????? _Insertion_sort(_F, _L, _P);

????? else

???????????? {_Sort(_F, _L, _P, (_Ty *)0);

???????????? _Insertion_sort(_F, _F + _SORT_MAX, _P);

???????????? for (_F += _SORT_MAX; _F != _L; ++_F)

??????????????????? _Unguarded_insert(_F, _Ty(*_F), _P); }}

對于重復的元素沒有達到一定程度時， _L-_F 就會小于或等于 16 ，這樣就會調用 _Insertion_sort 。而這個 _Insertion_sort 里面只是用到了 If—Else 語句。

當重復的元素的數目達到一定程度后，使得 _L-_F 大于 16 ，就會調用 _Sort(_F, _L, _P, (_Ty *)0) 。這里面可是一個 for 循環！而且 for 循環退出的條件為：

for (; _SORT_MAX < _L - _F; )

對于實際情況，就會為：

16 ??????? < ? 5 ? - ? 5

多么可怕的事情！這個條件永遠也滿足不了的！這樣就陷入了死循環！所以這應不應該算作 STL 的 Bug!?