删除重复项和排序向量的最有效方法是什么？

Question

我需要带有可能包含大量元素的C++向量,擦除重复项并对其进行排序.

我目前有以下代码,但它不起作用.

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

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

此外,首先擦除重复项(类似于上面编码)或首先执行排序是否更快？如果我首先执行排序,是否保证在std::unique执行后保持排序？

或者还有另一种(也许是更有效的)方法来做这一切吗？

Answer 1

我同意R. Pate和Todd Gardner ; 这std::set可能是一个好主意.即使你使用向量,如果你有足够的副本,你可能最好创建一个集来做脏工作.

我们来比较三种方法:

只需使用矢量,排序+唯一

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

转换为设置(手动)

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构造函数更快 - 至少在我使用的玩具随机数据上.

Answer 2

我重写了Nate Kohl的分析并得到了不同的结果.对于我的测试用例,直接对向量进行排序总是比使用集合更有效.我添加了一个新的更有效的方法,使用unordered_set.

请记住,unordered_set只有在您需要单独和排序的类型具有良好的哈希函数时,该方法才有效.对于整数,这很容易!(标准库提供了一个默认的哈希,它只是身份函数.)另外,不要忘记在最后排序,因为unordered_set是,无序的,无序的:)

我做了里面的一些挖掘set和unordered_set实施,并发现构造函数实际上构造一个新的节点,每一个元素,检查它的价值,以确定它实际上应该被插入之前(在Visual Studio实现,至少).

以下是5种方法:

f1:只需使用vector,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

Answer 3

std::unique 只有当它们是邻居时才会删除重复的元素:你必须先按照你想要的方式对向量进行排序.

std::unique 被定义为稳定的,因此在运行唯一的向量之后仍然会对向量进行排序.

Answer 4

我不确定你使用的是什么,所以我不能100%确定地说这个,但通常当我认为"排序,独特"的容器时,我会想到一个std :: set.它可能更适合您的用例:

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

否则,在调用unique之前进行排序(如指出的其他答案)是要走的路.

Answer 5

std::unique仅适用于连续运行的重复元素,因此您最好先排序.但是,它是稳定的,因此您的矢量将保持排序.

Answer 6

这是为您完成的模板:

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

Answer 7

您需要在调用之前对其进行排序,unique因为unique只会删除彼此相邻的重复项.

编辑:38秒......

Answer 8

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

如果你有相对较少的重复,那么排序后跟唯一和擦除似乎是要走的路.如果你有相对较多的重复项,从向量创建一个集合并让它完成繁重的工作可能很容易击败它.

不要只关注时间效率.排序+唯一+擦除在O(1)空间中操作,而集合构造在O(n)空间中操作.并且它们都没有直接适用于map-reduce并行化(对于非常庞大的数据集).

Answer 9

您可以按如下方式执行此操作：

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

Answer 10

unique只删除连续的重复元素(这是线性时间运行所必需的),因此您应首先执行排序.它将在通话后保持排序unique.

Answer 11

如果您不想更改元素的顺序,那么您可以尝试以下解决方案:

template <class T>
void RemoveDuplicatesInVector(std::vector<T> & vec)
{
    set<T> values;
    vec.erase(std::remove_if(vec.begin(), vec.end(), [&](const T & value) { return !values.insert(value).second; }), vec.end());
}

Answer 12

假设a是一个向量，使用

a.erase(unique(a.begin(),a.end()),a.end());在O(n)时间内运行。

Answer 13

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

action::unique(vec);

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

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