## search, search_n

    Algorithm

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

### Summary

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

### Data Type and Member Function Indexes
(exclusive of constructors and destructors)

None

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

### Complexity

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.

### Example

    //
    // 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

### Warnings

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`.

Copyright (c) 1998, Rogue Wave Software, Inc.
Send mail to report errors or comment on the documentation.
OEM Release, June 1998