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

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

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

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

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

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


当前回答

我重做了内特·科尔的侧写得到了不同的结果。对于我的测试用例,直接对向量排序总是比使用集合更有效。我添加了一个新的更有效的方法,使用unordered_set。

请记住,unordered_set方法仅适用于您需要唯一和排序的类型的良好哈希函数。对于int型,这很简单!(标准库提供了一个默认的哈希,它只是标识函数。)另外,不要忘记在最后排序,因为unordered_set是无序的:)

我深入研究了set和unordered_set实现,发现构造函数实际上为每个元素构造了一个新节点,然后检查其值以确定是否应该实际插入(至少在Visual Studio实现中是这样)。

以下是5种方法:

f1:只是使用向量,sort + unique

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

f2:转换为set(使用构造函数)

set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );

f3:转换为set(手动)

set<int> s;
for (int i : vec)
    s.insert(i);
vec.assign( s.begin(), s.end() );

f4:转换为unordered_set(使用构造函数)

unordered_set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );
sort( vec.begin(), vec.end() );

f5:转换为unordered_set(手动)

unordered_set<int> s;
for (int i : vec)
    s.insert(i);
vec.assign( s.begin(), s.end() );
sort( vec.begin(), vec.end() );

我在[1,10],[1,1000]和[1,100000]的范围内随机选择了100,000,000 int的向量进行测试

结果(以秒为单位,越小越好):

range         f1       f2       f3       f4      f5
[1,10]      1.6821   7.6804   2.8232   6.2634  0.7980
[1,1000]    5.0773  13.3658   8.2235   7.6884  1.9861
[1,100000]  8.7955  32.1148  26.5485  13.3278  3.9822

其他回答

我重做了内特·科尔的侧写得到了不同的结果。对于我的测试用例,直接对向量排序总是比使用集合更有效。我添加了一个新的更有效的方法,使用unordered_set。

请记住,unordered_set方法仅适用于您需要唯一和排序的类型的良好哈希函数。对于int型,这很简单!(标准库提供了一个默认的哈希,它只是标识函数。)另外,不要忘记在最后排序,因为unordered_set是无序的:)

我深入研究了set和unordered_set实现,发现构造函数实际上为每个元素构造了一个新节点,然后检查其值以确定是否应该实际插入(至少在Visual Studio实现中是这样)。

以下是5种方法:

f1:只是使用向量,sort + unique

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

f2:转换为set(使用构造函数)

set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );

f3:转换为set(手动)

set<int> s;
for (int i : vec)
    s.insert(i);
vec.assign( s.begin(), s.end() );

f4:转换为unordered_set(使用构造函数)

unordered_set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );
sort( vec.begin(), vec.end() );

f5:转换为unordered_set(手动)

unordered_set<int> s;
for (int i : vec)
    s.insert(i);
vec.assign( s.begin(), s.end() );
sort( vec.begin(), vec.end() );

我在[1,10],[1,1000]和[1,100000]的范围内随机选择了100,000,000 int的向量进行测试

结果(以秒为单位,越小越好):

range         f1       f2       f3       f4      f5
[1,10]      1.6821   7.6804   2.8232   6.2634  0.7980
[1,1000]    5.0773  13.3658   8.2235   7.6884  1.9861
[1,100000]  8.7955  32.1148  26.5485  13.3278  3.9822

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

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只适用于重复元素的连续运行,所以你最好先排序。但是,它是稳定的,所以你的向量是有序的。

使用Ranges v3库,您可以简单地使用

action::unique(vec);

注意,它实际上删除了重复的元素,而不仅仅是移动它们。

不幸的是,动作在c++ 20中没有标准化,因为即使在c++ 20中,范围库的其他部分仍然必须使用原始库。

关于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;
    }
}