命名空间
变体
操作

std::adjacent_find

来自 cppreference.com
< cpp‎ | algorithm
 
 
算法库
约束算法和范围上的算法 (C++20)
约束算法,例如 ranges::copy, ranges::sort, ...
执行策略 (C++17)
排序和相关操作
分区操作
排序操作
二分搜索操作
(在分区范围上)
集合操作(在排序范围上)
合并操作(在排序范围上)
堆操作
最小值/最大值操作
(C++11)
(C++17)
词典比较操作
排列操作
C 库
数值操作
未初始化内存上的操作
 
定义在头文件 <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 开始)

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

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)的 Type1Type2 的所有值,无论其 值类别 如何(因此,Type1 & 不允许Type1 也不允许,除非对于 Type1,移动等效于复制(从 C++11 开始))。
类型 Type1Type2 必须是能够将类型 ForwardIt 的对象解引用,然后隐式转换为这两者的类型。​

类型要求
-
ForwardIt 必须满足 LegacyForwardIterator 的要求。
-
BinaryPred 必须满足 BinaryPredicate 的要求。

[编辑] 返回值

指向第一对相同元素的第一项的迭代器,即第一个迭代器 it 使得 *it == *(it + 1) 对于 (1,2)p(*it, *(it + 1)) != false 对于 (3,4) 成立。

如果找不到这样的元素,则返回 last

[编辑] 复杂度

假设 resultadjacent_find 的返回值,Mstd::distance(first, result)Nstd::distance(first, last)

1) 使用 operator== 进行 min(M+1,N-1) 次比较。
2) 使用 operator== 进行 O(N) 次比较。
3) 对谓词 p 进行 min(M+1,N-1) 次调用。
4) 对谓词 p 进行 O(N) 次调用。

[编辑] 异常

具有名为 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)

[编辑] 另请参见

从范围内删除连续的重复元素
(函数模板) [编辑]
查找第一个相邻的两个相等项(或满足给定谓词的项)
(niebloid)[编辑]