我需要采取一个c++向量与潜在的很多元素,擦除重复,并排序。

我目前有下面的代码,但它不起作用。

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

我怎样才能正确地做到这一点呢?

此外,是先删除副本(类似于上面的编码)还是先执行排序更快?如果我先执行排序,它是否保证在std::unique执行后保持排序?

或者是否有另一种(也许更有效的)方法来完成这一切?


当前回答

unique只删除重复的元素,如果它们是邻居:你必须先对向量排序,然后它才能像你想的那样工作。

unique被定义为稳定的,所以在vector上运行unique之后,它仍然会被排序。

其他回答

unique只删除重复的元素,如果它们是邻居:你必须先对向量排序,然后它才能像你想的那样工作。

unique被定义为稳定的,所以在vector上运行unique之后,它仍然会被排序。

这里有一个模板来帮你做这件事:

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());
}

这样称呼它:

removeDuplicates<int>(vectorname);

在调用unique之前需要对它进行排序,因为unique只删除相邻的重复项。

编辑:38秒……

假设a是一个向量,使用

a.erase(独特(a.begin (), a.end ()), a.end ());运行时间为O(n)。

关于alexK7基准测试。我尝试了它们,得到了类似的结果,但是当值的范围为100万时,使用std::sort (f1)和使用std::unordered_set (f5)的情况产生类似的时间。当取值范围为1000万时,f1比f5快。

如果值的范围是有限的,并且值是无符号int,则可以使用std::vector,其大小对应于给定的范围。代码如下:

void DeleteDuplicates_vector_bool(std::vector<unsigned>& v, unsigned range_size)
{
    std::vector<bool> v1(range_size);
    for (auto& x: v)
    {
       v1[x] = true;    
    }
    v.clear();

    unsigned count = 0;
    for (auto& x: v1)
    {
        if (x)
        {
            v.push_back(count);
        }
        ++count;
    }
}