# 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 first 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
    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

### Notes

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

### See also

`search`, `find_end`, `find`, `find_if`

Copyright © 1999 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation