std::ranges:: search
|
定义于头文件
<algorithm>
|
||
|
调用签名
|
||
|
template
<
std::
forward_iterator
I1,
std::
sentinel_for
<
I1
>
S1,
std::
forward_iterator
I2,
std::
sentinel_for
<
I2
>
S2,
|
(1) | (C++20 起) |
|
template
<
ranges::
forward_range
R1,
ranges::
forward_range
R2,
class
Pred
=
ranges::
equal_to
,
|
(2) | (C++20 起) |
[
first1
,
last1
)
中搜索元素序列
[
first2
,
last2
)
的
首个
出现位置。元素分别通过投影器
proj2
和
proj1
处理后，使用二元谓词
pred
进行比较。
本页面描述的函数式实体是 算法函数对象 （非正式称为 niebloids ），即：
目录 |
参数
| first1, last1 | - | 定义待检查元素范围的迭代器-哨位对（称为 haystack ） |
| first2, last2 | - | 定义待查找元素范围的迭代器-哨位对（称为 needle ） |
| r1 | - | 待检查的元素范围（称为 haystack ） |
| r2 | - | 待查找的元素范围（称为 needle ） |
| pred | - | 应用于投影元素的二元谓词 |
| proj1 | - | 应用于第一个范围元素的投影 |
| proj2 | - | 应用于第二个范围元素的投影 |
返回值
[
first2
,
last2
)
（称为
needle
）在范围
[
first1
,
last1
)
（称为
haystack
）中的首次出现位置，其中已分别对两个序列的元素应用投影
proj1
和
proj2
，并随后应用二元谓词
pred
来比较投影后的元素。
如果未找到该序列，则返回 ranges:: subrange { last1, last1 } 。
如果要搜索的范围（称为 needle ）为空，即 first2 == last2 ，则返回 ranges:: subrange { first1, first1 } 。复杂度
最多进行
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); // 'needle' 范围为空： constexpr auto none {""sv}; constexpr auto found3 = std::ranges::search(haystack, none); print(3, haystack, none, found3); // 'needle' 将不会被找到： 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)
|
在范围内搜索首个连续出现指定次数的元素
(算法函数对象) |
|
搜索元素范围的首次出现
(函数模板) |