c++ - 从 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 ，我检查它是否已经在我的 vector 中:

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

4

从头开始使用一组

好的，我有这4个方法，我的问题是:

1 1、2 和 3 哪个最快？
2 4 是否比前 3 个快？
3 在2 将 vector 转换为集合后，使用集合做我需要做的事情或我应该做vals.assign( .. ) 更方便并继续我的 vector ？

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.