Click on the banner to return to the Class Reference home page.

©Copyright 1996 Rogue Wave Software

search, search_n


     Algorithm

Summary

Finds a subsequence within a sequence of values that is element-wise equal to the values in an indicated range.

Contents

Synopsis

#include <algorithm>
template <class ForwardIterator1, class ForwardIterator2>
 ForwardIterator1 search (ForwardIterator1 first1,
                          ForwardIterator1 last1,
                          ForwardIterator2 first2,
                          ForwardIterator2 last2);
template <class ForwardIterator1,
          class ForwardIterator2,
          class BinaryPredicate>
 ForwardIterator1 search (ForwardIterator1 first1,
                          ForwardIterator1 last1,
                          ForwardIterator2 first2,
                          ForwardIterator2 last2,
                          BinaryPredicate binary_pred);
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)

Description

The search and search_n are used for searching for a subsequence within a sequence. The search algorithm searches for a subsequence [first2, last2) within a sequence [first1, last1), and returns the beginning location of the subsequence. If it does not find the subsequence, search returns last1. The first version of search uses the equality (==) 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 [first, last), and returns first if this subsequence is found. If it does not find the subsequence, search_n returns last. The first version of search_n uses the equality (==) operator as a default, and the second version allows you to specify a binary predicate to perform the comparison.

Complexity

search performs at most (last1 - first1)*(last2-first2) applications of the corresponding predicate.

search_n performs at most (last - first) applications of the corresponding predicate.

Example

//
// search.cpp
//
 #include <algorithm>
 #include <list>
 #include <iostream.h>
 int main()
 {
   // 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> sequence(seq, seq+39);
   list<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>::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>::iterator i = sequence.begin(); 
           i != sequence.end(); i++)
     cout << *i;
   cout << endl;
   return 0;
 }
Output :
The subsequence, substring, was found at the
location identified by a '*'
     Here's a string with a *ubstring in it

Warning

If your compiler does not support default template parameters, then you need to always supply the Allocator template argument. For instance, you will need to write :

list<char, allocator>

instead of :

list<char>