search詳解

search算法:
                   //TEMPLATE FUNCTION search
template<class_FwdIt1,
         class_FwdIt2,
         class_Diff1,
         class_Diff2> inline
         _FwdIt1 _Search(_FwdIt1 _First1,_FwdIt1 _Last1,
                   _FwdIt2 _First2, _FwdIt2_Last2, _Diff1 *, _Diff2 *)
         {       // find first [_First2, _Last2) match
         _Diff1 _Count1 = 0;
         _Distance(_First1, _Last1, _Count1);//獲取父序列大小
         _Diff2 _Count2 = 0;
         _Distance(_First2, _Last2, _Count2);//獲取子序列大小
 
         for (;_Count2 <= _Count1; ++_First1, --_Count1)
                   {       // room for match, try it
//保存一個中間變量,使得父序列可以和子序列依次對比而不影響外層循環的父迭代器
                  _FwdIt1 _Mid1= _First1;
                   for(_FwdIt2 _Mid2 = _First2; ; ++_Mid1, ++_Mid2)
                            if (_Mid2 == _Last2)//如果子序列已經比較完成,則表明查找完成.
                                     return (_First1);
                            else if (!(*_Mid1 ==*_Mid2))//如果不等進行下次外循環
                                     break;
                            //else (*_Mid1 ==*Mid2 ) 繼續內循環
                   }
         return(_Last1);
         }
 
template<class_FwdIt1,
         class_FwdIt2> inline
         _FwdIt1 search(_FwdIt1 _First1, _FwdIt1_Last1,
                   _FwdIt2 _First2, _FwdIt2_Last2)
         {       // find first [_First2, _Last2) match
         _DEBUG_RANGE(_First1, _Last1);
         _DEBUG_RANGE(_First2, _Last2);
         return(_Rechecked(_First1,
                   _Search(_Unchecked(_First1),_Unchecked(_Last1),
                            _Unchecked(_First2),_Unchecked(_Last2),
                            _Dist_type(_First1),_Dist_type(_First2))));
         }
其中:_Dist_type返回兩指針的距離的類型
重載search:
                   //TEMPLATE FUNCTION search WITH PRED
template<class_FwdIt1,
         class_FwdIt2,
         class_Diff1,
         class_Diff2,
         class_Pr> inline
         _FwdIt1 _Search(_FwdIt1 _First1,_FwdIt1 _Last1,
                   _FwdIt2 _First2, _FwdIt2_Last2, _Pr _Pred, _Diff1 *, _Diff2 *)
         {       // find first [_First2, _Last2) satisfying _Pred
         _Diff1 _Count1 = 0;
         _Distance(_First1, _Last1, _Count1);
         _Diff2 _Count2 = 0;
         _Distance(_First2, _Last2, _Count2);
 
         for (;_Count2 <= _Count1; ++_First1, --_Count1)
                   {       // room for match, try it
                   _FwdIt1 _Mid1 = _First1;
                   for(_FwdIt2 _Mid2 = _First2; ; ++_Mid1, ++_Mid2)
                            if (_Mid2 == _Last2)
                                     return (_First1);
                            else if(!_Pred(*_Mid1, *_Mid2))
                                     break;
                   }
         return(_Last1);
         }
 
template<class_FwdIt1,
         class_FwdIt2,
         class_Pr> inline
         _FwdIt1 search(_FwdIt1 _First1, _FwdIt1_Last1,
                   _FwdIt2 _First2, _FwdIt2_Last2, _Pr _Pred)
         {       // find first [_First2, _Last2) satisfying _Pred
         _DEBUG_RANGE(_First1, _Last1);
         _DEBUG_RANGE(_First2, _Last2);
         _DEBUG_POINTER(_Pred);
         return(_Rechecked(_First1,
                   _Search(_Unchecked(_First1),_Unchecked(_Last1),
                            _Unchecked(_First2),_Unchecked(_Last2), _Pred,
                            _Dist_type(_First1),_Dist_type(_First2))));
         }
有了第一個函數作為基礎,第二個函數就容易理解多了.
需要注意的是,函數返回父迭代器.
舉例:
template<typenameT>
bool equal_three( T _value1,T _value2 )
{
         return_value1 == ++ _value2;
}
int main()
{
         vector<int>vecInt;
         vecInt.push_back( 2 );
         vecInt.push_back( 5 );
         vecInt.push_back( 7 );
         vecInt.push_back( 3 );
         vecInt.push_back( 5 );
         vecInt.push_back( 4 );
         vecInt.push_back( 5 );
         vecInt.push_back( -17 );
         vecInt.push_back( 3 );
 
         list<int>lstInt;
         lstInt.push_back( 2 );
         lstInt.push_back( 4 );
         lstInt.push_back( 3 );
         vector<int>::iteratoriterFind = search(vecInt.begin(),vecInt.end(),lstInt.begin(),lstInt.end(),equal_three<int> );
         if (iterFind != vecInt.end() )
         {
                   copy( iterFind,iterFind +lstInt.size(),ostream_iterator<int>(cout," " ) );
         }
         cout<<"\n";
         iterFind = search( vecInt.begin(),vecInt.end(),lstInt.begin(),lstInt.end());
         if (iterFind != vecInt.end() )
         {
                   copy( iterFind,iterFind +lstInt.size(),ostream_iterator<int>(cout," " ) );
         }
         system( "pause");
         return0;
}
3 5 4
         請按任意鍵繼續...



摘自 yuanweihuayan的專欄