| Defined in header <algorithm> | ||
|---|---|---|
template< class ForwardIt1, class ForwardIt2 >
ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last ); | (1) | |
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p ); | (2) |
Searches for the last subsequence of elements [s_first, s_last) in the range [first, last). The first version uses operator== to compare the elements, the second version uses the given binary predicate p.
Parameters
| first, last | - | the range of elements to examine |
| s_first, s_last | - | the range of elements to search for |
| p | - | binary predicate which returns true if the elements should be treated as equal. The signature of the predicate function should be equivalent to the following:
The signature does not need to have |
| Type requirements | ||
- ForwardIt1 must meet the requirements of ForwardIterator. | ||
- ForwardIt2 must meet the requirements of ForwardIterator. | ||
Return value
Iterator to the beginning of last subsequence [s_first, s_last) in range [first, last).
| If no such subsequence is found, | (until C++11) |
| If | (since C++11) |
Complexity
Does at most S*(N-S+1) comparisons where S = distance(s_first, s_last) and N = distance(first, last).
Possible implementation
| First version |
|---|
template<class ForwardIt1, class ForwardIt2>
ForwardIt1 find_end(ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last)
{
if (s_first == s_last)
return last;
ForwardIt1 result = last;
while (1) {
ForwardIt1 new_result = std::search(first, last, s_first, s_last);
if (new_result == last) {
return result;
} else {
result = new_result;
first = result;
++first;
}
}
return result;
} |
| Second version |
template<class ForwardIt1, class ForwardIt2, class BinaryPredicate>
ForwardIt1 find_end(ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last,
BinaryPredicate p)
{
if (s_first == s_last)
return last;
ForwardIt1 result = last;
while (1) {
ForwardIt1 new_result = std::search(first, last, s_first, s_last, p);
if (new_result == last) {
return result;
} else {
result = new_result;
first = result;
++first;
}
}
return result;
} |
Example
The following code uses find_end() to search for two different sequences of numbers.
#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> v{1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4};
std::vector<int>::iterator result;
std::vector<int> t1{1, 2, 3};
result = std::find_end(v.begin(), v.end(), t1.begin(), t1.end());
if (result == v.end()) {
std::cout << "subsequence not found\n";
} else {
std::cout << "last subsequence is at: "
<< std::distance(v.begin(), result) << "\n";
}
std::vector<int> t2{4, 5, 6};
result = std::find_end(v.begin(), v.end(), t2.begin(), t2.end());
if (result == v.end()) {
std::cout << "subsequence not found\n";
} else {
std::cout << "last subsequence is at: "
<< std::distance(v.begin(), result) << "\n";
}
}Output:
last subsequence is at: 8 subsequence not found
See also
| searches for a range of elements (function template) | |
| returns true if one set is a subset of another (function template) | |
| finds the first two adjacent items that are equal (or satisfy a given predicate) (function template) | |
| (C++11) | finds the first element satisfying specific criteria (function template) |
| searches for any one of a set of elements (function template) | |
| searches for a number consecutive copies of an element in a range (function template) | |
| std::experimental::parallel::find_end
(parallelism TS) | parallelized version of std::find_end (function template) |
Please login to continue.