Standard C++	Library
 		 Copyright 1996, Rogue Wave Software, Inc.

 NAME

   search, search_n  - Finds a sub-sequence within a sequence of	values
   that is element-wise equal	to the values in an indicated range.

 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 sub-sequence
   within a sequence. The	search algorithm searches for a
   sub-sequence [first2, last2) within a sequence [first1, last1), and
   returns the beginning location	of the sub-sequence.   If it
   does not find the sub-sequence, 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 sub-sequence	composed of
   count occurrences of value within a	sequence [first, last),	and
   returns first if this sub-sequence is found.  If it does not find
   the sub-sequence, 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
      //	sub-sequence 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 sub-sequence, " << subseq
 	  << ",	was found at the ";
     cout << endl << "location identified by a '*'"
 	  << endl << "	   ";

      //	Create an iterator to identify the location of
      //	sub-sequence 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 sub-sequence, substring, was found at the
   location identified by a '*'
       Here's a string with a *substring	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<char> >

   instead of :

   list<char>

 STANDARDS CONFORMANCE
   ANSI X3J16/ISO WG21 Joint C++	Committee