search 源码剖析

一：用法解析 函数原型：

equality (1)     template <class ForwardIterator1, class ForwardIterator2>    ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,                             ForwardIterator2 first2, ForwardIterator2 last2); predicate (2)    template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>    ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,                             ForwardIterator2 first2, ForwardIterator2 last2,                             BinaryPredicate pred);

功能：

是否在区间[ first1 , last1 ）找到一个连续区间，和区间[ first2, last2 )完全匹配（默认是完全相等，或者使pred为真），如果找到，返回前者区间的匹配到的第一个元素迭代器；找不到返回last1。注意C++11在源码新加了一句判断返回，如果first2==last2，返回first1，这待会直接看源码会更清晰。

例子：

#include <iostream> // std::cout #include <algorithm> // std::search #include <vector> // std::vector bool mypredicate (int i, int j) { return (i==j); } int main () { std::vector<int> haystack; // set some values: haystack: 10 20 30 40 50 60 70 80 90 for (int i=1; i<10; i++) haystack.push_back(i*10); // using default comparison: int needle1[] = {40,50,60,70}; std::vector<int>::iterator it; it = std::search (haystack.begin(), haystack.end(), needle1, needle1+4); if (it!=haystack.end()) std::cout << "needle1 found at position " << (it-haystack.begin()) << '\n'; else std::cout << "needle1 not found\n"; // using predicate comparison: int needle2[] = {20,30,50}; it = std::search (haystack.begin(), haystack.end(), needle2, needle2+3, mypredicate); if (it!=haystack.end()) std::cout << "needle2 found at position " << (it-haystack.begin()) << '\n'; else std::cout << "needle2 not found\n"; return 0; }运行如下：

needle1 found at position 3 needle2 not found

二：源码剖析 // 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 *, forward_iterator_tag, forward_iterator_tag) { // find first [_First2, _Last2) satisfying _Pred, arbitrary iterators for (; ; ++_First1) { // loop until match or end of a sequence _FwdIt1 _Mid1 = _First1; for (_FwdIt2 _Mid2 = _First2; ; ++_Mid1, (void)++_Mid2) if (_Mid2 == _Last2) return (_First1); else if (_Mid1 == _Last1) return (_Last1); else if (!_Pred(*_Mid1, *_Mid2)) break; } } 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 *, random_access_iterator_tag, random_access_iterator_tag) { // find first [_First2, _Last2) satisfying _Pred, random-access iterators _Diff1 _Count1 = _Last1 - _First1; _Diff2 _Count2 = _Last2 - _First2; for (; _Count2 <= _Count1; ++_First1, (void)--_Count1) { // room for match, try it _FwdIt1 _Mid1 = _First1; for (_FwdIt2 _Mid2 = _First2; ; ++_Mid1, (void)++_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_IF(_First1 != _Last1 && _First2 != _Last2, _Pred); return (_Rechecked(_First1, _Search(_Unchecked(_First1), _Unchecked(_Last1), _Unchecked(_First2), _Unchecked(_Last2), _Pred, _Dist_type(_First1), _Dist_type(_First2), _Iter_cat(_First1), _Iter_cat(_First2)))); } // TEMPLATE FUNCTION search template<class _FwdIt1, class _FwdIt2> inline _FwdIt1 search(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2) { // find first [_First2, _Last2) match return (_STD search(_First1, _Last1, _First2, _Last2, equal_to<>())); }

源码摘抄自Visual Studio 2015安装目录algorithm文件中。

点击进入目录----> C++源码剖析目录