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)
的首次出现。在分别用 proj1
与 proj2
投影后用二元谓词 pred
比较元素。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 | - | 应用到第二范围中元素的投影 |
返回值
[first2, last2)
(又称针),在分别应用 proj1
与 proj2
到两个序列的元素,再应用二元谓词 pred
比较投影后元素之后,于范围 [first1, last1)
(又称草堆)中首次出现的 ranges::subrange 值。
若找不到这种序列,则返回 ranges::subrange{last1, last1} 。
若待搜索范围(又称针)为空,即 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); // ‘针’范围为空: 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) |
查找首对相邻的相同(或满足给定谓词的)元素 (niebloid) |
(C++20)(C++20)(C++20) |
寻找首个满足特定判别标准的元素 (niebloid) |
(C++20) |
在特定范围中寻找最后出现的元素序列 (niebloid) |
(C++20) |
搜索元素集合中的任一元素 (niebloid) |
(C++20) |
若一个序列是另一个的子列则返回 true (niebloid) |
(C++20) |
寻找两个范围出现不同的首个位置 (niebloid) |
(C++20) |
在范围中搜索一定量的某个元素的连续副本 (niebloid) |
搜索一个元素范围 (函数模板) |