下面的代码总是运行时挂起。

谁知道为什么？但是如果我将 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!?