std::ranges::find_end() 算法
- 自 C++20 起
- 简化
- 详细
// (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 = {} );
参数类型是泛型的，并具有以下约束
I1,I2-std::forward_iteratorS1,S2-std::sentinel_for<I1>,std::sentinel_for<I2>Pred- (无)Proj1,Proj2- (无)- (2) -
R1,R2-std::ranges::forward_range
Proj1 和 Proj2 模板参数对于所有重载都具有默认类型 std::identity。
此外，每个重载都有以下约束
- (1) -
indirectly_comparable<I1, I2, Pred, Proj1, Proj2> - (2) -
indirectly_comparable<ranges::iterator_t<R1>, ranges::iterator_t<R2>, Pred, Proj1, Proj2>
（为方便阅读，此处省略了 std:: 命名空间）
// (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 = {} );
在范围内搜索序列的最后一次出现。
-
(1) 在范围 [
first1;last1) 中搜索序列 [first2;last2) 的最后一次出现，分别通过proj1和proj2进行投影。投影的元素使用二元谓词pred进行比较。 -
(2) 与 (1) 相同，但使用
r1作为第一个源范围，r2作为第二个源范围，如同使用ranges::begin(r1)作为first1，ranges::end(r1)作为last1，ranges::begin(r2)作为first2，以及ranges::end(r2)作为last2。
本页描述的函数类实体是niebloids。
参数
first1 last1 | 要检查的元素范围。 |
first2 last2 | 要搜索的元素范围。 |
r1 | 要检查的元素范围。 |
r2 | 要搜索的元素范围。 |
pred | 用于比较元素的二元谓词。 |
proj1 | 应用于第一个范围中元素的投影。 |
proj2 | 应用于第二个范围中元素的投影。 |
返回值
-
(1) 类型为
ranges::subrange<I1>的值，初始化如下：{
i,
i + (i == last1 ? 0 : ranges::distance(first2, last2))
}表示序列 [
first2;last2) 在范围 [first1;last1) 中（通过proj1和proj2投影后）的最后一次出现。如果 [
first2;last2) 为空或未找到此类序列，则返回值实际上使用{ last1, last1 }初始化。 -
(2) 与 (1) 相同，但返回类型为
ranges::borrowed_subrange_t<R1>。
复杂度
- (1) 给定
S为ranges::distance(first2, last2)，N为ranges::distance(first1, last1) - (2) 给定
S为ranges::distance(r2)，N为ranges::distance(r1)
最多应用谓词和每个投影 S * (N - S + 1) 次。
异常
(无)
可能的实现
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 {};
备注
如果输入迭代器模型为 std::bidirectional_iterator，则通过从末尾向开头搜索，可以提高搜索效率。建模 std::random_access_iterator 可以提高比较速度。
然而，所有这些都不会改变最坏情况的理论复杂性。
示例
Main.cpp
#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)
^^^^^