Difference between revisions of "cpp/algorithm/unique"

Revision as of 19:46, 2 December 2020

Eliminates all except the first element from every consecutive group of equivalent elements from the range [first, last) and returns a past-the-end iterator for the new logical end of the range.

Removing is done by shifting the elements in the range in such a way that elements to be erased are overwritten. Relative order of the elements that remain is preserved and the physical size of the container is unchanged. Iterators pointing to an element between the new logical end and the physical end of the range are still dereferenceable, but the elements themselves have unspecified values. A call to unique is typically followed by a call to a container's erase method, which erases the unspecified values and reduces the physical size of the container to match its new logical size.

Parameters

Return value

Forward iterator to the new end of the range.

Complexity

For nonempty ranges, exactly std::distance(first,last) -1 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 other ExecutionPolicy, the behavior is implementation-defined.
• If the algorithm fails to allocate memory, std::bad_alloc is thrown.

Possible implementation

See also the implementations in libstdc++ and libc++.

template<class ForwardIt>
ForwardIt unique(ForwardIt first, ForwardIt last)
{
    if (first == last)
        return last;
 
    ForwardIt result = first;
    while (++first != last) {
        if (!(*result == *first) && ++result != first) {
            *result = std::move(*first);
        }
    }
    return ++result;
}

template<class ForwardIt, class BinaryPredicate>
ForwardIt unique(ForwardIt first, ForwardIt last, BinaryPredicate p)
{
    if (first == last)
        return last;
 
    ForwardIt result = first;
    while (++first != last) {
        if (!p(*result, *first) && ++result != first) {
            *result = std::move(*first);
        }
    }
    return ++result;
}

Example

#include <algorithm>
#include <iostream>
#include <vector>
 
int main()
{
    // a vector containing several duplicate elements
    std::vector<int> v{1,2,1,1,3,3,3,4,5,4};
    auto print = [&] {
        for (int i : v)
            std::cout << i << ' ';
        std::cout << '\n';
    };
    print();
 
    // remove consecutive (adjacent) duplicates
    auto last = std::unique(v.begin(), v.end());
    // v now holds {1 2 1 3 4 5 4 x x x}, where 'x' is indeterminate
    v.erase(last, v.end());
    print();
 
    // sort followed by unique, to remove all duplicates
    std::sort(v.begin(), v.end()); // {1 1 2 3 4 4 5}
    last = std::unique(v.begin(), v.end());
    // v now holds {1 2 3 4 5 x x}, where 'x' is indeterminate
    v.erase(last, v.end());
    print();
}

1 2 1 1 3 3 3 4 5 4
1 2 1 3 4 5 4
1 2 3 4 5

See also