GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing cpprefjp.github.io — std::ranges::adjacent_find - cpprefjp C++日本語リファレンス

最終更新日時: 2026年09月11日 13時06分31秒 (JST)
Akira Takahashi が更新

function template

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 ✅
Visual C++: 2019 Update 10 ✅

参照

You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.