[SOLVED] std::unique() algorithm returns clearly non-unique results

std::unique() algorithm returns clearly non-unique results

I have been experimenting with C++'s std::unique() algorithm, but the results it returns really confuse me.

I have done a simple function to test it, like so:

#include <algorithm>
#include <vector>
#include <iostream>

int main()
{
    std::vector<int> test;
    for(int i =0; i < 1000; i++)
        test.push_back(rand() % 10);

    std::vector<int>::iterator last = std::unique<std::vector<int>::iterator>(test.begin(), test.end());
    test.erase(last, test.end());

    for(int x : test)
        std::cout << x << "\n";

    std::cout << std::distance(test.begin(), last) << "\n";
}

And somehow it returns 908 numbers, not unique whatsoever. I even tested it with an online compiler just to be sure that it wasn't my broken stdlibc++, but it's the same result.

Solution

std::unique only removes consecutive duplicates.

It operates in O(n) time complexity, so it can not compare every element with every other element.

Try sorting your vector first.

std::vector<int> test;
for(int i =0; i < 1000; i++)
    test.push_back(rand() % 10);

std::sort(test.begin(), test.end());
std::vector<int>::iterator last = std::unique<std::vector<int>::iterator>(test.begin(), test.end());
test.erase(last, test.end());

for(int x : test)
    std::cout << x << "\n";

std::cout << std::distance(test.begin(), last) << "\n";

Output: