删除重复项和对向量进行排序的最有效方法是什么? [英] What's the most efficient way to erase duplicates and sort a vector?

问题描述

我需要使用可能包含大量元素的 C++ 向量，删除重复项并对其进行排序.

I need to take a C++ vector with potentially a lot of elements, erase duplicates, and sort it.

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

I currently have the below code, but it doesn't work.

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

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

How can I correctly do this?

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

Additionally, is it faster to erase the duplicates first (similar to coded above) or perform the sort first? If I do perform the sort first, is it guaranteed to remain sorted after std::unique is executed?

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

Or is there another (perhaps more efficient) way to do all this?

推荐答案

我同意 R.Pate 和 托德·加德纳;std::set 可能是个好主意这里.即使您一直在使用向量，如果您有足够多的重复项，最好还是创建一个集合来完成繁琐的工作.

I agree with R. Pate and Todd Gardner; a std::set might be a good idea here. Even if you're stuck using vectors, if you have enough duplicates, you might be better off creating a set to do the dirty work.

让我们比较三种方法:

仅使用向量，排序 + 唯一

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

以下是这些在重复数量变化时的表现:

Here's how these perform as the number of duplicates changes:

总结:当重复的数量足够大时，转换为集合然后将数据转储回向量实际上会更快.

Summary: when the number of duplicates is large enough, it's actually faster to convert to a set and then dump the data back into a vector.

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

And for some reason, doing the set conversion manually seems to be faster than using the set constructor -- at least on the toy random data that I used.

这篇关于删除重复项和对向量进行排序的最有效方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！