有一位名为"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>()));</int>即可!
方案2:直接写sort(vecStrings.begin(), vecStrings.end())即可,因为less<int>()</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</type> 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>( ) );</int>
我试过这个例子,完全可以运行。
这就说明“less than or equal to”这种操作用于sort function完全没有问题,这本来就是Strict Weak Ordering。
其次,我可以证明这种hang现象是和特定的vector元素有关系的。
仍然采用less_equal的例子做实验,毕竟它比较可信。它原来插入vector的元素是:
for ( i = 0 ; i
{
v1.push_back( rand( ) );
}
for ( i = 0 ; i
{
v1.push_back( 2836 );
}
也就是说,元素为:( 41 18467 6334 26500 19169 2836 2836 2836 )
修改1:现在我们改为:
for ( i = 0 ; i
{
v1.push_back( 5 );
}
这样执行到sort()时就挂起了。其实是进入到了一个死循环。
修改2:改为16个元素呢:
for ( i = 0 ; i
{
v1.push_back( 5 );
}
就可以了。
可以说,肯定是STL的本身问题。
那么跟什么有关呢?经过试验,我们发现好像跟vector的元素数目有关系,vector的元素数不能大于16!
比如:
int nSize = 8;
for ( i = 0 ; i
{
v1.push_back( rand( ) );
v1.push_back( 5 );
}
中nSize只能增长到8为止。
而
int nSize = 15;
for ( i = 0 ; i
{
v1.push_back( rand( ) );
}
for ( i = 0 ; i
v1.push_back( 5 );
中的nSize只能增长到15为止。
跟踪的结果是:
STL的头文件algorithm的第599行为:
template<class _ri class _ty _pr> inline<br>void _Sort(_RI _F, _RI _L, _Pr _P, _Ty *)<br>{<br><b><span style="COLOR: red">for (; _SORT_MAX </span></b><br> {<br> _RI _M = _Unguarded_partition(_F, _L, _Median(_Ty(*_F),<br> _Ty(*(_F + (_L - _F) / 2)), _Ty(*(_L - 1)), _P), _P);<br> if (_L - _M _Sort(_M, _L, _P, _Val_type(_F)), _L = _M;<br> else<br> _Sort(_F, _M, _P, _Val_type(_F)), _F = _M;<br> }<br> }</class>
这就是sort function执行的细节部分。其中的_SORT_MAX定义为16,这是在第16行定义的。
Sort function如何执行,将会进行如下的判断:
template<class _ri class _ty _pr> inline<p></p></class>
void _Sort_0(_RI _F, _RI _L, _Pr _P, _Ty *)
{if (_L - _F
_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
对于实际情况,就会为:
16 5 - 5
多么可怕的事情!这个条件永远也满足不了的!这样就陷入了死循环!所以这应不应该算作STL的Bug!?
|
相关推荐
白宫.stl白宫.stl白宫
零件1.STL(21030402).STL.stl
长颈鹿.stl长颈鹿.
nb.STL.stl
底板.STL.stl
ZFT.STL.stl
ahouse.STL.stl
电池.STL.stl
EiffelTower.STL.stl
.stl有两种格式:二进制和ASCII,请注意区分。本资源为c# 解析二进制.stl模型,分享一个demo,希望各位网友下载能用得上。
神光棒.STL.stl
子擎支架.STL.stl
Tou200.STL.stl
五角星.STL.stl
发动机第二代.STL.stl
螺旋环1.stl螺旋环1.stl
密歇根地形(模拟岛屿).STL.stl
装配体1 - 防滑垫-4.STL.stl
零件1 21020243班2102040826高姚升.STL.stl
悉尼歌剧院.stl悉尼歌剧院