饭中淹的避难所~~~~~

偶尔来避难的地方~

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  94 随笔 :: 0 文章 :: 257 评论 :: 0 Trackbacks

在实现里面,使用了两个可变类型,为了应对在一堆结构数组中按照一个成员来搜索。

template <class T1, class T2>
struct def_binary_search_compare
{
    inline 
int operator()( const T1 & v1, const T2 & v2 ){
        
if( v1 == v2 )return 0;
        
if( v1 > v2 )return 1;
        
return -1;
    }

}
;

template 
<class T1, class T2, typename cmpT = def_binary_search_compare<T1, T2> >
struct xbinary_search
{
    
static inline int search_insertpoint( const T1 * pTArray, int nArraySize, const T2 & v )
    
{
        
int insertpoint;
        _search( pTArray, nArraySize, v, insertpoint );
        
return insertpoint;
    }


    
static inline int search_value( const T1 * pTArray, int nArraySize, const T2 & v )
    
{
        
int insertpoint;
        
return _search( pTArray, nArraySize, v, insertpoint );
    }

private:
    
static typename cmpT _cmp;
    
static inline int _search( const T1 * pTArray, int nArraySize, const T2 & v, int & insertpoint )
    
{
        
int s = 0, e = nArraySize, m, ret;

        
while( s < e )
        
{
            m 
= (s+e)/2;
            ret 
= _cmp( pTArray[m], v );
            
if( ret == 0 )
            
{
                insertpoint 
= m;
                
return m;
            }


            
if( ret > 0 )
                e 
= m;
            
else
            
{
                
if( s == m )
                    
break;
                s 
= m+1;
            }

        }

        insertpoint 
= e;
        
return -1;
    }

}
;

template 
<class T1, class T2, typename cmpT>
typename cmpT xbinary_search
<T1,T2,cmpT>::_cmp;

很简单的一个算法。相信都看得懂。

posted on 2008-04-17 01:19 饭中淹 阅读(799) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理