|
|
|
|
调用签名
|
|
|
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 = {} );
|
(1) |
(C++20 起) |
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 = {} );
|
(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> 。
复杂度
至多应用 \(\scriptsize S\cdot(N-S+1)\)S·(N-S+1) 次谓词和对应的每次投影，其中对于
(1) \(\scriptsize
S\)S 为 ranges::distance(first2, last2) 而 \(\scriptsize N\)N 为 ranges::distance(first1, last1) ，或对于 (2) \(\scriptsize S\)S 为 ranges::distance(r2) 而 \(\scriptsize N\)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)
^^^^^
参阅
|
|
在特定范围中寻找最后出现的元素序列
(函数模板) |
|
|
查找首对相邻的相同（或满足给定谓词的）元素
(niebloid) |
|
|
查找满足特定条件的的第一个元素
(niebloid) |
|
|
查找元素集合中的任一元素
(niebloid) |
|
|
搜索一个元素范围
(niebloid) |
|
|
在范围中搜索一定量的某个元素的连续副本
(niebloid) |