| find_end | function template |
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 ); |
<algortihm> |
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:
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
// 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 |
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) |