std::adjacent_find

ヘッダ `<algorithm>`
template< class ForwardIt > ForwardIt adjacent_find( ForwardIt first, ForwardIt last );	で定義 (1)	(C++20 から constexpr)
template< class ForwardIt, class BinaryPred > ForwardIt adjacent_find( ForwardIt first, ForwardIt last, BinaryPred p );	(2)	(C++20 から constexpr)
template< class ExecutionPolicy, class ForwardIt > ForwardIt adjacent_find( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );	(3)	(C++17 から)
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== によって判定されます。

2) 指定された二項述語 p を満たす隣接要素の最初のペアを検索します。

3,4) (1,2) と同じですが、policy に従って実行されます。

これらのオーバーロードは、以下の式の値が true である場合にのみオーバーロード解決に参加します:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(C++20 まで)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(C++20 から)

パラメータ

first, last	-	ソース範囲を定義するイテレータのペア範囲
p	-	二項述語。要素が等しいと扱われるべき場合に`true` を返します。述語関数のシグネチャは以下と同等であるべきです。 `bool pred(const Type1 &a, const Type2 &b);` シグネチャは `const &` を持つ必要はありませんが、関数は渡されたオブジェクトを変更してはならず、型 (const 付きも可) `Type1` および `Type2` のすべての値を、値カテゴリに関わらず受け入れられなければなりません（したがって、`Type1 &` は許可されず、`Type1` も、`Type1` の場合を除き許可されません。移動がコピーと同等である場合に限ります(C++11以降)）。型 `Type1` および `Type2` は、`ForwardIt` 型のオブジェクトがデリファレンスされ、その後暗黙的に両方に変換可能であるようにしなければなりません。
policy	-	使用する実行ポリシー
型要件
- `ForwardIt`は LegacyForwardIterator の要件を満たさなければなりません。
- `BinaryPred`は BinaryPredicate の要件を満たさなければなりません。

戻り値

最初のイテレータiter ソース範囲内で以下の式が真と評価される true:

1,3) bool(*iter == *std::next(iter))

2,4) bool(p(*iter, std::next(iter))

そのようなイテレータが見つからない場合は、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) 正確に

min(M+1,N-1)

回の述語pの適用。

3)

𝓞(N)

回の比較（operator==を使用）。

4)

𝓞(N)

回の述語pの適用。

例外

3,4) 実行プロセス中:

並列化に必要な一時メモリリソースが利用できない場合、std::bad_alloc がスローされます。
アルゴリズム引数を介してオブジェクトにアクセス中にキャッチされない例外がスローされた場合、動作は実行ポリシーによって決まります（標準ポリシーの場合、std::terminate が呼び出されます）。

可能な実装

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 (2)

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	複雑性の要件が不明確だった	明確化された

コンパイラサポート
フリースタンディングとホスト環境
言語
標準ライブラリ
標準ライブラリヘッダ
名前付き要件
機能テストマクロ (C++20)
言語サポートライブラリ
コンセプトライブラリ (C++20)
診断ライブラリ
メモリ管理ライブラリ
メタプログラミングライブラリ (C++11)
汎用ユーティリティライブラリ
コンテナライブラリ
イテレータライブラリ
レンジライブラリ (C++20)
アルゴリズムライブラリ
文字列ライブラリ
テキスト処理ライブラリ
数値ライブラリ
日付と時間ライブラリ
入出力ライブラリ
ファイルシステムライブラリ (C++17)
並行処理サポートライブラリ (C++11)
実行制御ライブラリ (C++26)
技術仕様書
シンボル索引
外部ライブラリ

ranges::adjacent_find (C++20)	最初に隣接する等値（または指定された述語を満たす）2つの要素を検索する（アルゴリズム関数オブジェクト）
unique	範囲内の連続した重複要素を削除する（関数テンプレート & アルゴリズム関数オブジェクト）
ranges::unique (C++20)	範囲内の連続した重複要素を削除する（関数テンプレート & アルゴリズム関数オブジェクト）

ja.cppreference.net

Namespaces

Variants

std::adjacent_find

目次

パラメータ

戻り値

計算量

例外

可能な実装

例

欠陥報告

関連項目