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) первую пару соседних элементов, удовлетворяющих заданному условию.
operator==.p.policy.true:
|
|
(до C++20) |
|
|
(начиная с C++20) |
Параметры
| first, last | - | пара итераторов, определяющая исходный диапазон |
| p | - | бинарный предикат, который возвращает true, если элементы следует считать равными. Сигнатура функции предиката должна быть эквивалентна следующей:
Хотя сигнатура не обязана содержать |
| policy | - | политика выполнения, которую следует использовать |
| Требования к типам | ||
-ForwardIt должен удовлетворять требованиям LegacyForwardIterator.
| ||
-BinaryPred должен удовлетворять требованиям BinaryPredicate.
| ||
Возвращаемое значение
Первый итератор iter в исходном диапазоне, для которого следующее выражение вычисляется в true:
bool(*iter == *std::next(iter))bool(p(*iter, std::next(iter))Если такой итератор не найден, возвращается last.
Сложность
Пусть result — возвращаемое значение adjacent_find, M равно std::distance(first, result) и N равно std::distance(first, last):
operator==.p.operator==.p.Исключения
- Если временные ресурсы памяти, необходимые для параллелизации, недоступны, выбрасывается 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;
}
|
Пример
#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 | требование к сложности было неясным | уточнено |
См. также
(C++20) |
находит первые два соседних элемента, которые равны (или удовлетворяют заданному предикату) (объект функции алгоритма) |
| удаляет последовательные дублирующиеся элементы в диапазоне (шаблон функции & объект функции алгоритма) | |
(C++20) |