C++ In a Nutshell

Name

find_end function template — Searches for the last occurrence of a sequence

Synopsis

template<typename FwdIter1, typename FwdIter2>
  FwdIter1 find_end(FwdIter1 first1, FwdIter1 last1, FwdIter2 first2,
                    FwdIter2 last2);
template<typename FwdIter1, typename FwdIter2, typename BinaryPredicate>
  FwdIter1 find_end(FwdIter1 first1, FwdIter1 last1, FwdIter2 first2, 
                    FwdIter2 last2, BinaryPredicate pred);

The find_end function template finds the last (rightmost) subsequence [first2, last2) within the range [first1, last1), as illustrated in Figure 13-5. It returns an iterator, find_end in Figure 13-5, that points to the start of the matching subsequence or last1 if a match cannot be found.

The first form compares items with the == operator. The second form calls pred(*iter1, *iter2).

Figure 13-5. Finding a subsequence with find_end and search

Technical Notes

Let length1 = last1 - first1 and length2 = last2 - first2.

The find_end function template returns first1 + n, in which n is the highest value in the range [0, length1 - length2) such that *(i + n + m) == (first2 + m) for all i in the range [first1, last1) and 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, search function template