search(), search_n()

Library:  Algorithms

Function

• Local Index
• Summary
• Synopsis
• Description
• Complexity
• Example
• Standards Conformance

An algorithm that finds a subsequence within a sequence of values

#include <algorithm>

namespace std {
  template <class ForwardIterator1, class ForwardIterator2>
  ForwardIterator1 search(ForwardIterator1 start1,
                          ForwardIterator1 finish1,
                          ForwardIterator2 start2,
                          ForwardIterator2 finish2);

  template <class ForwardIterator1,
            class ForwardIterator2,
            class BinaryPredicate>
  ForwardIterator1 search(ForwardIterator1 start1,
                          ForwardIterator1 finish1,
                          ForwardIterator2 start2,
                          ForwardIterator2 finish2,
                          BinaryPredicate binary_pred);

  template <class ForwardIterator, class Size, class T>
  ForwardIterator search_n(ForwardIterator start,
                           ForwardIterator finish,
                           Size count, const T& value);

  template <class ForwardIterator, class Size,
            class T, class BinaryPredicate>
  ForwardIterator search_n(ForwardIterator start 
                           ForwardIterator finish,
                           Size count, const T& value,
                           BinaryPredicate pred)
}

The search() and search_n() algorithms search for a subsequence within a sequence. The search() algorithm searches for a subsequence [start2, finish2) within a sequence [start1, finish1), and returns the beginning location of the subsequence. If it does not find the subsequence, search() returns finish1. The first version of search() uses operator==() as a default, and the second version allows you to specify a binary predicate to perform the comparison.

The search_n() algorithm searches for the subsequence composed of count occurrences of value within a sequence [start, finish), and returns start if this subsequence is found. If it does not find the subsequence, search_n() returns finish. The first version of search_n() uses operator==() as a default, and the second version allows you to specify a binary predicate to perform the comparison.

search() performs at most (finish1 - start1)*(finish2-start2) applications of the corresponding predicate.

search_n() performs at most (finish - start)* count applications of the corresponding predicate.

//
//  search.cpp
//

#include <algorithm>
#include <list>
#include <iostream>


int main ()
{
#ifndef _RWSTD_NO_NAMESPACE
  using namespace std;
#endif

  // Initialize a list sequence and subsequence with 
  // characters.

  char seq[40]    = "Here's a string with a substring in it";
  char subseq[10] = "substring";
  list<char,allocator<char> > sequence(seq, seq+38);
  list<char,allocator<char> > subseqnc(subseq, subseq+9);

  // Print out the original sequence.

  cout << endl << "The subsequence, " << subseq 
       << ", was found at the ";
  cout << endl << "location identified by a '*'" 
       << endl << "     ";

  // Create an iterator to identify the location of 
  // subsequence within sequence.

  list<char,allocator<char> >::iterator place;

  // Do search.

  place = search(sequence.begin(), sequence.end(),
                 subseqnc.begin(), subseqnc.end());

  // Identify result by marking first character with a '*'.

  *place = '*';

  // Output sequence to display result.

  for (list<char,allocator<char> >::iterator i = 
       sequence.begin(); i != sequence.end(); i++)
    cout << *i;
  cout << endl;

  return 0;
}


Program Output:

The subsequence, substring, was found at the 
location identified by a '*'
     Here's a string with a *ubstring in it

ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.1.9