Standard Template Library Programmer's Guide

find , find_if , find_end , search_n , mismatch , equal

Category: algorithms

Component type: function

Search_n is an overloaded name; there are actually two search_n functions.

template

ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Integer count, const T& value);

template

ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Integer count, const T& value, BinaryPredicate binary_pred);

Search_n searches for a subsequence of count consecutive elements in the range [first, last) , all of which are equal to value . [1] It returns an iterator pointing to the beginning of that subsequence, or else last if no such subsequence exists. The two versions of search_n 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 [first, last – count) [2] such that, for every iterator j in the range [i, i + count) , *j == value . The second version returns the first iterator i in the range [first, last – count) such that, for every iterator j in the range [i, i + count) , binary_pred(*j, value) is true .

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

For the first version:

• ForwardIterator is a model of Forward Iterator.

• Integer is an integral type.

• T is a model of EqualityComparable.

• ForwardIterator 's value type is a model of EqualityComparable.

• Objects of ForwardIterator 's value type can be compared for equality with Objects of type T .

For the second version:

• ForwardIterator is a model of Forward Iterator.

• Integer is an integral type.

• T is a model of EqualityComparable.

• BinaryPredicate is a model of Binary Predicate.

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

• T is convertible to BinaryPredicate 's second argument type.

• [first, last) is a valid range.

• count is non-negative [1].

Linear. Search_n performs at most last – first comparisons.

(The C++ standard permits the complexity to be O ( n ( last – first )), but this is unnecessarily lax. There is no reason for search_n to examine any element more than once.)

bool eq_nosign(int x, int y) { return abs(x) == abs(y); }

void lookup(int* first, int* last, size_t count, int val) {

cout << "Searching for a sequence of " << count << " '" << val << "'" << (count != 1 ? "s: " : ": ");

int* result = search_n(first, last, count, val);

if (result == last) cout << "Not found" << endl;

else cout << "Index = " << result – first << endl;

}

void lookup_nosign(int* first, int* last, size_t count, int val) {

cout << "Searching for a (sign-insensitive) sequence of " << count << " '" << val << "'" << (count != 1 ? "s: " : ": ");

int* result = search_n(first, last, count, val, eq_nosign);

if (result == last) cout << "Not found" << endl;

else cout << "Index = " << result – first << endl;

}

int main() {

const int N = 10;

int A[N] = {1, 2, 1, 1, 3, –3, 1, 1, 1, 1};

lookup(A, A+N, 1, 4);

lookup(A, A+N, 0, 4);

lookup(A, A+N, 1, 1);

lookup(A, A+N, 2, 1);

lookup(A, A+N, 3, 1);

lookup(A, A+N, 4, 1);

lookup(A, A+N, 1, 3);

lookup(A, A+N, 2, 3);

lookup_nosign(A, A+N, 1, 3);

lookup_nosign(A, A+N, 2, 3);

}

The output is

Searching for a sequence of 1 '4': Not found

Searching for a sequence of 0 '4's: Index = 0

Searching for a sequence of 1 '1': Index = 0

Searching for a sequence of 2 '1's: Index = 2

Searching for a sequence of 3 '1's: Index = 6

Searching for a sequence of 4 '1's: Index = 6

Searching for a sequence of 1 '3': Index = 4

Searching for a sequence of 2 '3's: Not found

Searching for a (sign-insensitive) sequence of 1 '3': Index = 4

Searching for a (sign-insensitive) sequence of 2 '3's: Index = 4

[1] Note that count is permitted to be zero: a subsequence of zero elements is well defined. If you call search_n with count equal to zero, then the search will always succeed: no matter what value is, every range contains a subrange of zero consecutive elements that are equal to value . When search_n is called with count equal to zero, the return value is always first .

[2] The reason that this range is [first, last – count) , rather than just [first, last) , is that we are looking for a subsequence whose length is count ; an iterator i can't be the beginning of such a subsequence unless last – count is greater than or equal to count . Note the implication of this: you may call search_n with arguments such that last – first is less than count , but such a search will always fail.

search , find_end , find , find_if

Category: algorithms

Component type: function

find_end is an overloaded name; there are actually two find_end functions.

template

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

template

ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate comp);