Search for the sequence [ first2...last2 ) within the sequence [ first1, last1 ). Return an iterator into [ first1...last1 ) at the location the second sequence was found, or return last1 if the sequence was not found. The first version uses operator== to compare elements, whereas the second version uses the binary function binary_pred .

Complexity

Time complexity is quadratic. Space complexity is constant.

Example <ospace/osstd/examples/search0.cpp>


    #include <iostream>
#include <algorithm>

int v1[ 6 ] = { 1, 1, 2, 3, 5, 8 };
int v2[ 6 ] = { 0, 1, 2, 3, 4, 5 };
int v3[ 2 ] = { 3, 4 };

void
main()
  {
  int* location;

  location = search( v1, v1 + 6, v3, v3 + 2 );

  if ( location == v1 + 6 )
    cout << "v3 not contained in v1\n";
  else
    cout << "Found v3 in v1 at offset: " << location - v1 << "\n";

  location = search( v2, v2 + 6, v3, v3 + 2 );

  if ( location == v2 + 6 )
    cout << "v3 not contained in v2\n";
  else
    cout << "Found v3 in v2 at offset: " << location - v2 << "\n";
  }

v3 not contained in v1
Found v2 in v2 at offset: 3

Example <ospace/osstd/examples/search1.cpp>


    #include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>

void
main()
  {
  vector< int > v1( 10 );
  int i;
  for ( i = 0; i < v1.size(); ++i )
    v1[ i ] = i;
  vector< int > v2( 3 );
  for ( i = 0; i < v2.size(); ++i )
    v2[ i ] = 50 + i;
  ostream_iterator< int > iter( cout, " " );
  cout << "v1: ";
  copy( v1.begin(), v1.end(), iter );
  cout << "\n";
  cout << "v2: ";
  copy( v2.begin(), v2.end(), iter );
  cout << "\n";
  vector< int >::iterator location;

  location = search( v1.begin(), v1.end(), v2.begin(), v2.end() );

  if ( location == v1.end() )
    cout << "v2 not contained in v1\n";
  else
    cout << "Found v2 in v1 at offset: " << location - v1.begin() << "\n";
  for ( i = 0; i < v2.size(); ++i )
    v2[ i ] = 4 + i;
  cout << "v1: ";
  copy( v1.begin(), v1.end(), iter );
  cout << "\n";
  cout << "v2: ";
  copy( v2.begin(), v2.end(), iter );
  cout << "\n";

  location = search( v1.begin(), v1.end(), v2.begin(), v2.end() );

  if ( location == v1.end() )
    cout << "v2 not contained in v1\n";
  else
    cout << "Found v2 in v1 at offset: " << location - v1.begin() << "\n";

  }

v1: 0 1 2 3 4 5 6 7 8 9
v2: 50 51 52
v2 not contained in v1
v1: 0 1 2 3 4 5 6 7 8 9
v2: 4 5 6
Found v2 in v1 at offset: 4

Example <ospace/osstd/examples/search2.cpp>


    #include <iostream>
#include <string.h>
#include <algorithm>

char* grades[] = { "A", "B", "C", "D", "F" };
char* letters[] = { "Q", "E", "D" };

bool
str_equal( const char* a_, const char* b_ )
  {
  return ::strcmp( a_, b_ ) == 0 ? 1 : 0;
  }

void
main()
  {
  const unsigned grade_count = sizeof( grades ) / sizeof( grades[ 0 ] );
  const unsigned letter_count = sizeof( letters ) / sizeof( letters[ 0 ] );
  ostream_iterator< char* > iter( cout, " " );
  cout << "grades: ";
  copy( grades, grades + grade_count, iter );
  cout << "\nletters:";
  copy( letters, letters + letter_count, iter );
  cout << "\n";

  char** location = search
    (
    grades,
    grades + grade_count,
    letters,
    letters + letter_count,
    str_equal
    );

  if ( location == grades + grade_count )
    cout << "letters not found in grades\n";
  else
    cout
      << "letters found in grades at offset: "
      << ( location - grades )
      << "\n";
  copy
    (
    grades + 1,
    grades + 1 + letter_count,
    letters
    );
  cout << "grades: ";
  copy( grades, grades + grade_count, iter );
  cout << "\nletters:";
  copy( letters, letters + letter_count, iter );
  cout << "\n";

  location = search
    (
    grades,
    grades + grade_count,
    letters,
    letters + letter_count,
    str_equal
    );

  if ( location == grades + grade_count )
    cout << "letters not found in grades\n";
  else
    cout
      << "letters found in grades at offset: "
      << ( location - grades )
      << "\n";
  }

grades: A B C D F
letters:Q E D
letters not found in grades
grades: A B C D F
letters:B C D
letters found in grades at offset: 1

search

Library

Declaration

Complexity

Example <ospace/osstd/examples/search0.cpp>

Example <ospace/osstd/examples/search1.cpp>

Example <ospace/osstd/examples/search2.cpp>