std::ranges::find_end
来自cppreference.com
| 在标头 <algorithm> 定义
|
||
| 调用签名 |
||
| |
(1) | (C++20 起) |
| |
(2) | (C++20 起) |
1) 搜索序列
[first2, last2) 在范围 [first1, last1) 中的最后出现，在分别以proj1 与 proj2 投影后。用二元谓词 pred 比较投影后的元素。2) 同 (1)，但以
r1 为第一源范围并以 r2 为第二源范围，如同以 ranges::begin(r1) 为 first1，以 ranges::end(r1) 为 last1，ranges::begin(r2) 为 first2，并以 ranges::end(r2) 为 last2。此页面上描述的函数式实体是算法函数对象（非正式地称为 niebloid），即：
参数
| first1, last1 | - | 要检验的（又称草堆）元素范围的迭代器-哨位对 |
| first2, last2 | - | 要搜索的（又称针）元素范围的迭代器-哨位对 |
| r1 | - | 要检验的元素范围（又称草堆） |
| r2 | - | 要搜索的元素范围（又称针） |
| pred | - | 比较元素的二元谓词 |
| proj1 | - | 应用到第一范围中元素的投影 |
| proj2 | - | 应用到第二范围中元素的投影 |
返回值
1) 以表达式
{i, i + (i == last1 ? 0 : last2 - first2)} 初始化的 ranges::subrange<I1>{} 值，该范围代表序列 [first2, last2) 在范围 [first1, last1) 中的最后一次出现（在以 proj1 与 proj2 投影后）。若 [first2, last2) 为空或找不到该序列，则等效地以 {last1, last1} 初始化返回值。2) 同 (1)，但返回类型为
ranges::borrowed_subrange_t<R1>。复杂度
至多应用 S·(N-S+1) 次谓词和对应的每次投影，其中对于 (1) S 为 ranges::distance(first2, last2) 而 N 为 ranges::distance(first1, last1)，或对于 (2) S 为 ranges::distance(r2) 而 N 为 ranges::distance(r1)。
注解
若输入迭代器构成 std::bidirectional_iterator，则实现可以通过从末尾到起始搜索改进效率。实现 std::random_access_iterator 可能提升比较速度。然而所有这些不改变最坏情况的理论复杂度。
可能的实现
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 {};
|
示例
运行此代码
#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) { // 用二元谓词
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); }); // 投影第二范围
print(secret, found4);
static_assert(std::ranges::find_end(secret, "PASS"sv).empty()); // => 找不到
}
输出：
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)
^^^^^
参阅
(C++23)(C++23)(C++23) |
查找最后一个满足特定条件的元素 (算法函数对象) |
(C++20)(C++20)(C++20) |
查找首个满足特定条件的元素 (算法函数对象) |
(C++20) |
搜索一组元素中任一元素 (算法函数对象) |
(C++20) |
查找首对相同（或满足给定谓词）的相邻元素 (算法函数对象) |
(C++20) |
搜索元素范围的首次出现 (算法函数对象) |
(C++20) |
搜索元素在范围中首次连续若干次出现 (算法函数对象) |
| 查找元素序列在特定范围中最后一次出现 (函数模板) |
