Computing › Stl › Algorithms › Nonmodifying ›

search_n

Searches for the first n consecutive elements with certain properties

View version details

Contents

Definition
Interface
Description
Return Value
Complexity
Page Comments

Key Facts

Gyroscopic Couple: The rate of change of angular momentum ( $\inline \tau$ ) = $\inline I\omega\Omega$ (In the limit).

$\inline I$ = Moment of Inertia.
$\inline \omega$ = Angular velocity
$\inline \Omega$ = Angular velocity of precession.

Blaise Pascal (1623-1662) was a French mathematician, physicist, inventor, writer and Catholic philosopher.

Leonhard Euler (1707-1783) was a pioneering Swiss mathematician and physicist.

Definition

The search_n() algorithm is defined in the standard header <algorithm>, and in the nonstandard backward-compatibility header <algo.h>.

Interface

#include <algorithm>
template < class ForwardIterator1, class Diff2, class Type >
   ForwardIterator1 search_n(
      ForwardIterator1 first, 
      ForwardIterator1 last,
      Size2 count, 
      const Type& val
   );
template < class ForwardIterator1, 
           class Size2, 
           class Type, 
           class BinaryPredicate >
   ForwardIterator1 search_n(
      ForwardIterator1 first, 
      ForwardIterator1 last,
      Size2 count, 
      const Type& val,
      BinaryPredicate comp
   );

Parameters:

Parameter	Description
first	A forward iterator addressing the position of the first element in the range to be searched
last	A forward iterator addressing the position one past the final element in the range to be searched
count	The size of the subsequence being searched for
val	The value of the elements in the sequence being searched for
comp	User-defined predicate function object that defines the condition to be satisfied if two elements are to be taken as equivalent. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied

Description

Search_n searches for a subsequence of count consecutive elements in the range [first, last), all of which are equal to val.

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

Return Value

The return value is a forward iterator addressing the position of the first element of the first subsequence that matches the specified sequence or that is equivalent in a sense specified by a binary predicate.

Complexity

The complexity is linear, search_n performs at most last - first comparisons.

References

http://msdn.microsoft.com/en-us/

Example:

Example - search_n algorithm

Problem

The following example searches for three consecutive elements that have a value equal to or greater than 3.

Workings

#include <iostream>
#include <algorithm>
#include <deque>
 
using namespace std;
 
int main()
{
  deque<int> coll;
 
  INSERT_ELEMENTS(coll,1,9);
  PRINT_ELEMENTS(coll);
 
  // find three consecutive elements with value 4
  deque<int>::iterator pos;
  pos = search_n (coll.begin(), coll.end(),   // range
                             4,               // count
                             3);              // value
 
  // print result
  if (pos != coll.end()) 
    cout <<"four consecutive elements with value 3 "
         <<"start with "<<distance(coll.begin(),pos) +1
         << ". element" << endl;
  else 
    cout <<"no four consecutive elements with value 3 found"<< endl;
 
  // find three consecutive elements with value greater than 4
  pos = search_n (coll.begin(), coll.end(),  // range
                        4,                   // count
                        3,                   // value
                        greater<int>());     // criterion
 
  // print result
  if (pos != coll.end()) {
    cout <<"four consecutive elements with value > 3 "
         <<"start with "<<distance(coll.begin(),pos) +1
                 <<". element"<<endl;
  else  
    cout <<"no four consecutive elements with value > 3 found"<< endl;
 
  return 0;
}

Solution

Output:

1 2 3 4 5 6 7 8 9
no four consecutive elements with value 3 found
four consecutive elements with value > 3 start with 4. element