c++ - 从 vector 中删除重复项的最快方法

就像标题所说的那样，我在脑海中有一些方法可以做到，但我不知道哪种方法最快。

假设我们有一个带有一些值的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将 vector 转换为集合后，在 2 处，使用集合执行我需要做的事情还是应该做vals.assign( .. )并继续执行 vector ，这更方便。

最佳答案

问题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快得多。

关于c++ - 从 vector 中删除重复项的最快方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33774354/