Category: algorithms | Component type: function |
template <class ForwardIterator1, class ForwardIterator2> ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate binary_pred);
The first version of search returns the first iterator i in the range [first1, last1 - (last2 - first2)) [1] such that, for every iterator j in the range [first2, last2), *(i + (j - first2)) == *j. The second version returns the first iterator i in [first1, last1 - (last2 - first2)) such that, for every iterator j in [first2, last2), binary_pred(*(i + (j - first2)), *j) is true. These conditions simply mean that every element in the subrange beginning with i must be the same as the corresponding element in [first2, last2).
const char S1[] = "Hello, world!"; const char S2[] = "world"; const int N1 = sizeof(S1) - 1; const int N2 = sizeof(S2) - 1; const char* p = search(S1, S1 + N1, S2, S2 + N2); printf("Found subsequence \"%s\" at character %d of sequence \"%s\".\n", S2, p - S1, S1);
[1] The reason that this range is [first1, last1 - (last2 - first2)), instead of simply [first1, last1), is that we are looking for a subsequence that is equal to the complete sequence [first2, last2). An iterator i can't be the beginning of such a subsequence unless last1 - i is greater than or equal to last2 - first2. Note the implication of this: you may call search with arguments such that last1 - first1 is less than last2 - first2, but such a search will always fail.