|
<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 pred );
Find subsequence in range
Searches the range [first1,last1) for the first occurrence of the sequence defined by [first2,last2), and returns an iterator to its first element.
The sequence of elements in [first2,last2) is compared to the possible subsequences of successive elements within [first1,last1) by either applying the == comparison operator or the template parameter comp (for the second version).
The behavior of this function template is equivalent to:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search ( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2)
{
ForwardIterator1 it1, limit;
ForwardIterator2 it2;
limit=first1; advance(limit,1+distance(first1,last1)-distance(first2,last2));
while (first1!=limit)
{
it1 = first1; it2 = first2;
while (*it1==*it2) // or: while (pred(*it1,*it2)) for the pred version
{ ++it1; ++it2; if (it2==last2) return first1; }
++first1;
}
return last1;
}
|
A similar algorithm function, but returning the last occurrence instead of the first, is find_end.
Parameters
- first1, last1
- Forward iterators to the initial and final positions of the searched sequence. The range used is [first1,last1), which contains all the elements between first1 and last1, including the element pointed by first1 but not the element pointed by last1.
- first2, last2
- Forward iterators to the initial and final positions of the sequence to be searched for. The range used is [first2,last2).
- pred
- Binary predicate taking two elements as argument (one of each of the two sequences), and returning the result of the comparison between them, with true (non-zero) meaning that they are to be considered equal, and false (zero) that they are not-equal. This can either be a pointer to a function or an object whose class overloads operator().
Return value
An iterator to the first element of the first occurrence of the sequence [first2,last2) in [first1,last1).
If the sequence is not found, the function returns last1.
Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
// search algorithm example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool mypredicate (int i, int j) {
return (i==j);
}
int main () {
vector<int> myvector;
vector<int>::iterator it;
// set some values: myvector: 10 20 30 40 50 60 70 80 90
for (int i=1; i<10; i++) myvector.push_back(i*10);
// using default comparison:
int match1[] = {40,50,60,70};
it = search (myvector.begin(), myvector.end(), match1, match1+4);
if (it!=myvector.end())
cout << "match1 found at position " << int(it-myvector.begin()) << endl;
else
cout << "match1 not found" << endl;
// using predicate comparison:
int match2[] = {20,30,50};
it = search (myvector.begin(), myvector.end(), match2, match2+3, mypredicate);
if (it!=myvector.end())
cout << "match2 found at position " << int(it-myvector.begin()) << endl;
else
cout << "match2 not found" << endl;
return 0;
}
|
Output:
match1 found at position 3
match2 not found
|
Complexity
At most, performs count2*(1+count1-count2) comparisons or applications of pred (where countX is the distance between firstX and lastX).
See also
| find_end | Find last subsequence in range (function template) |
| search_n | Find succession of equal values in range (function template) |
| equal | Test whether the elements in two ranges are equal (function template) |
| mismatch | Return first position where two ranges differ (function template) |
| find | Find value in range (function template) |
|