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,
补充:软件开发 , C++ ,