Remove consecutive duplicates from a sequence

Source code

Declaration

template <class ForwardIterator>
ForwardIterator unique(ForwardIterator first, ForwardIterator last);

template <class ForwardIterator, class BinaryPredicate>
ForwardIterator unique(ForwardIterator first, ForwardIterator last,
                       BinaryPredicate binary_pred);

template <class InputIterator, class OutputIterator>
OutputIterator unique_copy(InputIterator first, InputIterator last,
                           OutputIterator result);

template <class InputIterator, class OutputIterator, class BinaryPredicate>
OutputIterator unique_copy(InputIterator first, InputIterator last,
                           OutputIterator result,
                           BinaryPredicate binary_pred);

Description     The unique  functions remove    consecutive duplicates from the range [ first, last) and return l, the past-the-end iterator .

The unique_copy  functions copy elements in the range [ first, last) to the range [ result, l) , except for elements that are consecutive duplicates   , and return the location l that is the past-the-end iterator  for the resulting sequence.

An element is considered a consecutive duplicate   if it is equal to an element in the location to its immediate right in the range.

In the first function checks for element equality are made with operator!=, while in the second they are made with the function object BinaryPredicate.

Type requirements

• ForwardIterator must be at least a regular forward iterator .
• InputIterator must be at least an input iterator .
• OutputIterator must be at least an output iterator .
• For the unique functions, BinaryPredicate must be a function object type that provides int operator()(S, S), where S is the dereference type of \ ForwardIterator. For the unique_copy functions, BinaryPredicate must be a function object type that provides int operator()(T1, T2), where T1 and T2 are the dereference types of OutputIterator and InputIterator, respectively.

Group Mutating sequence operations.

Time complexity Linear.

Space complexity Constant.

Mutative? Yes.

Details

1. These functions are stable ; i.e., the elements in the resulting range are in the same order as they were in the original range.
2. Typically these functions are applied to a sorted  range (either ascending or decending order), since in that case all duplicates  are consecutive duplicates  . For an unsorted  range, sort  with an time algorithm followed by unique  (linear time) to remove duplicates   (provided that stability ---order of elements in the result---doesn't matter).

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.