Standard C++ Library
Copyright 1998, 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 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 com-
posed 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 ver-
sion 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 parame-
ters, 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.
<ENDNOTES> </ENDNOTES>