VC.STL Newsgroup Good Questions(一)
使用Sort Function时程序挂起，Why?
Article last modified on 2002-5-29
----------------------------------------------------------------
The information in this article applies to:
- Microsoft Visual C++, 32-bit Editions, version 6.0, SP5
----------------------------------------------------------------
Question:
下面的代码总是运行时挂起。
谁知道为什么？但是如果我将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>()));
}
Answer:
有一位名为"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!?
(To be Continued)
Written by zhengyun@tomosoft.com
