search, search_n

Algorithm

• Summary
• Data Type and Member Function Indexes
• Synopsis
• Description
• Complexity
• Example
• Warnings

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

None

#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)

The search and search_n algorithms search 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.

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

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

//
// search.cpp
//
 #include <algorithm>
 #include <list>
 #include <iostream>
 using namespace std;

 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;
 }

Program Output

The sub-sequence, substring, was found at the
location identified by a '*'
     Here's a string with a *substring in it

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

list<char, allocator<char> >

instead of:

list<char>

If your compiler does not support namespaces, then you do not need the using declaration for std.