search_n


function template
<algorithm>
template <class ForwardIterator, class Size, class T>
   ForwardIterator search_n ( ForwardIterator first, ForwardIterator last,
                              Size count, const T& value );

template <class ForwardIterator, class Size, class T, class BinaryPredicate>
   ForwardIterator search_n ( ForwardIterator first, ForwardIterator last,
                              Size count, const T& value. BinaryPredicate pred );

Find succession of equal values in range

Searches the range [first,last) for a succession of count elements, each of them comparing equal (or some other predicate) to value.

In the first version, the comparison is performed by applying the == comparison operator between the elements being iterated and value. In the second version, comp is applied to these, and a return value of true (or non-zero) is interpreted as an equivalence.

The behavior of this function template is equivalent to:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
template<class ForwardIterator, class Size, class T>
  ForwardIterator search_n ( ForwardIterator first, ForwardIterator last,
                             Size count, const T& value )
{
  ForwardIterator it, limit;
  Size i;

  limit=first; advance(limit,distance(first,last)-count);

  while (first!=limit)
  {
    it = first; i=0;
    while (*it==value)       // or: while (pred(*it,value)) for the pred version
      { ++it; if (++i==count) return first; }
    ++first;
  }
  return last;
}


Parameters

first, last
Forward iterators to the initial and final positions of the searched sequence. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
count
Minimum number of successive elements meeting the predicate to be considered a match.
Its type is an integral type or some other type convertible to it.
value
Individual value to be compared, or to be used as argument for pred (in the second version).
Its type has to support the appropriate equality comparison, for the first version.
pred
Binary predicate taking two elements as argument (one of each of the two sequences), and returning the result of the comparison between them, with true (non-zero) meaning that they are to be considered equal, and false (zero) that they are not-equal. This can either be a pointer to a function or an object whose class overloads operator().


Return value

An iterator to the first element of the first occurrence of the succession of count equal values in [first,last).
If the sequence is not found, the function returns last.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
// search_n example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool mypredicate (int i, int j) {
  return (i==j);
}

int main () {
  int myints[]={10,20,30,30,20,10,10,20};
  vector<int> myvector (myints,myints+8);

  vector<int>::iterator it;

  // using default comparison:
  it = search_n (myvector.begin(), myvector.end(), 2, 30);

  if (it!=myvector.end())
    cout << "two 30s found at position " << int(it-myvector.begin()) << endl;
  else
    cout << "match not found" << endl;

  // using predicate comparison:
  it = search_n (myvector.begin(), myvector.end(), 2, 10, mypredicate);

  if (it!=myvector.end())
    cout << "two 10s found at position " << int(it-myvector.begin()) << endl;
  else
    cout << "match not found" << endl;
  
  return 0;
}


Output:
Two 30s found at position 2
Two 10s found at position 5


Complexity

At most, performs as many comparisons or applications of pred as count*(distance(first,last)-count).

See also

search Find subsequence in range (function template)
find_first_of Find element from set in range (function template)
find Find value in range (function template)
equal Test whether the elements in two ranges are equal (function template)