search function template — Searches a range for a subsequence
template<typename FwdIter1, typename FwdIter2> FwdIter1 search(FwdIter1 first1, FwdIter1 last1, FwdIter2 first2, FwdIter2 last2); template<typename FwdIter1, typename FwdIter2, typename BinaryPredicate> FwdIter1 search(FwdIter1 first1, FwdIter1 last1, FwdIter2 first2, FwdIter2 last2, BinaryPredicate pred);
The search
function
template finds the first (leftmost) subsequence [first2
, last2
) within the range [first1
, last1
). It returns an iterator that points
to the start of the subsequence or last1
if the subsequence is not
found.
The first form compares items with the ==
operator. The second form calls
pred(*iter1
, *iter2)
.
Figure 13-5 (under
find_end
) illustrates the
search
function template.
Let length1
= last1
- first1
and length2
= last2
- first2
.
The search
function
template returns first1
+
n
, in which n
is the smallest value in the range [0,
length1
- length2
) such that *(i
+ n
+ m
) == (first2
+ m
) for all m
in the range [0, length2
). It returns last1
if no such n
can be found.
Complexity: at most length1
× length2
comparisons are performed.