std::ranges::adjacent_find() algorithm

od C++20

Simplified

// (1)
constexpr I
    adjacent_find( I first, S last, Pred pred = {}, Proj proj = {} );

// (2)
constexpr ranges::borrowed_iterator_t<R>
    adjacent_find( R&& r, Pred pred = {}, Proj proj = {} );

The type of arguments are generic and have the following constraints:

• I - std::forward_iterator

• S - std::sentinel_for<I>

• Proj - (none)

• Pred:

  • (1) - indirect_binary_predicate<projected<I, Proj>, projected<I, Proj>>
  • (2) - indirect_binary_predicate<projected<ranges::iterator_t<R>, Proj>, projected<ranges::iterator_t<R>, Proj>>

  (The std:: namespace was ommitted here for readability)

• (2) - R - std::ranges::input_range

The Proj template argument has a default type of std::identity for all overloads.

Detailed

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

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

Searches the range [first; last) for two consecutive equal elements.

• (1) Elements are compared using pred (after projecting with the projection proj).

• (2) Same as (1), but uses r as the source range, as if using ranges::begin(r) as first and ranges::end(r) as last.

The function-like entities described on this page are niebloids.

Parameters

first last	The range of elements to examine.
r	The range of elements to examine.
pred	Predicate to apply to the projected elements.
proj	Projection to apply to the elements.

Return value

An iterator to the first of the first pair of identical elements, that is, the first iterator it such that bool(std::invoke(pred, std::invoke(proj1, *it), std::invoke(proj, *(it + 1)))) is true.

If no such elements are found, an iterator equal to last is returned.

Complexity

Exactly min((result - first) + 1, (last - first) - 1) applications of the predicate and projection where result is the return value.

Exceptions

(none)

Possible implementation

adjacent_find(1) and adjacent_find(2)

struct adjacent_find_fn
{
    template<std::forward_iterator I, std::sentinel_for<I> S, class Proj = std::identity,
             std::indirect_binary_predicate<
                 std::projected<I, Proj>,
                 std::projected<I, Proj>> Pred = ranges::equal_to>
    constexpr I operator()(I first, S last, Pred pred = {}, Proj proj = {}) const
    {
        if (first == last)
            return first;
        auto next = ranges::next(first);
        for (; next != last; ++next, ++first)
            if (std::invoke(pred, std::invoke(proj, *first), std::invoke(proj, *next)))
                return first;
        return next;
    }

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

inline constexpr adjacent_find_fn adjacent_find;

Examples

Main.cpp

#include <algorithm>
#include <functional>
#include <iostream>

int main()
{
    const auto v = {0, 1, 2, 3, 40, 40, 41, 41, 5}; /*
                                ^^          ^^       */
    namespace ranges = std::ranges;

    if (auto it = ranges::adjacent_find(v.begin(), v.end()); it == v.end())
        std::cout << "No matching adjacent elements\n";
    else
        std::cout << "The first adjacent pair of equal elements is at ["
                  << ranges::distance(v.begin(), it) << "] == " << *it << '\n';

    if (auto it = ranges::adjacent_find(v, ranges::greater()); it == v.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 ["
                  << ranges::distance(v.begin(), it) << "] == " << *it << '\n';
}

Output

The first adjacent pair of equal elements is at [4] == 40
The last element in the non-decreasing subsequence is at [7] == 41