Generic way to remove all duplicates from a not-sorted container

Question

Here's an interesting article called "How to Remove Elements from a Sequence Container in C++". At some point, the author also explains how to remove duplicates from a container, but only with the very restrictive condition that those duplicates are adjacent. I've given a bit of thoughts on how to make a generic algorithm that would work on any duplicate in the container, and it's a bit more complicated that one might think at first.

The naively obvious solution is:

template <typename Iterator>
Iterator remove_duplicates(Iterator first, Iterator last) {
    auto it = std::next(first);
    while (first != last) {
        it = std::find(it, last, *first);
        if (it == last) it = std::next(++first);
        else std::rotate(it, std::next(it), last--);
    }
    return last;
}

and it looks a lot like an implementation of a STL's algorithm, but it also is a polynomial-time algorithm, which is only acceptable if there is no alternative. But you generally keep track of already encountered values in a separate container in order to attain linear or almost-linear time. Sets are good candidates but they come in two flavors, and the std::unordered_set being more efficient than the simple std::set must be used when possible.

I've used concepts (gcc > 6.3 && -fconcepts) to dispatch to the most efficient overload:

template <typename T>
concept bool Hashable = requires {
    std::hash<T>();
};

template <typename T>
concept bool Comparable = requires (T a, T b) {
    { a == b } -> bool;
};

template <typename T>
concept bool Orderable = requires (T a, T b) {
    { a < b } -> bool;
};

unordered_sets require the key to be hashable and comparable, and sets that it be orderable. After code factorization it gives:

template <typename Iterator, typename Set>
Iterator remove_duplicates_impl(Iterator first, Iterator last, Set& known_values) {
    while (first != last) {
        if (known_values.find(*first) != known_values.end()) std::rotate(first, std::next(first), last--);
        else known_values.insert(*first++);
    }
    return last;
}

template <typename Iterator>
Iterator remove_duplicates(Iterator first, Iterator last) 
        requires Orderable<Value_type<Iterator>> && !Hashable<Value_type<Iterator>>
{
    std::set<Value_type<Iterator>> known_values;
    return remove_duplicates_impl(first, last, known_values);
}


template <typename Iterator>
Iterator remove_duplicates(Iterator first, Iterator last) 
        requires Hashable<Value_type<Iterator>> && Comparable<Value_type<Iterator>>
{
    std::unordered_set<Value_type<Iterator>> known_values;
    return remove_duplicates_impl(first, last, known_values);
}

So what's missing here, be it optimizations or corner-cases handling?

A minimal working example:

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_set>
#include <set>
#include <iterator>
#include <type_traits>

template <typename Iterator>
using Value_type = typename std::iterator_traits<Iterator>::value_type;

template <typename T>
concept bool Hashable = requires {
    std::hash<T>();
};

template <typename T>
concept bool Comparable = requires (T a, T b) {
    { a == b } -> bool;
};

template <typename T>
concept bool Orderable = requires (T a, T b) {
    { a < b } -> bool;
};

template <typename Iterator>
Iterator remove_duplicates(Iterator first, Iterator last) {
    auto it = std::next(first);
    while (first != last) {
        it = std::find(it, last, *first);
        if (it == last) it = std::next(++first);
        else std::rotate(it, std::next(it), last--);
    }
    return last;
}

template <typename Iterator, typename Set>
Iterator remove_duplicates_impl(Iterator first, Iterator last, Set& known_values) {
    while (first != last) {
        if (known_values.find(*first) != known_values.end()) std::rotate(first, std::next(first), last--);
        else known_values.insert(*first++);
    }
    return last;
}

template <typename Iterator>
Iterator remove_duplicates(Iterator first, Iterator last) 
        requires Orderable<Value_type<Iterator>> && !Hashable<Value_type<Iterator>>
{
    std::set<Value_type<Iterator>> known_values;
    return remove_duplicates_impl(first, last, known_values);
}


template <typename Iterator>
Iterator remove_duplicates(Iterator first, Iterator last) 
        requires Hashable<Value_type<Iterator>>
{
    std::unordered_set<Value_type<Iterator>> known_values;
    return remove_duplicates_impl(first, last, known_values);
}

struct Foo {};
bool operator==(Foo, Foo) { return true; }

int main() {

    std::vector<int> data{ 1,2,3,4,5,6,7,8,9,8,7,6,5,2,4,3,1,8 };
    std::vector<int> unik(data.begin(), remove_duplicates(data.begin(), data.end()));
    for (auto i : unik) std::cout << i << ' '; 
    std::cout << std::endl;

    std::vector<std::pair<int, int>> test{ {1,2}, {3,4} , {5,6} , {7,8}, {7, 8} };
    [[maybe_unused]]
    auto it = remove_duplicates(test.begin(), test.end());

    std::vector<Foo> test2{ Foo(), Foo(), Foo() };
    [[maybe_unused]]
    auto it2 = remove_duplicates(test2.begin(), test2.end());

}

Answer 1

Your naive solution is quadratic time, O(n^2) and O(1) additional memory. Note, polynomial time doesn't say much about the actual time complexity other than it's not exponential or factorial.

Your improved version is O(nlogn) time for the implementation with set and O(n) for the one with unordered_set and both come with the additional cost of O(n) memory.

However the hash version is not necessarily faster than the set version depending on the cost of the hash function and value of n, you should allow the user the option of choosing a specific implementation if they want.

I would probably call the functions something like remove_duplicates_stable to imply the property you are designing for that is preserving the original order and keeping the first observed value. Which by the way differs between the naive implementation and the others, the naive one keeps the last of the dupes.

If keeping the order of the elements is not important I would probably sort the source array and use std unique or something. Because sorting can make use of move construction to avoid possibly expensive copy construction of all non duplicate elements which is necessary in your implementation, requires no additional space, and is O(nlogn). But again it depends on if copy construction is expensive and of the hash function is expensive.

I would also put the implementation in a separate namespace, like "detail" but this is just personal style.

Answer 2

Regardless of which kind of set you use to keep track, you'll be spending a lot of time in std::rotate when given an input like this:

std::array<int, 10000>()

Yes, all the elements compare equal, and we dutifully rotate each one individually, resulting in (I think) ¼n² move operations. This is a problem with the "naive method", too, but not with std::unique(). If we're going to use extra storage, it might be more productive to use at least some of it to selectively copy input values to a new collection, and then swap() that new collection back into place.

---

I know it's not really the code for review, but I can't resist pointing out that you could have written the naive version more clearly with std::remove(), like this:

template <typename Iterator>
Iterator remove_duplicates(Iterator first, Iterator last)
{
    while (first != last) {
        auto const& value = *first;
        last = std::remove(first = std::next(first), last, value);
    }
    return last;
}