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) 内で、隣接する2つの等しい要素を検索します。

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 の要件を満たす必要がある。

[edit] 戻り値

最初に見つかった同一要素のペアの最初の要素へのイテレータ。すなわち、(1,2) の場合は *it == *(it + 1)、(3,4) の場合は p(*it, *(it + 1)) != false となる最初のイテレータ it です。

そのような要素が見つからない場合は、last が返されます。

[edit] 計算量

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 の適用。

[edit] 例外

ExecutionPolicy というテンプレートパラメータを持つオーバーロードは、次のようにエラーを報告します。

アルゴリズムの一部として呼び出された関数の実行が例外をスローし、ExecutionPolicy が標準ポリシーのいずれかである場合、std::terminate が呼び出されます。その他の ExecutionPolicy の場合、動作は実装定義です。
アルゴリズムがメモリの割り当てに失敗した場合、std::bad_alloc がスローされます。

[edit] 実装例

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;
}

[edit] 例

このコードを実行

#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

[edit] 不具合報告

以下の動作変更を伴う欠陥報告が、以前に公開されたC++標準に遡って適用されました。

DR	適用対象	公開された動作	正しい動作
LWG 240	C++98	述語は std::find のように適用された。 (first, last, value) - first 回 (1,3) について、value は定義されなかった。	std::min( (result - first) + 1, (last - first) - 1) 回

[edit] 関連項目

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

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

cppreference.com

名前空間

変種

表示

操作