删除重复和排序向量的最有效的方法是什么？ [英] 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.

我目前有以下代码， t工作。

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?

推荐答案

我同意和托德·加德纳; 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.

让我们比较三种方法：

/ p>

Just using vector, sort + unique

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<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.

由于某些原因，手动进行set转换似乎比使用set构造函数更快 - 至少对我使用的玩具随机数据。

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屋！