Find the first consecutive duplicate in a sequence

Source code

Declaration

template <class InputIterator>
InputIterator adjacent_find(InputIterator first, InputIterator last);

template <class InputIterator, class BinaryPredicate>
InputIterator adjacent_find(InputIterator first, InputIterator last,
                            BinaryPredicate binary_pred);

Description      The adjacent_find  function returns an iterator i referring to the first consecutive duplicate  element in the range [ first, last) , or last if there is no such location. In the first function checks for element equality are made with operator==, while in the second they are made with the function object binary_pred.

Type requirements

• InputIterator must be at least an input iterator .
• BinaryPredicate must be a function object type that provides int operator()(S, S), where S is the dereference type of InputIterator.

Group Non-mutating sequence operations.

Time complexity Linear.

If a consecutive duplicate  is found, then the number of comparisons performed is the size of the range [ first, i] ; otherwise, the number of comparisons performed is the size of the range [ first, last) .

Space complexity Constant.

Mutative? No.

Details By a consecutive duplicate , it is meant that an element is equal  to the element immediately following it in the range.

If the range [ first, last) is sorted   (either in ascending or decending order), then adjacent_find  returns last if and only if there are no duplicate elements   (according to operator== or function object binary_pred).

Glossary terms BinaryPredicate, constant space, dereference type, function object, function object type, InputIterator, iterator, linear time, mutative, operator ==, range, sequence.

Example Select here to view the source code for the example.

Implementation Select here to view source code (Copyright (C) 1994, Hewlett-Packard Company) for this algorithm.