std::ranges::search_n
来自cppreference.com
定义于头文件 <algorithm>
|
||
调用签名 |
||
template< std::forward_iterator I, std::sentinel_for<I> S, class T, class Pred = ranges::equal_to, class Proj = std::identity > |
(1) | (C++20 起) |
template< ranges::forward_range R, class T, class Pred = ranges::equal_to, class Proj = std::identity > |
(2) | (C++20 起) |
1) 在范围
[first, last)
中搜索首个 count
元素的序列,其投影后的值按照二元谓词 pred
等于给定的值 value
。2) 同 (1) ,但以
r
为源范围,如同以 ranges::begin(r) 为 first
并以 ranges::end(r) 为 last
。此页面上描述的仿函数实体是 niebloid ,即:
实际上,它们能以函数对象,或以某些特殊编译器扩展实现。
参数
first, last | - | 要检验的元素范围(又称草堆) |
r | - | 要检验的元素范围(又称草堆) |
count | - | 要搜索的序列长度 |
value | - | 要搜索的值(又称针) |
pred | - | 比较投影后元素与 value 的二元谓词
|
proj | - | 应用到要检验的范围的元素的投影 |
返回值
1) 返回含有范围
[first, last)
中指代找到的序列的一对迭代器的 std::ranges::subrange 。
若找不到这种序列,则返回 std::ranges::subrange{last, last} 。
若 count ≤ 0 则返回 std::ranges::subrange{first, first} 。2) 同 (1) ,但返回类型为 ranges::borrowed_subrange_t<R> 。
复杂度
线性:至多应用 ranges::distance(first, last) 次谓词与投影。
注解
若迭代器实现 std::random_access_iterator 则实现可以提升平均搜索效率。
可能的实现
struct search_n_fn { template<std::forward_iterator I, std::sentinel_for<I> S, class T, class Pred = ranges::equal_to, class Proj = std::identity> requires std::indirectly_comparable<I, const T*, Pred, Proj> constexpr ranges::subrange<I> operator()(I first, S last, std::iter_difference_t<I> count, const T& value, Pred pred = {}, Proj proj = {}) const { if (count <= 0) return {first, first}; for (; first != last; ++first) { if (std::invoke(pred, std::invoke(proj, *first), value)) { I start = first; std::iter_difference_t<I> n{1}; for (;;) { if (n++ == count) return {start, std::next(first)}; // 找到 if (++first == last) return {first, first}; // 找不到 if (!std::invoke(pred, std::invoke(proj, *first), value)) break; // not equ to value } } } return {first, first}; } template<ranges::forward_range R, class T, class Pred = ranges::equal_to, class Proj = std::identity> requires std::indirectly_comparable<ranges::iterator_t<R>, const T*, Pred, Proj> constexpr ranges::borrowed_subrange_t<R> operator()(R&& r, ranges::range_difference_t<R> count, const T& value, Pred pred = {}, Proj proj = {}) const { return (*this)(ranges::begin(r), ranges::end(r), std::move(count), value, std::move(pred), std::move(proj)); } }; inline constexpr search_n_fn search_n{}; |
示例
运行此代码
#include <algorithm> #include <iomanip> #include <iostream> #include <string> int main() { static constexpr auto nums = {1, 2, 2, 3, 4, 1, 2, 2, 2, 1}; constexpr int count{ 3 }; constexpr int value{ 2 }; constexpr auto result1 = std::ranges::search_n( nums.begin(), nums.end(), count, value ); static_assert( // 找到 result1.size() == count && std::distance(nums.begin(), result1.begin()) == 6 && std::distance(nums.begin(), result1.end()) == 9 ); constexpr auto result2 = std::ranges::search_n(nums, count, value); static_assert( // 找到 result2.size() == count && std::distance(nums.begin(), result2.begin()) == 6 && std::distance(nums.begin(), result2.end()) == 9 ); constexpr auto result3 = std::ranges::search_n(nums, count, /* value */ 5); static_assert( // 找不到 result3.size() == 0 && result3.begin() == result3.end() && result3.end() == nums.end() ); constexpr auto result4 = std::ranges::search_n(nums, /* count */ 0, /* value */ 1); static_assert( // 找不到 result4.size() == 0 && result4.begin() == result4.end() && result4.end() == nums.begin() ); constexpr char symbol{'B'}; std::cout << std::boolalpha << "Find a sub-sequence: " << std::quoted(std::string(count, symbol)) << '\n'; auto result5 = std::ranges::search_n(nums, count, symbol, [](const char x, const char y) { // 二元谓词 const bool o{ x == y }; std::cout << "bin_op(" << x << ", " << y << ") == " << o << "\n"; return o; }, [](const int z) { return 'A' + z - 1; } // 投影数字 -> ASCII ); std::cout << "Found: " << !result5.empty() << '\n'; }
输出:
Find a sub-sequence: "BBB" bin_op(A, B) == false bin_op(B, B) == true bin_op(B, B) == true bin_op(C, B) == false bin_op(D, B) == false bin_op(A, B) == false bin_op(B, B) == true bin_op(B, B) == true bin_op(B, B) == true Found: true
参阅
(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) |
在范围中搜索一定量的某个元素的连续副本 (函数模板) |