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 elementbyelement.
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 usersupplied
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
backwardcompatibility 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.
See also
find, find_if, find_end, search_n,
mismatch, equal
Copyright ©
1999 Silicon Graphics, Inc. All Rights Reserved.
TrademarkInformation
webmaster@www.sgi.com