Library: Algorithms
Function
An algorithm that finds a subsequence within a sequence of values
#include <algorithm>
namespace std {
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search(ForwardIterator1 start1,
ForwardIterator1 finish1,
ForwardIterator2 start2,
ForwardIterator2 finish2);
template <class ForwardIterator1,
class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1 search(ForwardIterator1 start1,
ForwardIterator1 finish1,
ForwardIterator2 start2,
ForwardIterator2 finish2,
BinaryPredicate binary_pred);
template <class ForwardIterator, class Size, class T>
ForwardIterator search_n(ForwardIterator start,
ForwardIterator finish,
Size count, const T& value);
template <class ForwardIterator, class Size,
class T, class BinaryPredicate>
ForwardIterator search_n(ForwardIterator start
ForwardIterator finish,
Size count, const T& value,
BinaryPredicate pred)
}
The search() and search_n() algorithms search for a subsequence within a sequence. The search() algorithm searches for a subsequence [start2, finish2) within a sequence [start1, finish1), and returns the beginning location of the subsequence. If it does not find the subsequence, search() returns finish1. The first version of search() uses 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 [start, finish), and returns start if this subsequence is found. If it does not find the subsequence, search_n() returns finish. The first version of search_n() uses operator==() as a default, and the second version allows you to specify a binary predicate to perform the comparison.
search() performs at most (finish1 - start1)*(finish2-start2) applications of the corresponding predicate.
search_n() performs at most (finish - start)* count applications of the corresponding predicate.
//
// search.cpp
//
#include <algorithm>
#include <list>
#include <iostream>
int main ()
{
#ifndef _RWSTD_NO_NAMESPACE
using namespace std;
#endif
// 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,allocator<char> > sequence(seq, seq+38);
list<char,allocator<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,allocator<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,allocator<char> >::iterator i =
sequence.begin(); i != sequence.end(); i++)
cout << *i;
cout << endl;
return 0;
}
Program Output:
The subsequence, substring, was found at the location identified by a '*' Here's a string with a *ubstring in it
ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.1.9