std::find_end() algorithm
- since C++20
- since C++17
- until C++17
// (1)
template< class ForwardIt1, class ForwardIt2 >
constexpr ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last );
// (2)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
constexpr ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last,
BinaryPredicate p );
// (3)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last );
// (4)
template<
class ExecutionPolicy,
class ForwardIt1,
class ForwardIt2,
class BinaryPredicate
>
ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );
// (1)
template< class ForwardIt1, class ForwardIt2 >
ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last );
// (2)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last,
BinaryPredicate p );
// (3)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last );
// (4)
template<
class ExecutionPolicy,
class ForwardIt1,
class ForwardIt2,
class BinaryPredicate
>
ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );
// (1)
template< class ForwardIt1, class ForwardIt2 >
ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last );
// (2)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,
ForwardIt2 s_first, ForwardIt2 s_last,
BinaryPredicate p );
Searches for the last occurrence of the sequence [s_first
; s_last
) in the range [first
; last
).
-
(1) Compares elements with
operator==
. -
(2) Compares elements with the given binary predicate
p
. -
(3 - 4) Same as (1 - 2), but executed according to
policy
.Overload ResolutionThese overloads participate in overload resolution only if
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
(until C++20)std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>
(since C++20) istrue
.
Parameters
first last | The range of elements to examine. |
s_first s_last | The range of elements to search for. |
policy | The execution policy to use. See execution policy for details. |
p | Binary predicate which returns The signature of the function should be equivalent to the following:
|
Type requirements
ForwardIt1 ForwardIt2 | LegacyForwardIterator |
Return value
Iterator to the beginning of last occurrence of the sequence [s_first
; s_last
) in range [first
; last
).
s_first
; s_last
) is empty or if no such sequence is found, last
is returned. (since C++11)
If no such sequence is found,
last
is returned. (until C++11)
Complexity
Given S
as std::distance(s_first, s_last)
and N
as std::distance(first, last)
:
- (1, 3) - At most S * (N − S + 1) comparisons.
- (2, 4) - At most S * (N − S + 1) applications of
p
.
Exceptions
The overloads with a template parameter named ExecutionPolicy
report errors as follows:
- If execution of a function invoked as part of the algorithm throws an exception and
ExecutionPolicy
is one of the standard policies,std::terminate
is called. For any otherExecutionPolicy
, the behavior is implementation-defined. - If the algorithm fails to allocate memory,
std::bad_alloc
is thrown.
Possible implementation
find_end (1)
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 (true)
{
ForwardIt1 new_result = std::search(first, last, s_first, s_last);
if (new_result == last)
break;
else
{
result = new_result;
first = result;
++first;
}
}
return result;
}
find_end (2)
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 (true)
{
ForwardIt1 new_result = std::search(first, last, s_first, s_last, p);
if (new_result == last)
break;
else
{
result = new_result;
first = result;
++first;
}
}
return result;
}
Examples
#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
auto print_result = [](auto result, const auto& v)
{
result == v.end()
? std::cout << "Sequence not found\n"
: std::cout << "Last occurrence is at: " << std::distance(v.begin(), result)
<< '\n';
};
int main()
{
const auto v = {1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4};
for (auto const& x : { std::array {1, 2, 3}, {4, 5, 6} })
{
auto iter = std::find_end(v.begin(), v.end(), x.begin(), x.end()); // overload (1)
print_result(iter, v);
}
for (auto const& x : { std::array {-1, -2, -3}, {-4, -5, -6} })
{
auto iter = std::find_end(v.begin(), v.end(), x.begin(), x.end(), // overload (3)
[](int x, int y)
{
return std::abs(x) == std::abs(y);
});
print_result(iter, v);
}
}
Last occurrence is at: 8
Sequence not found
Last occurrence is at: 8
Sequence not found
Hover to see the original license.