|
find_end
function template
<algorithm>
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_end ( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2 );
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1 find_end ( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2.
BinaryPredicate pred );
Find last subsequence in range
Searches the range [first1,last1) for the last 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 to each element, 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
19
|
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_end ( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2)
{
ForwardIterator1 it1, limit, ret;
ForwardIterator2 it2;
limit=first1; advance(limit,1+distance(first1,last1)-distance(first2,last2));
ret=last1;
while (first1!=limit)
{
it1 = first1; it2 = first2;
while (*it1==*it2) // or: while (pred(*it1,*it2)) for the pred version
{ ++it1; ++it2; if (it2==last2) {ret=first1;break;} }
++first1;
}
return ret;
}
|
A similar algorithm function, but returning the first occurrence instead of the last, is search.
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 last 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
|
// find_end example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool myfunction (int i, int j) {
return (i==j);
}
int main () {
int myints[] = {1,2,3,4,5,1,2,3,4,5};
vector<int> myvector (myints,myints+10);
vector<int>::iterator it;
int match1[] = {1,2,3};
// using default comparison:
it = find_end (myvector.begin(), myvector.end(), match1, match1+3);
if (it!=myvector.end())
cout << "match1 last found at position " << int(it-myvector.begin()) << endl;
int match2[] = {4,5,1};
// using predicate comparison:
it = find_end (myvector.begin(), myvector.end(), match2, match2+3, myfunction);
if (it!=myvector.end())
cout << "match2 last found at position " << int(it-myvector.begin()) << endl;
return 0;
}
|
Output:
Match found at position 5
Match found at position 3
|
Complexity
At most, performs count2*(1+count1-count2) comparisons or applications of pred (where countX is the distance between firstX and lastX).
See also
| search | Find subsequence in range (function template) |
| find | Find value in range (function template) |
| find_if | Find element in range (function template) |
|