std::ranges::adjacent_find

Определён в заголовочном файле `<algorithm>`
Сигнатура вызова
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 = {} );	(1)	(начиная с C++20)
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 = {} );	(2)	(начиная с C++20)
template< /execution-policy/ Ep, std::random_access_iterator I, std::sized_sentinel_for<I> S, class Proj = std::identity, std::indirect_binary_predicate <std::projected<I, Proj>, std::projected<I, Proj>> Pred = ranges::equal_to > I adjacent_find( Ep&& policy, I first, S last, Pred pred = {}, Proj proj = {} );	(3)	(начиная с C++26)
template< /execution-policy/ Ep, /sized-random-access-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 > ranges::borrowed_iterator_t<R> adjacent_find( Ep&& policy, R&& r, Pred pred = {}, Proj proj = {} );	(4)	(начиная с C++26)

Определение /*execution-policy*/ см. на этой странице; определение /*sized-random-access-range*/ см. на этой странице.

Выполняет поиск в исходном диапазоне первой пары соседних элементов (спроецированных с помощью proj), удовлетворяющей заданному бинарному предикату pred.

1) Исходный диапазон — это [first, last).

2) Исходный диапазон — это r.

3,4) То же, что и (1,2), но выполняется в соответствии с policy.

Функциональные объекты, описанные на этой странице, являются функциональными объектами алгоритмов (неофициально называемыми niebloids), то есть:

При вызове любого из них нельзя указывать явные списки аргументов шаблона.
Ни один из них не виден для поиска, зависящего от аргументов.
Когда любой из них обнаруживается посредством обычного неквалифицированного поиска в качестве имени слева от оператора вызова функции, поиск, зависящий от аргументов, подавляется.

Параметры

first, last	-	пара итератора и сентинела, задающая исходный диапазон
r	-	исходный диапазон
pred	-	предикат, применяемый к (спроецированным) элементам
proj	-	проекция, применяемая к элементам
policy	-	политика выполнения, которую следует использовать

Возвращаемое значение

Первый итератор iter в исходном диапазоне, для которого bool(std::invoke(pred, std::invoke(proj, *iter), std::invoke(proj, *ranges::next(iter)))) принимает значение true.

Если такой итератор не найден, возвращает:

1,3) ranges::next(first, last)

2,4) ranges::next(ranges::begin(r), ranges::end(r))

Сложность

Пусть

result — возвращаемое значение adjacent_find,
\(\scriptsize M\)M — это ranges::distance(first, result) или ranges::distance(ranges::begin(r), result), а
\(\scriptsize N\)N — это ranges::distance(first, last) или ranges::distance(r):

1,2) Ровно \(\scriptsize \min(M+1,N-1)\)min(M+1,N-1) применений pred.

3,4) \(\scriptsize \mathcal{O}(N)\)𝓞(N) применений pred.

proj применяется не более чем вдвое чаще, чем pred.

Исключения

3,4) В ходе выполнения:

Если временные ресурсы памяти, необходимые для распараллеливания, недоступны, выбрасывается std::bad_alloc.
Если при доступе к объектам через аргумент алгоритма выбрасывается неперехваченное исключение, поведение определяется политикой выполнения (для стандартных политик вызывается std::terminate).

Возможная реализация

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::next(ranges::begin(r), ranges::end(r)),
                       std::ref(pred), std::ref(proj));
    }
};

inline constexpr adjacent_find_fn adjacent_find;

Пример

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

constexpr bool some_of(auto&& r, auto&& pred) // some but not all
{
    return std::ranges::cend(r) != std::ranges::adjacent_find(r,
        [&pred](const auto& x, const auto& y)
        {
            return pred(x) != pred(y);
        });
}

// test some_of
constexpr auto a = {0, 0, 0, 0}, b = {1, 1, 1, 0}, c = {1, 1, 1, 1};
auto is_one = [](auto x){ return x == 1; };
static_assert(!some_of(a, is_one) && some_of(b, is_one) && !some_of(c, is_one));

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';
}

Вывод:

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

См. также

adjacent_find	находит первые два соседних элемента, которые равны (или удовлетворяют заданному предикату) (шаблон функции)
ranges::unique (C++20)	удаляет последовательные повторяющиеся элементы в диапазоне (функциональный объект алгоритма)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/ranges/adjacent_find