std::find_end
Defined in header
<algorithm>
|
||
template< class ForwardIt1, class ForwardIt2 >
ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last, |
(1) | |
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last, |
(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
.
Contents |
[edit] 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: bool pred(const Type1 &a, const Type2 &b); The signature does not need to have const &, but the function must not modify the objects passed to it. |
Type requirements | ||
-
ForwardIt1 must meet the requirements of ForwardIterator .
|
||
-
ForwardIt2 must meet the requirements of ForwardIterator .
|
[edit] 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) |
[edit] Complexity
Does at most S*(N-S+1)
comparisons where S = distance(s_first, s_last) and N = distance(first, last).
[edit] 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; } |
[edit] 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
[edit] 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) |
|
(parallelism TS)
|
parallelized version of std::find_end (function template) |