search


Category: algorithms	Component type: function

Prototype

Search is an overloaded name; there are actually two search functions.

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);

Description

Search finds a subsequence within the range [first1 last1) that is identical to [first2 last2) when compared element-by-element. It returns an iterator pointing to the beginning of that subsequence or else last1 if no such subsequence exists. The two versions of search differ in how they determine whether two elements are the same: the first uses operator== and the second uses the user-supplied function object 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).

Definition

Defined in the standard header algorithm and in the nonstandard backward-compatibility header algo.h.

Requirements on types

For the first version:

ForwardIterator1 is a model of Forward Iterator.
ForwardIterator2 is a model of Forward Iterator.
ForwardIterator1's value type is a model of EqualityComparable.
ForwardIterator2's value type is a model of EqualityComparable.
Objects of ForwardIterator1's value type can be compared for equality with Objects of ForwardIterator2's value type.

For the second version:

ForwardIterator1 is a model of Forward Iterator.
ForwardIterator2 is a model of Forward Iterator.
BinaryPredicate is a model of Binary Predicate.
ForwardIterator1's value type is convertible to BinaryPredicate's first argument type.
ForwardIterator2's value type is convertible to BinaryPredicate's second argument type.

Preconditions

[first1 last1) is a valid range.
[first2 last2) is a valid range.

Complexity

Worst case behavior is quadratic: at most (last1 - first1) * (last2 - first2) comparisons. This worst case however is rare. Average complexity is linear.

Example

  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);

Notes

[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.