std::search_n
定义在头文件 <algorithm> 中 |
||
(1) | ||
template< class ForwardIt, class Size, class T > ForwardIt search_n( ForwardIt first, ForwardIt last, |
(自 C++20 起为 constexpr) (直到 C++26) |
|
template< class ForwardIt, class Size, class T = typename std::iterator_traits |
(自 C++26 起) | |
(2) | ||
template< class ExecutionPolicy, class ForwardIt, class Size, class T > |
(自 C++17 起) (直到 C++26) |
|
template< class ExecutionPolicy, class ForwardIt, class Size, |
(自 C++26 起) | |
(3) | ||
template< class ForwardIt, class Size, class T, class BinaryPred > ForwardIt search_n( ForwardIt first, ForwardIt last, |
(自 C++20 起为 constexpr) (直到 C++26) |
|
template< class ForwardIt, class Size, class T = typename std::iterator_traits |
(自 C++26 起) | |
(4) | ||
template< class ExecutionPolicy, class ForwardIt, class Size, class T, class BinaryPred > |
(自 C++17 起) (直到 C++26) |
|
template< class ExecutionPolicy, class ForwardIt, class Size, class T = typename std::iterator_traits |
(自 C++26 起) | |
在范围 [
first,
last)
中搜索第一个包含 count 个相同元素的序列,每个元素都等于给定的 value。
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> 为 true 时,这些重载才参与重载解析。 |
(直到 C++20) |
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> 为 true 时。 |
(自 C++20 起) |
内容 |
[编辑] 参数
first, last | - | 要检查的元素范围 |
count | - | 要搜索的序列的长度 |
value | - | 要搜索的元素的值 |
policy | - | 要使用的执行策略。有关详细信息,请参见 执行策略。 |
p | - | 二元谓词,如果元素应被视为相等,则返回 true。 谓词函数的签名应等效于以下内容 bool pred(const Type1 &a, const Type2 &b); 虽然签名不需要有 const &,但该函数不得修改传递给它的对象,并且必须能够接受类型(可能为 const) |
类型要求 | ||
-ForwardIt 必须满足 LegacyForwardIterator 的要求。 | ||
-BinaryPred 必须满足 BinaryPredicate 的要求。 | ||
-Size 必须可以 隐式转换为 整型。 |
[编辑] 返回值
如果 count 为正,则返回指向在范围 [
first,
last)
中找到的第一个序列开头的迭代器。序列中的每个迭代器 it 应满足以下条件
如果未找到这样的序列,则返回 last。
如果 count 为零或负数,则返回 first。
[编辑] 复杂度
给定 N 作为 std::distance(first, last)
[编辑] 异常
具有名为 ExecutionPolicy
的模板参数的重载报告错误如下
- 如果作为算法的一部分调用的函数的执行引发异常,并且
ExecutionPolicy
是 标准策略 之一,则调用 std::terminate。对于任何其他ExecutionPolicy
,行为是实现定义的。 - 如果算法无法分配内存,则会引发 std::bad_alloc。
[编辑] 可能的实现
search_n (1) |
---|
template<class ForwardIt, class Size, class T = typename std::iterator_traits<ForwardIt>::value_type> ForwardIt search_n(ForwardIt first, ForwardIt last, Size count, const T& value) { if (count <= 0) return first; for (; first != last; ++first) { if (!(*first == value)) continue; ForwardIt candidate = first; for (Size cur_count = 1; true; ++cur_count) { if (cur_count >= count) return candidate; // success ++first; if (first == last) return last; // exhausted the list if (!(*first == value)) break; // too few in a row } } return last; } |
search_n (3) |
template<class ForwardIt, class Size, class T = typename std::iterator_traits<ForwardIt>::value_type, class BinaryPred> ForwardIt search_n(ForwardIt first, ForwardIt last, Size count, const T& value, BinaryPred p) { if (count <= 0) return first; for (; first != last; ++first) { if (!p(*first, value)) continue; ForwardIt candidate = first; for (Size cur_count = 1; true; ++cur_count) { if (cur_count >= count) return candidate; // success ++first; if (first == last) return last; // exhausted the list if (!p(*first, value)) break; // too few in a row } } return last; } |
[编辑] 说明
功能测试 宏 | 值 | Std | 功能 |
---|---|---|---|
__cpp_lib_algorithm_default_value_type |
202403 | (C++26) | 算法的 列表初始化 (1-4) |
[编辑] 示例
#include <algorithm> #include <cassert> #include <complex> #include <iostream> #include <iterator> #include <vector> template<class Container, class Size, class T> constexpr bool consecutive_values(const Container& c, Size count, const T& v) { return std::search_n(std::begin(c), std::end(c), count, v) != std::end(c); } int main() { constexpr char sequence[] = ".0_0.000.0_0."; static_assert(consecutive_values(sequence, 3, '0')); for (int n : {4, 3, 2}) std::cout << std::boolalpha << "Has " << n << " consecutive zeros: " << consecutive_values(sequence, n, '0') << '\n'; std::vector<std::complex<double>> nums{{4, 2}, {4, 2}, {1, 3}}; #ifdef __cpp_lib_algorithm_default_value_type auto it = std::search_n(nums.cbegin(), nums.cend(), 2, {4, 2}); #else auto it = std::search_n(nums.cbegin(), nums.cend(), 2, std::complex<double>{4, 2}); #endif assert(it == nums.begin()); }
输出
Has 4 consecutive zeros: false Has 3 consecutive zeros: true Has 2 consecutive zeros: true
[编辑] 缺陷报告
以下行为变更缺陷报告被追溯应用于先前发布的 C++ 标准。
DR | 应用于 | 发布的行为 | 正确行为 |
---|---|---|---|
LWG 283 | C++98 | T 要求是 EqualityComparable,但InputIt 的值类型并不总是 T |
删除了该要求 |
LWG 426 | C++98 | 复杂度上限为 N·count ,如果 count 为负,则为负 |
上限为 0 如果 count 非正 |
LWG 714 | C++98 | 如果 count > 0,则复杂度上限为 N·count ,但在最坏情况下,比较/操作次数始终为 N |
更改了上限 在这种情况下将其限制为 N |
LWG 2150 | C++98 | “序列出现”的条件不正确 | 更正 |
[编辑] 另请参见
在某个范围内查找最后一个元素序列 (函数模板) | |
(C++11) |
查找满足特定条件的第一个元素 (函数模板) |
搜索一系列元素的首次出现 (函数模板) | |
(C++20) |
在范围内搜索一个元素的连续副本的第一次出现 (niebloid) |