Most efficient way to erase duplicates and sort a c++ vector?

Question

I need to take a C++ vector with potentially a lot of elements, erase duplicates, and sort it. Looks like this code will do the trick: (Correction--it won't; next time I'll test before posting. Thanks for the feedback.)

vec.erase(
      std::unique(vec.begin(), vec.end()),
      vec.end());
std::sort(vec.begin(), vec.end());

Is it faster to erase the duplicates first (as coded above) or perform the sort first? If I do perform the sort first, is it guaranteed to remain sorted after std::unique is executed?

Or is there a more efficient way to do all this?

Answer 1

std::unique only works on consecutive runs of duplicate elements, so you'd better sort first. However, it is stable, so your vector will remain sorted.

Answer 2

You need to sort it before you call unique because unique only removes duplicates that are next to each other.

edit: 38 seconds...

Answer 3

unique only removes consecutive duplicate elements (which is necessary for it to run in linear time), so you should perform the sort first. It will remain sorted after the call to unique.

Answer 4

std::unique only removes duplicate elements if they're neighbours: you have to sort the vector first before it will work as you intend.

std::unique is defined to be stable, so the vector will still be sorted after running unique on it.

Answer 5

As already stated, unique requires a sorted container. Additionally, unique doesn't actually remove elements from the container. Instead, they are copied to the end, unique returns an iterator pointing to the first such duplicate element, and you are expected to call erase to actually remove the elements.

Answer 6

I'm not sure what you are using this for, so I can't say this with 100% certainty, but normally when I think "sorted, unique" container, I think of a std::set. It might be a better fit for your usecase:

std::set<Foo> foos(vec.begin(), vec.end()); // both sorted & unique already

Otherwise, sorting prior to calling unique (as the other answers pointed out) is the way to go.

Answer 7

Efficiency is a complicated concept. There's time vs. space considerations, as well as general measurements (where you only get vague answers such as O(n)) vs. specific ones (e.g. bubble sort can be much faster than quicksort, depending on input characteristics).

If you have relatively few duplicates, then sort followed by unique and erase seems the way to go. If you had relatively many duplicates, creating a set from the vector and letting it do the heavy lifting could easily beat it.

Don't just concentrate on time efficiency either. Sort+unique+erase operates in O(1) space, while the set construction operates in O(n) space. And neither directly lends itself to a map-reduce parallelization (for really huge datasets).

Answer 8

Here's a template to do it for you:

template<typename T>
void removeDuplicates(std::vector<T>& vec)
{
    std::sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
}

call it like:

removeDuplicates<int>(vectorname);