std::adjacent_find
定义在头文件 <algorithm> 中 |
||
template< class ForwardIt > ForwardIt adjacent_find( ForwardIt first, ForwardIt last ); |
(1) | (从 C++20 开始为 constexpr) |
template< class ExecutionPolicy, class ForwardIt > ForwardIt adjacent_find( ExecutionPolicy&& policy, |
(2) | (从 C++17 开始) |
template< class ForwardIt, class BinaryPred > ForwardIt adjacent_find( ForwardIt first, ForwardIt last, |
(3) | (从 C++20 开始为 constexpr) |
template< class ExecutionPolicy, class ForwardIt, class BinaryPred > ForwardIt adjacent_find( ExecutionPolicy&& policy, |
(4) | (从 C++17 开始) |
在范围 [
first,
last)
中搜索两个连续相等的元素。
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 | - | 要检查的元素范围 |
policy | - | 要使用的执行策略。有关详细信息,请参见 执行策略。 |
p | - | 二元谓词,如果元素应被视为相等,则返回 true。 谓词函数的签名应等效于以下内容 bool pred(const Type1 &a, const Type2 &b); 虽然签名不需要具有 const &,但该函数不得修改传递给它的对象,并且必须能够接受类型(可能是 const)的 |
类型要求 | ||
-ForwardIt 必须满足 LegacyForwardIterator 的要求。 | ||
-BinaryPred 必须满足 BinaryPredicate 的要求。 |
[编辑] 返回值
指向第一对相同元素的第一项的迭代器,即第一个迭代器 it 使得 *it == *(it + 1) 对于 (1,2) 或 p(*it, *(it + 1)) != false 对于 (3,4) 成立。
如果找不到这样的元素,则返回 last。
[编辑] 复杂度
假设 result 是 adjacent_find
的返回值,M 为 std::distance(first, result),N 为 std::distance(first, last)
[编辑] 异常
具有名为 ExecutionPolicy
的模板参数的重载函数报告错误如下:
- 如果作为算法一部分调用的函数执行时抛出异常,并且
ExecutionPolicy
是 标准策略 之一,则调用 std::terminate。对于任何其他ExecutionPolicy
,行为由实现定义。 - 如果算法无法分配内存,则抛出 std::bad_alloc。
[编辑] 可能的实现
adjacent_find (1) |
---|
template<class ForwardIt> ForwardIt adjacent_find(ForwardIt first, ForwardIt last) { if (first == last) return last; ForwardIt next = first; ++next; for (; next != last; ++next, ++first) if (*first == *next) return first; return last; } |
adjacent_find (3) |
template<class ForwardIt, class BinaryPred> ForwardIt adjacent_find(ForwardIt first, ForwardIt last, BinaryPred p) { if (first == last) return last; ForwardIt next = first; ++next; for (; next != last; ++next, ++first) if (p(*first, *next)) return first; return last; } |
[编辑] 示例
#include <algorithm> #include <functional> #include <iostream> #include <vector> int main() { std::vector<int> v1{0, 1, 2, 3, 40, 40, 41, 41, 5}; auto i1 = std::adjacent_find(v1.begin(), v1.end()); if (i1 == v1.end()) std::cout << "No matching adjacent elements\n"; else std::cout << "The first adjacent pair of equal elements is at " << std::distance(v1.begin(), i1) << ", *i1 = " << *i1 << '\n'; auto i2 = std::adjacent_find(v1.begin(), v1.end(), std::greater<int>()); if (i2 == v1.end()) std::cout << "The entire vector is sorted in ascending order\n"; else std::cout << "The last element in the non-decreasing subsequence is at " << std::distance(v1.begin(), i2) << ", *i2 = " << *i2 << '\n'; }
输出
The first adjacent pair of equal elements is at 4, *i1 = 40 The last element in the non-decreasing subsequence is at 7, *i2 = 41
[编辑] 缺陷报告
以下行为更改缺陷报告被追溯应用于之前发布的 C++ 标准。
DR | 应用于 | 已发布的行为 | 正确的行为 |
---|---|---|---|
LWG 240 | C++98 | 谓词被应用 std::find (first, last, value) - first 次 对于 (1,3),其中 value 从未定义 |
应用 std::min( (result - first) + 1, (last - first) - 1) 次 |
[编辑] 另请参见
从范围内删除连续的重复元素 (函数模板) | |
(C++20) |
查找第一个相邻的两个相等项(或满足给定谓词的项) (niebloid) |