std::ranges::find_end() algorithm
- since C++20
- Simplified
- Detailed
// (1)
constexpr ranges::subrange<I1>
find_end( I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );
// (2)
constexpr ranges::borrowed_subrange_t<R1>
find_end( R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );
The type of arguments are generic and have the following constraints:
I1
,I2
-std::forward_iterator
S1
,S2
-std::sentinel_for<I1>
,std::sentinel_for<I2>
Pred
- (none)Proj1
,Proj2
- (none)- (2) -
R1
,R2
-std::ranges::forward_range
The Proj1
and Proj2
template arguments have a default type of std::identity
for all overloads.
Additionally, each overload has the following constraints:
- (1) -
indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
- (2) -
indirectly_comparable<ranges::iterator_t<R1>, ranges::iterator_t<R2>, Pred, Proj1, Proj2>
(The std::
namespace was ommitted here for readability)
// (1)
template<
std::forward_iterator I1,
std::sentinel_for<I1> S1,
std::forward_iterator I2,
std::sentinel_for<I2> S2,
class Pred = ranges::equal_to,
class Proj1 = std::identity,
class Proj2 = std::identity
>
requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr ranges::subrange<I1>
find_end( I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );
// (2)
template<
ranges::forward_range R1,
ranges::forward_range R2,
class Pred = ranges::equal_to,
class Proj1 = std::identity,
class Proj2 = std::identity
>
requires std::indirectly_comparable<ranges::iterator_t<R1>, ranges::iterator_t<R2>, Pred, Proj1, Proj2>
constexpr ranges::borrowed_subrange_t<R1>
find_end( R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {} );
Searches for the last occurrence of a sequence in a range.
-
(1) Searches for the last occurrence of the sequence [
first2
;last2
) in the range [first1
;last1
), after projection withproj1
andproj2
respectively. The projected elements are compared using the binary predicatepred
. -
(2) Same as (1), but uses
r1
as the first source range andr2
as the second source range, as if usingranges::begin(r1)
asfirst1
,ranges::end(r1)
aslast1
,ranges::begin(r2)
asfirst2
, andranges::end(r2)
aslast2
.
The function-like entities described on this page are niebloids.
Parameters
first1 last1 | The range of elements to examine. |
first2 last2 | The range of elements to search for. |
r1 | The range of elements to examine. |
r2 | The range of elements to search for. |
pred | Binary predicate to compare the elements with. |
proj1 | Projection to apply to the elements in the first range. |
proj2 | Projection to apply to the elements in the second range. |
Return value
-
(1) Value of type
ranges::subrange<I1>
initialized as follows:{
i,
i + (i == last1 ? 0 : ranges::distance(first2, last2))
}that denotes the last occurrence of the sequence [
first2
;last2
) in range [first1
;last1
) (after projections withproj1
andproj2
).If [
first2
;last2
) is empty or if no such sequence is found, the return value is effectively initialized with{ last1, last1 }
. -
(2) Same as (1), except that the return type is
ranges::borrowed_subrange_t<R1>
.
Complexity
- (1) Given
S
asranges::distance(first2, last2)
andN
asranges::distance(first1, last1)
- (2) Given
S
asranges::distance(r2)
andN
asranges::distance(r1)
At most S * (N - S + 1) applications of predicate and each projection.
Exceptions
(none)
Possible implementation
find_end(1)
struct find_end_fn
{
template<std::forward_iterator I1, std::sentinel_for<I1> S1,
std::forward_iterator I2, std::sentinel_for<I2> S2,
class Pred = ranges::equal_to,
class Proj1 = std::identity, class Proj2 = std::identity>
requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr ranges::subrange<I1>
operator()(I1 first1, S1 last1,
I2 first2, S2 last2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {}) const
{
if (first2 == last2)
{
auto last_it = ranges::next(first1, last1);
return {last_it, last_it};
}
auto result = ranges::search(
std::move(first1), last1, first2, last2, pred, proj1, proj2);
if (result.empty()) return result;
for (;;)
{
auto new_result = ranges::search(
std::next(result.begin()), last1, first2, last2, pred, proj1, proj2);
if (new_result.empty())
return result;
else
result = std::move(new_result);
}
}
template<ranges::forward_range R1, ranges::forward_range R2,
class Pred = ranges::equal_to,
class Proj1 = std::identity,
class Proj2 = std::identity>
requires std::indirectly_comparable<ranges::iterator_t<R1>,
ranges::iterator_t<R2>,
Pred, Proj1, Proj2>
constexpr ranges::borrowed_subrange_t<R1>
operator()(R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {}) const
{
return (*this)(ranges::begin(r1), ranges::end(r1),
ranges::begin(r2), ranges::end(r2),
std::move(pred),
std::move(proj1), std::move(proj2));
}
};
inline constexpr find_end_fn find_end {};
Notes
An implementation can improve efficiency of the search if the input iterators model std::bidirectional_iterator
by searching from the end towards the begin.
Modelling the std::random_access_iterator
may improve the comparison speed.
All this however does not change the theoretical complexity of the worst case.
Examples
#include <algorithm>
#include <array>
#include <cctype>
#include <iostream>
#include <ranges>
#include <string_view>
void print(const auto haystack, const auto needle)
{
const auto pos = std::distance(haystack.begin(), needle.begin());
std::cout << "In \"";
for (const auto c : haystack) { std::cout << c; }
std::cout << "\" found \"";
for (const auto c : needle) { std::cout << c; }
std::cout << "\" at position [" << pos << ".." << pos + needle.size() << ")\n"
<< std::string(4 + pos, ' ') << std::string(needle.size(), '^') << '\n';
}
int main()
{
using namespace std::literals;
constexpr auto secret{"password password word..."sv};
constexpr auto wanted{"password"sv};
constexpr auto found1 = std::ranges::find_end(
secret.cbegin(), secret.cend(), wanted.cbegin(), wanted.cend());
print(secret, found1);
constexpr auto found2 = std::ranges::find_end(secret, "word"sv);
print(secret, found2);
const auto found3 = std::ranges::find_end(secret, "ORD"sv,
[](const char x, const char y) { // uses a binary predicate
return std::tolower(x) == std::tolower(y);
});
print(secret, found3);
const auto found4 = std::ranges::find_end(secret, "SWORD"sv, {}, {},
[](char c) { return std::tolower(c); }); // projects the 2nd range
print(secret, found4);
static_assert(std::ranges::find_end(secret, "PASS"sv).empty()); // => not found
}
In "password password word..." found "password" at position [9..17)
^^^^^^^^
In "password password word..." found "word" at position [18..22)
^^^^
In "password password word..." found "ord" at position [19..22)
^^^
In "password password word..." found "sword" at position [12..17)
^^^^^
Hover to see the original license.