从vector <>中删除重复项的最快方法

Question

正如标题所说,我在脑海中有一些方法可以做到,但我不知道哪个是最快的.

所以我们说我们有vector<int> vals一些:有一些价值观

1

我vals加入后

sort(vals.begin(), vals.end());
auto last = unique(vals.begin(), vals.end());
vals.erase(last, vals.end());

2

vals添加后转换为设置:

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

3

当我添加我的时候vals,我检查它是否已经在我的向量中:

if( find(vals.begin(), vals.end(), myVal)!=vals.end() )
    // add my val

4

从头开始使用一套

好的,我有这四种方法,我的问题是:

1从1,2和3这是最快的？
2 比前3 个快4吗？
3在将矢量转换为设置后的2处,使用该集合做我需要做的事情或者我应该vals.assign( .. )继续使用我的矢量更加方便吗？

Answer 1

问题1：1和2都是O(n log n)，3是O(n^2)。1到2之间，取决于数据。

问题 2：4 也是 O(n log n)，如果有很多重复项，它可能比 1 和 2 更好，因为它只存储每个副本的一个副本。想象一下一百万个值都是相等的。

问题 3：嗯，这实际上取决于您需要做什么。

在不了解更多情况下唯一可以说的是，您的替代方案 3 渐近地比其他方案更差。

如果您使用 C++11 并且不需要排序，则可以使用std::unordered_set，它是一个哈希表，并且比std::set.