I have forgotten
my Password

Or login with:

  • Facebookhttp://facebook.com/
  • Googlehttps://www.google.com/accounts/o8/id
  • Yahoohttps://me.yahoo.com

search

Searches for the first occurrence of a subrange
+ View version details

Key Facts

Gyroscopic Couple: The rate of change of angular momentum (\tau) = I\omega\Omega (In the limit).
  • I = Moment of Inertia.
  • \omega = Angular velocity
  • \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() algorithm is defined in the standard header <algorithm> and in the nonstandard backward-compatibility header <algo.h>.

Interface

#include <algorithm>
template < class ForwardIterator1, class ForwardIterator2 >
   ForwardIterator1 search(
      ForwardIterator1 first1, 
      ForwardIterator1 last1,
      ForwardIterator2 first2, 
      ForwardIterator2 last2
   );
template < class ForwardIterator1, class ForwardIterator2, class Pr >
   ForwardIterator1 search(
      ForwardIterator1 first1, 
      ForwardIterator1 last1,
      ForwardIterator2 first2, 
      ForwardIterator2 last2
      BinaryPredicate comp
   );

Parameters:
Parameter Description
first1 A forward iterator addressing the position of the first element in the range to be searched
last1 A forward iterator addressing the position one past the final element in the range to be searched
first2 A forward iterator addressing the position of the first element in the range to be matched
last2 A forward iterator addressing the position one past the final element in the range to be matched
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

This function searches a subsequence (elements from fi rst2 to last2 ) into sequence (elements from first1 to last1 ).

The two forms of search differ in how they determine if 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. If the subsequence wasn't found, last1 is returned.

Complexity

The complexity is linear, and worst case complexity is also linear with respect to the size of the sequence being searched for.
Example:

Example - search algorithm
Problem
This program illustrates the use of the STL search() algorithm (default version) to find the first occurrence of one range of integer values in a vector within another range of integer values, also in a vector.
Workings
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
  int a1[] = {1, 2, 3, 4, 5, 6, 7, 8, 3, 4, 5, 9, 10, 11};
  vector<int> v1(a1, a1+14);
  cout <<"\nHere are the contents of v1:\n";
  for (vector<int>::size_type i=0; i<v1.size(); i++)
    cout <<v1.at(i)<<" ";
 
  int a2[] = {3, 4, 5};
  vector<int> v2(a2, a2+3);
  cout <<"\nHere are the contents of v2:\n";
  for (vector<int>::size_type i=0; i<v2.size(); i++)
    cout <<v2.at(i)<<" ";
 
  vector<int>::iterator p;
 
  p = search(v1.begin(), v1.end(), v2.begin(), v2.end());
  if (p != v1.end())
    cout <<"\nThe first instance of v2 in v1 begins at location "<<(int)(p-v1.begin()+1)<<".";
  else
    cout <<"\nNo instance of v2 was found in v1.";
 
  p = search(p+1, v1.end(), v2.begin(), v2.end());
  if (p != v1.end())
    cout <<"\nThe next instance of v2 in v1 begins at location "<<(int)(p-v1.begin()+1)<<".";
  else
    cout<<"\nNo further instance of v2 was found in v1.";
 
  p = search(p+1, v1.end(), v2.begin(), v2.end());
  if (p != v1.end())
    cout <<"\nThe next instance of v2 in v1 begins at location "<< (int)(p-v1.begin()+1)<<".";
  else
    cout <<"\nNo further instance of v2 was found in v1.";
 
  return 0;
}
Solution
Output:

Here are the contents of v1: 1 2 3 4 5 6 7 8 3 4 5 9 10 11

Here are the contents of v2: 3 4 5

The first instance of v2 in v1 begins at location 3.

The next instance of v2 in v1 begins at location 9.

No further instance of v2 was found in v1.
References