名前空間
変種
操作

std::adjacent_find

提供: cppreference.com
< cpp‎ | algorithm
 
 
アルゴリズムライブラリ
実行ポリシー (C++17)
非変更シーケンス操作
(C++11)(C++11)(C++11)
(C++17)
adjacent_find
変更シーケンス操作
未初期化記憶域の操作
分割操作
ソート操作
(C++11)
二分探索操作
集合操作 (ソート済み範囲用)
ヒープ操作
(C++11)
最小/最大演算
(C++11)
(C++17)
順列
数値演算
C のライブラリ
 
ヘッダ <algorithm> で定義
(1)
template< class ForwardIt >
ForwardIt adjacent_find( ForwardIt first, ForwardIt last );
(C++20以前)
template< class ForwardIt >
constexpr ForwardIt adjacent_find( ForwardIt first, ForwardIt last );
(C++20およびそれ以降)
template< class ExecutionPolicy, class ForwardIt >

ForwardIt adjacent_find( ExecutionPolicy&& policy,

                         ForwardIt first, ForwardIt last );
(2) (C++17およびそれ以降)
(3)
template< class ForwardIt, class BinaryPredicate>
ForwardIt adjacent_find( ForwardIt first, ForwardIt last, BinaryPredicate p );
(C++20以前)
template< class ForwardIt, class BinaryPredicate>
constexpr ForwardIt adjacent_find( ForwardIt first, ForwardIt last, BinaryPredicate p );
(C++20およびそれ以降)
template< class ExecutionPolicy, class ForwardIt, class BinaryPredicate>

ForwardIt adjacent_find( ExecutionPolicy&& policy,

                         ForwardIt first, ForwardIt last, BinaryPredicate p );
(4) (C++17およびそれ以降)

同じ要素が2つ連続する位置を範囲 [first, last) から検索します。

1) 要素は operator== を用いて比較されます。
3) 要素は指定された二項述語 p を用いて比較されます。
2,4) (1,3) と同じですが、 policy に従って実行されます。 これらのオーバーロードは、std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> が true でなければ、オーバーロード解決に参加しません。

目次

[編集] 引数

first, last - 調べる要素の範囲
policy - 使用する実行ポリシー。 詳細は実行ポリシーを参照してください
p - 要素が等しいと扱われるべき場合に ​true を返す二項述語。

述語関数のシグネチャは以下と同等なものであるべきです。

 bool pred(const Type1 &a, const Type2 &b);

シグネチャが const & を持つ必要はありませんが、関数は渡されたオブジェクトを変更してはなりません。
Type1 および Type2 は、どちらも ForwardIt 型のオブジェクトの逆参照から暗黙に変換可能なものでなければなりません。 ​

型の要件
-
ForwardItForwardIterator の要件を満たさなければなりません。

[編集] 戻り値

同じ要素の最初の組の先頭を指すイテレータ、つまり、1つめのバージョンの場合は *it == *(it+1) であるような最初のイテレータ it、2つめのバージョンの場合は p(*it, *(it + 1)) != false であるような最初のイテレータ it

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

[編集] 計算量

1,3) ちょうど min((result-first)+1, (last-first)-1) 回の述語の適用。 ただし result は戻り値です。
2,4) O(last-first) 回の対応する述語の適用。

[編集] 例外

テンプレート引数 ExecutionPolicy を持つオーバーロードは以下のようにエラーを報告します。

  • アルゴリズムの一部として呼び出された関数の実行が例外を投げ、 ExecutionPolicy が3つの標準のポリシーのいずれかの場合は、 std::terminate が呼ばれます。 それ以外のあらゆる ExecutionPolicy については、動作は処理系定義です。
  • アルゴリズムがメモリの確保に失敗した場合は、 std::bad_alloc が投げられます。

[編集] 実装例

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;
}
2つめのバージョン
template<class ForwardIt, class BinaryPredicate>
ForwardIt adjacent_find(ForwardIt first, ForwardIt last, 
                        BinaryPredicate 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 <iostream>
#include <vector>
#include <functional>
 
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 at: "
                  << std::distance(v1.begin(), 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) << '\n';
    }
}

出力:

The first adjacent pair of equal elements at: 4
The last element in the non-decreasing subsequence is at: 7

[編集] 関連項目

指定範囲の連続している重複要素を削除します
(関数テンプレート) [edit]