std::ranges::search
来自cppreference.com
| 在标头 <algorithm> 定义
|
||
| 调用签名 |
||
| |
(1) | (C++20 起) |
| |
(2) | (C++20 起) |
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。此页面上描述的函数式实体是算法函数对象（非正式地称为 niebloid），即：
参数
| first1, last1 | - | 要检验的（又称草堆）元素范围的迭代器对 |
| first2, last2 | - | 要搜索的（又称针）元素范围的迭代器对 |
| r1 | - | 要检验的元素范围（又称草堆） |
| r2 | - | 要搜索的元素范围（又称针） |
| pred | - | 应用到投影后元素的谓词 |
| proj1 | - | 应用到第一范围中元素的投影 |
| proj2 | - | 应用到第二范围中元素的投影 |
返回值
1) 返回作为序列
[first2, last2)（又称针），在分别应用 proj1 与 proj2 到两个序列的元素，再应用二元谓词 pred 比较投影后元素之后，于范围 [first1, last1)（又称草堆）中首次出现的 ranges::subrange 值。
若找不到这种序列，则返回 ranges::subrange{last1, last1}。
first2 == last2 ，则返回 ranges::subrange{first1, first1}。2) 同 (1)，但返回类型为
ranges::borrowed_subrange_t<R1>。复杂度
至多应用 S*N 次对应的谓词和各自的投影，其中
(1) S = ranges::distance(first2, last2) 而 N = ranges::distance(first1, last1)；
(2) S = ranges::distance(r2) 而 N = ranges::distance(r1)。
可能的实现
struct search_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
{
for (;; ++first1)
{
I1 it1 = first1;
for (I2 it2 = first2;; ++it1, ++it2)
{
if (it2 == last2)
return {first1, it1};
if (it1 == last1)
return {it1, it1};
if (!std::invoke(pred, std::invoke(proj1, *it1), std::invoke(proj2, *it2)))
break;
}
}
}
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 search_fn search {};
|
示例
运行此代码
#include <algorithm>
#include <cctype>
#include <iostream>
#include <iterator>
#include <string_view>
using namespace std::literals;
void print(int id, const auto& haystack, const auto& needle, const auto& found)
{
std::cout << id << ") search(\"" << haystack << "\", \"" << needle << "\"); ";
const auto first = std::distance(haystack.begin(), found.begin());
const auto last = std::distance(haystack.begin(), found.end());
if (found.empty())
std::cout << "not found;";
else
{
std::cout << "found: \"";
for (const auto x : found)
std::cout << x;
std::cout << "\";";
}
std::cout << " subrange: {" << first << ", " << last << "}\n";
}
int main()
{
constexpr auto haystack {"abcd abcd"sv};
constexpr auto needle {"bcd"sv};
// 搜索使用迭代器对 begin()/end()：
constexpr auto found1 = std::ranges::search(
haystack.begin(), haystack.end(),
needle.begin(), needle.end());
print(1, haystack, needle, found1);
// 搜索使用范围 r1、 r2：
constexpr auto found2 = std::ranges::search(haystack, needle);
print(2, haystack, needle, found2);
// ‘针’范围为空：
constexpr auto none {""sv};
constexpr auto found3 = std::ranges::search(haystack, none);
print(3, haystack, none, found3);
// 不会找到‘针’范围：
constexpr auto awl {"efg"sv};
constexpr auto found4 = std::ranges::search(haystack, awl);
print(4, haystack, awl, found4);
// 搜索使用定制比较器与投影：
constexpr auto bodkin {"234"sv};
auto found5 = std::ranges::search(haystack, bodkin,
[](const int x, const int y) { return x == y; }, // pred
[](const int x) { return std::toupper(x); }, // proj1
[](const int y) { return y + 'A' - '1'; } // proj2
);
print(5, haystack, bodkin, found5);
}
输出：
1). search("abcd abcd", "bcd"); found: "bcd"; subrange: {1, 4}
2). search("abcd abcd", "bcd"); found: "bcd"; subrange: {1, 4}
3). search("abcd abcd", ""); not found; subrange: {0, 0}
4). search("abcd abcd", "efg"); not found; subrange: {9, 9}
5). search("abcd abcd", "234"); found: "bcd"; subrange: {1, 4}
参阅
(C++20) |
查找首对相同（或满足给定谓词）的相邻元素 (算法函数对象) |
(C++20)(C++20)(C++20) |
查找首个满足特定条件的元素 (算法函数对象) |
(C++20) |
查找元素序列在特定范围中最后一次出现 (算法函数对象) |
(C++20) |
搜索一组元素中任一元素 (算法函数对象) |
(C++23)(C++23) |
检查范围是否包含给定元素或子范围 (算法函数对象) |
(C++20) |
当一个序列是另一个的子序列时返回 true (算法函数对象) |
(C++20) |
查找两个范围的首个不同之处 (算法函数对象) |
(C++20) |
搜索元素在范围中首次连续若干次出现 (算法函数对象) |
| 搜索元素范围的首次出现 (函数模板) |
