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, ForwardIt first, ForwardIt last );	(2)	(C++17 起)
template<class ForwardIt, class BinaryPred > ForwardIt adjacent_find( ForwardIt first, ForwardIt last, BinaryPred p );	(3)	(C++20 起为 `constexpr`)
template<class ExecutionPolicy, class ForwardIt, class BinaryPred > ForwardIt adjacent_find( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, BinaryPred p );	(4)	(C++17 起)

在范围 [first, last) 中搜索两个连续的相等元素。

1) 用 operator== 比较元素。

3) 用给定的二元谓词 p 比较元素。

2,4) 同 (1,3)，但按照 policy 执行。

这些重载只有在满足以下所有条件时才会参与重载决议：

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 的）类型 `Type1` 与 `Type2` 的值，无关乎值类别（从而不允许 Type1 &，亦不允许 Type1 ，除非 `Type1` 的移动等价于复制(C++11 起)）。类型 Type1 与 Type2 必须使得 ForwardIt 类型的对象能在解引用后隐式转换到这两个类型。
类型要求
- `ForwardIt` 必须满足老式向前迭代器(LegacyForwardIterator) 。
- `BinaryPred` 必须满足二元谓词(BinaryPredicate) 。

[编辑]返回值

指向首对等同元素的首个元素的迭代器，即首个满足 *it ==*(it +1)（版本 (1,2)）或 p(*it, *(it +1))!=false（版本 (3,4)）的迭代器 it。

如果找不到这种元素，那么返回 last。

[编辑]复杂度

给定 result 为 adjacent_find 的返回值，$\scriptsize M$ $M$ 为 std::distance(first, result)，$\scriptsize N$ $N$ 为 std::distance(first, last)：

1) 应用

min(M+1,N-1)

次 operator== 进行比较。

2) 应用

O(N)

次 operator== 进行比较。

3) 应用

min(M+1,N-1)

次谓词 p。

4) 应用

O(N)

次谓词 p。

[编辑]异常

拥有名为 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<<"没有匹配的相邻元素\n";elsestd::cout<<"第一对相等的相邻元素位于 "<<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<<"整个 vector 已经是升序的\n";elsestd::cout<<"非降序子序列中最后的元素位于 "<<std::distance(v1.begin(), i2)<<"，*i2 = "<<*i2 <<'\n';}

输出：

第一对相等的相邻元素位于 4，*i1 = 40 非降序子序列中最后的元素位于 7，*i2 = 41

[编辑]缺陷报告

下列更改行为的缺陷报告追溯地应用于以前出版的 C++ 标准。

缺陷报告	应用于	出版时的行为	正确行为
LWG 240	C++98	(1,3) 中谓词会应用 std::find(first, last, value)- first 次，但 value 没有定义	应用 std::min((result - first) +1, (last - first)-1) 次

[编辑]参阅

unique	移除范围中连续重复元素 (函数模板)[编辑]
ranges::adjacent_find (C++20)	查找首对相同（或满足给定谓词）的相邻元素 (算法函数对象)[编辑]

编译器支持
自立实现与有宿主实现
语言
标准库
标准库标头
具名要求
功能特性测试宏(C++20)
语言支持库
概念库(C++20)
诊断库
内存管理库
元编程库(C++11)
通用工具库
容器库
迭代器库
范围库(C++20)
算法库
字符串库
文本处理库
数值库
日期和时间库
输入/输出库
文件系统库(C++17)
并发支持库(C++11)
执行控制库(C++26)
技术规范
符号索引
外部库

cppreference.com

名字空间

变换

查看

操作