Standard Template Library Programmer's Guide

equal , search , find , find_if

Category: algorithms

Component type: function

Equal is an overloaded name; there are actually two equal functions.

template

bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

template

bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate binary_pred);

Equal returns true if the two ranges [first1, last1) and [first2, first2 + (last1 – first1)) are identical when compared element-by-element, and otherwise returns false . [1]

The first version of equal returns true if and only if for every iterator i in [first1, last1) , *i == *(first2 + (i – first1)) . The second version of equal returns true if and only if for every iterator i in [first1, last1) , binary_pred(*i, *(first2 + (i – first1)) is true .

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

For the first version:

• InputIterator1 is a model of Input Iterator.

• InputIterator2 is a model of Input Iterator.

• InputIterator1 's value type is a model of Equality Comparable.

• InputIterator2 's value type is a model of Equality Comparable.

• InputIterator1 's value type can be compared for equality with InputIterator2 's value type.

For the second version:

• InputIterator1 is a model of Input Iterator.

• InputIterator2 is a model of Input Iterator.

• BinaryPredicate is a model of Binary Predicate.

• InputIterator1 's value type is convertible to BinaryPredicate 's first argument type.

• InputIterator2 's value type is convertible to BinaryPredicate 's second argument type.

• [first1, last1) is a valid range.

• [first2, first2 + (last2 – last1)) is a valid range.

Linear. At most last1 – first1 comparisons.

int A1[] = { 3, 1, 4, 1, 5, 9, 3 };

int A2[] = { 3, 1, 4, 2, 8, 5, 7 };

const int N = sizeof(A1) / sizeof(int);

cout << "Result of comparison: " << equal(A1, A1 + N, A2) << endl;

[1] Note that this is very similar to the behavior of mismatch : The only real difference is that while equal will simply return false if the two ranges differ, mismatch returns the first location where they do differ. The expression equal(f1, l1, f2) is precisely equivalent to the expression mismatch(f1, l1, f2).first == l1 , and this is in fact how equal could be implemented.

mismatch , search , find , find_if

Category: algorithms

Component type: function

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

template

ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);

template

ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate binary_pred);

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

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

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.

• [first1, last1) is a valid range.

• [first2, last2) is a valid range.

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

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.