std::adjacent_find - cppreference.com

From cppreference.com

Defined in header `<algorithm>`
template< class ForwardIt > ForwardIt adjacent_find( ForwardIt first, ForwardIt last );	(1)	(constexpr since C++20)
template< class ForwardIt, class BinaryPred > ForwardIt adjacent_find( ForwardIt first, ForwardIt last, BinaryPred p );	(2)	(constexpr since C++20)
template< class ExecutionPolicy, class ForwardIt > ForwardIt adjacent_find( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );	(3)	(since C++17)
template< class ExecutionPolicy, class ForwardIt, class BinaryPred > ForwardIt adjacent_find( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, BinaryPred p );	(4)	(since C++17)

Searches the source range [first, last) for the first pair of adjacent elements satisfying the specified condition.

1) Searches for the first pair of adjacent equal elements. Equality is determined by operator==.

2) Searches for the first pair of adjacent elements satisfying the given binary predicate p.

3,4) Same as (1,2), but executed according to policy.

These overloads participate in overload resolution only if the value of the following expression is true:

`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)

Parameters

first, last	-	the pair of iterators defining the source range
p	-	binary predicate which returns `true` if the elements should be treated as equal. The signature of the predicate function should be equivalent to the following: `bool pred(const Type1 &a, const Type2 &b);` While the signature does not need to have `const &`, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) `Type1` and `Type2` regardless of value category (thus, `Type1 &` is not allowed, nor is `Type1` unless for `Type1` a move is equivalent to a copy(since C++11)). The types `Type1` and `Type2` must be such that an object of type `ForwardIt` can be dereferenced and then implicitly converted to both of them.
policy	-	the execution policy to use
Type requirements
-`ForwardIt` must meet the requirements of LegacyForwardIterator.
-`BinaryPred` must meet the requirements of BinaryPredicate.

Return value

The first iterator iter in the source range such that the following expression evaluates to true:

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

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

If no such iterator is found, last is returned.

Complexity

Given result as the return value of adjacent_find, M as std::distance(first, result) and N as std::distance(first, last):

1) Exactly min(M+1,N-1) comparisons using operator==.

2) Exactly min(M+1,N-1) applications of the predicate p.

3) 𝓞(N) comparisons using operator==.

4) 𝓞(N) applications of the predicate p.

Exceptions

3,4) During the execution process:

If the temporary memory resources required for parallelization are not available, std::bad_alloc is thrown.
If an uncaught exception is thrown while accessing objects via an algorithm argument, the behavior is determined by the execution policy (for standard policies, std::terminate is invoked).

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

Example

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

Output:

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

Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

DR	Applied to	Behavior as published	Correct behavior
LWG 240	C++98	the complexity requirement was unclear	made clear

	finds the first two adjacent items that are equal (or satisfy a given predicate) (algorithm function object)[edit]
	removes consecutive duplicate elements in a range (function template & algorithm function object)[edit]