Standard Template Library Programmer's Guide

See also

find, find_if, find_end, search_n, mismatch, equal

search_n

Category: algorithms

Component type: function

Prototype

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

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

Description

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.

Definition

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

Requirements on types

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.

Preconditions

• [first, last) is a valid range.

• count is non-negative [1].

Complexity

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

Example

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