std::ranges::search_n
在标头 <algorithm> 定义 | ||
调用签名 | ||
| (1) | ||
template<std::forward_iterator I, std::sentinel_for<I> S, class T, class Pred =ranges::equal_to, class Proj =std::identity> | (C++20 起) (C++26 前) | |
template<std::forward_iterator I, std::sentinel_for<I> S, class Pred =ranges::equal_to, class Proj =std::identity, | (C++26 起) | |
| (2) | ||
template<ranges::forward_range R, class T, class Pred =ranges::equal_to, class Proj =std::identity> | (C++20 起) (C++26 前) | |
template<ranges::forward_range R, class Pred =ranges::equal_to, class Proj =std::identity, | (C++26 起) | |
[first, last) 中搜索首个 count 个元素的连续序列，其投影后的值按照二元谓词 pred 均等于给定的值 value。此页面上描述的函数式实体是算法函数对象（非正式地称为 niebloid），即：
目录 |
[编辑]参数
| first, last | - | 要检验的（又称草堆）元素范围的迭代器-哨位对 |
| r | - | 要检验的元素范围（又称草堆） |
| count | - | 要搜索的序列长度 |
| value | - | 要搜索的值（又称针） |
| pred | - | 比较投影后元素与 value 的二元谓词 |
| proj | - | 应用到要检验的范围的元素的投影 |
[编辑]返回值
[first, last) 中指代找到的序列的一对迭代器的 std::ranges::subrange。 若找不到这种序列，则返回 std::ranges::subrange{last, last}。
若 count ≤ 0 则返回 std::ranges::subrange{first, first}。[编辑]复杂度
线性：至多应用 ranges::distance(first, last) 次谓词与投影。
[编辑]注解
若迭代器实现了 std::random_access_iterator 则实现可以提升平均搜索效率。
| 功能特性测试宏 | 值 | 标准 | 功能特性 |
|---|---|---|---|
__cpp_lib_algorithm_default_value_type | 202403 | (C++26) | 算法中的列表初始化 |
[编辑]可能的实现
struct search_n_fn {template<std::forward_iterator I, std::sentinel_for<I> S, class Pred =ranges::equal_to, class Proj =std::identity, class T = std::projected_value_t<I, Proj>> requires std::indirectly_comparable<I, const T*, Pred, Proj>constexprranges::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;// 不等于 value}}return{first, first};} template<ranges::forward_range R, class Pred =ranges::equal_to, class Proj =std::identity, class T = std::projected_value_t<ranges::iterator_t<R>, Proj>> requires std::indirectly_comparable<ranges::iterator_t<R>, const T*, Pred, Proj>constexprranges::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));}}; inlineconstexpr search_n_fn search_n {}; |
[编辑]示例
#include <algorithm>#include <cassert>#include <complex>#include <iomanip>#include <iostream>#include <iterator>#include <string>#include <vector> int main(){namespace ranges = std::ranges; staticconstexprauto nums ={1, 2, 2, 3, 4, 1, 2, 2, 2, 1};constexprint count{3};constexprint value{2};typedefint count_t, value_t; constexprauto result1 = 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); constexprauto result2 = 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); constexprauto result3 = ranges::search_n(nums, count, value_t{5}); static_assert // 找不到( result3.size()==0&& result3.begin()== result3.end()&& result3.end()== nums.end()); constexprauto result4 = ranges::search_n(nums, count_t{0}, value_t{1}); static_assert // 找不到( result4.size()==0&& result4.begin()== result4.end()&& result4.end()== nums.begin()); constexprchar symbol{'B'};auto to_ascii =[](constint z)->char{return'A'+ z -1;};auto is_equ =[](constchar x, constchar y){return x == y;}; std::cout<<"找到了子序列 "<<std::string(count, symbol)<<" 于 "; std::ranges::transform(nums, std::ostream_iterator<char>(std::cout, ""), to_ascii);std::cout<<'\n'; auto result5 = ranges::search_n(nums, count, symbol, is_equ, to_ascii);if(not result5.empty())std::cout<<"找到其位置在 "<<ranges::distance(nums.begin(), result5.begin())<<'\n'; std::vector<std::complex<double>> nums2{{4, 2}, {4, 2}, {1, 3}};#ifdef __cpp_lib_algorithm_default_value_typeauto it = ranges::search_n(nums2, 2, {4, 2});#elseauto it = ranges::search_n(nums2, 2, std::complex<double>{4, 2});#endifassert(it.size()==2);}
输出：
找到了子序列 BBB 于 ABBCDABBBA 找到其位置在 6
[编辑]参阅
(C++20) | 查找首对相同（或满足给定谓词）的相邻元素 (算法函数对象) |
(C++20)(C++20)(C++20) | 查找首个满足特定条件的元素 (算法函数对象) |
(C++20) | 查找元素序列在特定范围中最后一次出现 (算法函数对象) |
(C++20) | 搜索一组元素中任一元素 (算法函数对象) |
(C++20) | 当一个序列是另一个的子序列时返回 true (算法函数对象) |
(C++20) | 查找两个范围的首个不同之处 (算法函数对象) |
(C++20) | 搜索元素范围的首次出现 (算法函数对象) |
| 搜索元素在范围中首次连续若干次出现 (函数模板) |
