std::ranges::adjacent_find

Определено в заголовке <algorithm>

Вызов

Определено в заголовке `<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< 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)

Ищет в диапазоне [first, last) две последовательные равные элементы.

1) Элементы сравниваются с помощью pred (после применения проекции proj).

2) То же, что и (1), но использует r в качестве исходного диапазона, как если бы ranges::begin(r) использовалось как first и ranges::end(r) как last.

Функциональные сущности, описанные на этой странице, являются niebloids, то есть:

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

На практике они могут быть реализованы как объекты-функции или с помощью специальных расширений компилятора.

Параметры

first, last	-	диапазон элементов для проверки
r	-	диапазон элементов для проверки
pred	-	предикат для применения к проецированным элементам
proj	-	проекция для применения к элементам

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

Итератор на первый из пары одинаковых элементов, то есть первый итератор it такой, что bool(std::invoke(pred, std::invoke(proj1, *it), std::invoke(proj, *(it + 1)))) является true.

Если такие элементы не найдены, возвращается итератор, равный last.

Сложность

Точно min((result - first) + 1, (last - first) - 1) применений предиката и проекции, где result является возвращаемым значением.

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

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;

Пример

#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](auto const& x, auto const& 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

См. также

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

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