4. adjacent_find

最終更新日時(UTC):
が更新

履歴 編集

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
}

概要

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

戻り値

[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

実装例

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

処理系

参照