C++ In a Nutshell

Name

search function template — Searches a range for a subsequence

Synopsis

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.

Technical Notes

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.

See Also

find function template, find_end function template, search_n function template