搜狐回应员工遭遇工资补助诈骗： 搜狐回应员工遭遇工资补助诈骗：
俄媒：滴滴公司改变决定，放弃退 俄媒：滴滴公司改变决定，放弃退
Facebook披上了新马甲 Meta能抓住年 Facebook披上了新马甲 Meta能抓住年

软件测试 > 测试开发技术 > 软件测试开发语言 > .net >

VC.STL Newsgroup Good Questions(一)

发表于：2007-07-01来源：作者：点击数： 标签：
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++, 3

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!?




 
 


           
原文转自：http://www.ltesting.net

           

  




           
          

            
    
              
            

          

         
          
 

           

          


          
        

      
    
   
   

      

        

          
 相关文章

        

        

          
        

        

       
	   
	   
	   
  

   
          
               

         
   
  






        
      

      

        

          
 软件测试沙龙 More>> 

        

        
 
        
        
        
        

      

      

        

          
 新浪微博More>>

        

        

          
        

      

      ...
      

          
 热门标签 

        

        

          
          

            
             
    
              
    • 
              
    • 
              
    • 
              
    •