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

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

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

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

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

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


当前回答

我同意R. Pate和Todd Gardner的观点;std::set在这里可能是个好主意。即使你在使用向量时遇到了困难,如果你有足够多的副本,你最好创建一个集合来做这些肮脏的工作。

让我们来比较三种方法:

用向量,sort + unique

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

转换为set(手动)

set<int> s;
unsigned size = vec.size();
for( unsigned i = 0; i < size; ++i ) s.insert( vec[i] );
vec.assign( s.begin(), s.end() );

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

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

下面是它们在重复数量变化时的表现:

总结:当副本的数量足够大时,实际上更快地将数据转换为一个集合,然后将数据转储回一个向量。

出于某种原因,手动进行set转换似乎比使用set构造函数更快——至少在我使用的随机数据上是这样。

其他回答

效率是一个复杂的概念。有时间和空间的考虑,以及一般的测量(你只能得到模糊的答案,如O(n))和特定的(例如冒泡排序可以比快速排序快得多,这取决于输入特征)。

如果你有相对较少的副本,那么排序,然后唯一和擦除似乎是要走的路。如果您有相对较多的副本,则从向量创建一个集合,并让它完成繁重的工作,可以轻松击败它。

也不要只关注时间效率。Sort+unique+erase操作在O(1)空间,而set构造操作在O(n)空间。而且这两种方法都不能直接用于map-reduce并行化(对于真正庞大的数据集)。

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

Unique只删除连续的重复元素(这是它在线性时间内运行所必需的),因此应该首先执行排序。调用unique后,它将保持排序。

更多可理解的代码来自:https://en.cppreference.com/w/cpp/algorithm/unique

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cctype>

int main() 
{
    // remove duplicate elements
    std::vector<int> v{1,2,3,1,2,3,3,4,5,4,5,6,7};
    std::sort(v.begin(), v.end()); // 1 1 2 2 3 3 3 4 4 5 5 6 7 
    auto last = std::unique(v.begin(), v.end());
    // v now holds {1 2 3 4 5 6 7 x x x x x x}, where 'x' is indeterminate
    v.erase(last, v.end()); 
    for (int i : v)
      std::cout << i << " ";
    std::cout << "\n";
}

增长:

1 2 3 4 5 6 7

如果您正在寻找性能并使用std::vector,我推荐使用本文档链接提供的方法。

std::vector<int> myvector{10,20,20,20,30,30,20,20,10};             // 10 20 20 20 30 30 20 20 10
std::sort(myvector.begin(), myvector.end() );
const auto& it = std::unique (myvector.begin(), myvector.end());   // 10 20 30 ?  ?  ?  ?  ?  ?
                                                                   //          ^
myvector.resize( std::distance(myvector.begin(),it) ); // 10 20 30