最終更新日時: 2026年02月05日 13時53分18秒 (JST)
Akira Takahashi が更新

履歴 編集

function template
<algorithm>

# std::ranges::adjacent_find(C++20)

    namespace std::ranges {
      template <forward_iterator I,
                sentinel_for<I> S,
                class Proj = identity,
                indirect_binary_predicate<projected<I, Proj>,
                projected<I, Proj>> Pred = ranges::equal_to>
      constexpr I
        adjacent_find(I first, S last, Pred pred = {}, Proj proj = {}); // (1) C++20

      template <forward_range R,
                class Proj = identity,
                indirect_binary_predicate<projected<iterator_t<R>, Proj>,
                projected<iterator_t<R>, Proj>> Pred = ranges::equal_to>
      constexpr borrowed_iterator_t<R>
        adjacent_find(R&& r, Pred pred = {}, Proj proj = {});           // (2) C++20

      template <execution-policy Ep,
                random_access_iterator I,
                sized_sentinel_for<I> S,
                class Proj = identity,
                indirect_binary_predicate<projected<I, Proj>,
                projected<I, Proj>> Pred = ranges::equal_to>
      I adjacent_find(Ep&& exec,
                      I first,
                      S last,
                      Pred pred = {},
                      Proj proj = {});                                  // (3) C++26

      template <execution-policy Ep,
                sized-random-access-range R,
                class Proj = identity,
                indirect_binary_predicate<projected<iterator_t<R>, Proj>,
                projected<iterator_t<R>, Proj>> Pred = ranges::equal_to>
      borrowed_iterator_t<R>
        adjacent_find(Ep&& exec,
                      R&& r,
                      Pred pred = {},
                      Proj proj = {});                                  // (4) C++26
    }

## 概要

隣接する要素で条件を満たしている最初の要素を検索する。

- (1): イテレータ範囲を指定する
- (2): Rangeを直接指定する
- (3): (1)の並列アルゴリズム版。実行ポリシーを指定する
- (4): (2)の並列アルゴリズム版。実行ポリシーを指定する

このアルゴリズムは、範囲の先頭から1つづつ進みながら隣接するペアに対して条件を満たすかをチェックし、その条件を満たす最初の要素へのイテレータを返す。指定された条件を満たしているかをチェックされるのは、現在位置にある要素とその次の位置にある要素の2つについてであり、1つの要素は最大2回参照される。

整数の配列`{1, 3, 3, 5, 0, 4, 5, 2}`を入力、指定された条件`pred`を`std::greater<void>`とした時の、チェックされる要素の様子

    |0  1  2  3  4  5  6  7| : index
    [1, 3, 3, 5, 0, 4, 5, 2] : input range
    [1, 3] <- pred(1, 3) == false
       [3, 3] <- pred(3, 3) == false
          [3, 5] <- pred(3, 5) == false
             [5, 0] <- pred(5, 0) == true
                [0, 4]
                   [4, 5]
                      [5, 2]

この時、最初に条件を満たしたペアの左側の要素に対応するイテレータを返す。この例の場合、返される要素のイテレータは元の範囲で3番目の要素（0-indexed）であり、その値は`5`である。

## 戻り値

`[first,last)` 内にあるイテレータ i について、`invoke(pred, invoke(proj, *i), invoke(proj, *(i + 1))) != false` であるような最初のイテレータを返す。

もしそのようなイテレータが見つからなかった場合は `last` を返す。

## 計算量

与えられたシーケンスが空でない場合、正確に `min((i - first) + 1, (last - first) - 1)` 回（`i` は `adjacent_find` の戻り値）の比較または述語が適用される

## 例

### 基本的な使い方

    #include <algorithm>
    #include <iterator>
    #include <iostream>
    #include <vector>

    int main() {
      std::vector<int> v = { 1,4,3,3,1,2,2 };

      // 同じ値が連続している最初の要素を検索する
      auto it = std::ranges::adjacent_find(v);
      if (it == v.end()) {
        std::cout << "not found" << std::endl;
      } else {
        std::cout << "found: index==" << std::ranges::distance(v.begin(), it) << std::endl;
        std::cout << std::boolalpha << "*it == *(it+1): " << (*it == *(it+1)) << std::endl;
      }
    }

#### 出力

    found: index==2
    *it == *(it+1): true

#### 動作イメージ

    |0  1  2  3  4  5  6| : index
    [1, 4, 3, 3, 1, 2, 2] : input range
    [1, 4]
       [4, 3]
          [3, 3] <- pred(3, 3) == true
             [3, 1]
                [1, 2]
                   [2, 2]

### 並列アルゴリズムの例 (C++26)

    #include <algorithm>
    #include <execution>
    #include <iostream>
    #include <vector>

    int main() {
      std::vector<int> v = {1, 4, 3, 3, 1, 2, 2};

      // 並列に同じ値が連続している最初の要素を検索する
      auto it = std::ranges::adjacent_find(std::execution::par, v);
      if (it == v.end()) {
        std::cout << "not found" << std::endl;
      } else {
        std::cout << "found: index==" << std::distance(v.begin(), it) << std::endl;
      }
    }

#### 出力

    found: index==2

## 実装例

    struct adjacent_find_impl {
      template<forward_iterator I, sentinel_for<I> S, class Proj = identity, indirect_binary_predicate<projected<I, Proj>, projected<I, Proj>> Pred = ranges::equal_to>
      constexpr I operator()(I first, S last, Pred pred = {}, Proj proj = {}) const {
        if (first == last)
          return last;

        I next = first;
        ++next;
        for ( ; next != last; ++next, ++first)
          if (invoke(pred, invoke(proj, *first), invoke(proj, *next)))
            return first;
        return last;
      }

      template<forward_range R, class Proj = identity, indirect_binary_predicate<projected<iterator_t<R>, Proj>, projected<iterator_t<R>, Proj>> Pred = ranges::equal_to>
      constexpr borrowed_iterator_t<R> operator()(R&& r, Pred pred = {}, Proj proj = {}) const {
        return (*this)(begin(r), end(r), ref(pred), ref(proj));
      }
    };

    inline constexpr adjacent_find_impl adjacent_find;

## バージョン

### 言語

- C++20

### 処理系

- Clang: ??
- GCC: 10.1.0 ✅
- ICC: ??
- Visual C++: 2019 Update 10 ✅

## 参照

- N4861 25 Algorithms library
- P3179R9 C++ parallel range algorithms