std::adjacent_find

Определён в заголовке `<algorithm>`
template< class ForwardIt > ForwardIt adjacent_find( ForwardIt first, ForwardIt last );	(1)	(constexpr с C++20)
template< class ForwardIt, class BinaryPred > ForwardIt adjacent_find( ForwardIt first, ForwardIt last, BinaryPred p );	(2)	(constexpr с C++20)
template< class ExecutionPolicy, class ForwardIt > ForwardIt adjacent_find( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );	(3)	(с C++17)
template< class ExecutionPolicy, class ForwardIt, class BinaryPred > ForwardIt adjacent_find( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, BinaryPred p );	(4)	(с C++17)

Выполняет поиск в исходном диапазоне [first, last) первой пары соседних элементов, удовлетворяющих заданному условию.

1) Выполняет поиск первой пары равных соседних элементов. Равенство определяется с помощью operator==.

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

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

Эти перегрузки участвуют в разрешении перегрузки, только если значение следующего выражения равно true:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(с C++20)

Параметры

first, last	-	пара итераторов, задающих исходный диапазон
p	-	бинарный предикат, возвращающий `true`, если элементы следует считать равными. Сигнатура функции-предиката должна быть эквивалентна следующей: boolpred(constType1&a,constType2&b); Хотя сигнатура не обязана содержать `const &`, функция не должна изменять переданные ей объекты и должна принимать значения любого типа (возможно, const) `Type1` и `Type2` независимо от категории значения (поэтому `Type1 &` не допускается, как и `Type1`, если только для `Type1` перемещение не эквивалентно копированию(с C++11)). Типы Type1 и Type2 должны быть такими, чтобы объект типа ForwardIt можно было разыменовать и неявно преобразовать в каждый из этих типов.
policy	-	используемая политика выполнения
Требования к типам
-`ForwardIt` должен соответствовать требованиям LegacyForwardIterator.
-`BinaryPred` должен соответствовать требованиям BinaryPredicate.

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

Первый итератор iter в исходном диапазоне, для которого следующее выражение принимает значение true:

1,3) bool(*iter == *std::next(iter))

2,4) bool(p(*iter, std::next(iter))

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

Сложность

Пусть result — возвращаемое значение adjacent_find, \(\scriptsize M\)M — std::distance(first, result), а \(\scriptsize N\)N — std::distance(first, last):

1) Ровно \(\scriptsize \min(M+1,N-1)\)min(M+1,N-1) сравнений с помощью operator==.

2) Ровно \(\scriptsize \min(M+1,N-1)\)min(M+1,N-1) вызовов p.

3) \(\scriptsize \mathcal{O}(N)\)𝓞(N) сравнений с помощью operator==.

4) \(\scriptsize \mathcal{O}(N)\)𝓞(N) вызовов p.

Исключения

3,4) Во время выполнения:

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

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

adjacent_find (1)
template<class ForwardIt> ForwardIt adjacent_find(ForwardIt first, ForwardIt last) { if (first == last) return last; ForwardIt next = first; ++next; for (; next != last; ++next, ++first) if (first == next) return first; return last; }
adjacent_find (2)
template<class ForwardIt, class BinaryPred> ForwardIt adjacent_find(ForwardIt first, ForwardIt last, BinaryPred p) { if (first == last) return last; ForwardIt next = first; ++next; for (; next != last; ++next, ++first) if (p(first, next)) return first; return last; }

adjacent_find (1)

template<class ForwardIt>
ForwardIt adjacent_find(ForwardIt first, ForwardIt last)
{
    if (first == last)
        return last;
    
    ForwardIt next = first;
    ++next;
    
    for (; next != last; ++next, ++first)
        if (*first == *next)
            return first;
    
    return last;
}

adjacent_find (2)

template<class ForwardIt, class BinaryPred>
ForwardIt adjacent_find(ForwardIt first, ForwardIt last, BinaryPred p)
{
    if (first == last)
        return last;
    
    ForwardIt next = first;
    ++next;
    
    for (; next != last; ++next, ++first)
        if (p(*first, *next))
            return first;
    
    return last;
}

Пример

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

int main()
{
    std::vector<int> v1{0, 1, 2, 3, 40, 40, 41, 41, 5};
    
    auto i1 = std::adjacent_find(v1.begin(), v1.end());
    
    if (i1 == v1.end())
        std::cout << "No matching adjacent elements\n";
    else
        std::cout << "The first adjacent pair of equal elements is at "
                  << std::distance(v1.begin(), i1) << ", *i1 = "
                  << *i1 << '\n';
    
    auto i2 = std::adjacent_find(v1.begin(), v1.end(), std::greater<int>());
    if (i2 == v1.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 "
                  << std::distance(v1.begin(), i2) << ", *i2 = " << *i2 << '\n';
}

Вывод:

The first adjacent pair of equal elements is at 4, *i1 = 40
The last element in the non-decreasing subsequence is at 7, *i2 = 41

Отчёты об ошибках

Следующие отчёты об ошибках, изменяющие поведение, были применены задним числом к ранее опубликованным стандартам C++.

DR	Применён к	Опубликованное поведение	Корректное поведение
LWG 240	C++98	требование к сложности было неясным	разъяснено

См. также

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

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