std::adjacent_find() algorithm
- since C++20
- since C++17
- until C++17
// (1)
template< class ForwardIt >
constexpr ForwardIt adjacent_find( ForwardIt first, ForwardIt last );
// (2)
template< class ForwardIt, class BinaryPredicate >
constexpr ForwardIt adjacent_find( ForwardIt first, ForwardIt last, BinaryPredicate p );
// (3)
template< class ExecutionPolicy, class ForwardIt >
ForwardIt adjacent_find( ExecutionPolicy&& policy,
ForwardIt first, ForwardIt last );
// (4)
template< class ExecutionPolicy, class ForwardIt, class BinaryPredicate >
ForwardIt adjacent_find( ExecutionPolicy&& policy,
ForwardIt first, ForwardIt last, BinaryPredicate p );
// (1)
template< class ForwardIt >
ForwardIt adjacent_find( ForwardIt first, ForwardIt last );
// (2)
template< class ForwardIt, class BinaryPredicate >
ForwardIt adjacent_find( ForwardIt first, ForwardIt last, BinaryPredicate p );
// (3)
template< class ExecutionPolicy, class ForwardIt >
ForwardIt adjacent_find( ExecutionPolicy&& policy,
ForwardIt first, ForwardIt last );
// (4)
template< class ExecutionPolicy, class ForwardIt, class BinaryPredicate >
ForwardIt adjacent_find( ExecutionPolicy&& policy,
ForwardIt first, ForwardIt last, BinaryPredicate p );
// (1)
template< class ForwardIt >
ForwardIt adjacent_find( ForwardIt first, ForwardIt last );
// (2)
template< class ForwardIt, class BinaryPredicate >
ForwardIt adjacent_find( ForwardIt first, ForwardIt last, BinaryPredicate p );
Searches the range [first
; last
) for two consecutive equal elements.
-
(1) Elements are compared using
operator==
. -
(2) Elements are compared using the given binary predicate
p
. -
(3 - 4) Same as (1 - 2), but executed according to
policy
.Overload ResolutionThese overloads participate in overload resolution only if
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
(until C++20)std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>
(since C++20) istrue
.
Parameters
first last | The range of elements to examine. |
policy | The execution policy to use. See execution policy for details. |
p | Binary predicate which returns The signature of the function should be equivalent to the following:
|
Type requirements
ForwardIt | LegacyForwardIterator |
Return value
An iterator to the first of the first pair of identical elements, that is, the first iterator it
such that *it == *(it + 1)
for (1, 3) or p(*it, *(it + 1)) != false
for (2, 4).
If no such elements are found, last
is returned.
Complexity
- (1, 3) Exactly
std::min((result - first) + 1, (last - first) - 1)
applications of the predicate where result is the return value. - (2, 4) O(last - first) applications of the corresponding predicate.
Exceptions
The overloads with a template parameter named ExecutionPolicy
report errors as follows:
- If execution of a function invoked as part of the algorithm throws an exception and
ExecutionPolicy
is one of the standard policies,std::terminate
is called. For any otherExecutionPolicy
, the behavior is implementation-defined. - If the algorithm fails to allocate memory,
std::bad_alloc
is thrown.
Possible implementation
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 BinaryPredicate>
ForwardIt adjacent_find(ForwardIt first, ForwardIt last, BinaryPredicate p)
{
if (first == last)
return last;
ForwardIt next = first;
++next;
for (; next != last; ++next, ++first)
if (p(*first, *next))
return first;
return last;
}
Examples
#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
Hover to see the original license.