我需要采取一个c++向量与潜在的很多元素，擦除重复，并排序。
我目前有下面的代码，但它不起作用。
vec.erase(
std::unique(vec.begin(), vec.end()),
vec.end());
std::sort(vec.begin(), vec.end());
我怎样才能正确地做到这一点呢?
此外，是先删除副本(类似于上面的编码)还是先执行排序更快?如果我先执行排序，它是否保证在std::unique执行后保持排序?
或者是否有另一种(也许更有效的)方法来完成这一切?
当前回答
如果你不想改变元素的顺序，那么你可以尝试这个解决方案:
template <class T>
void RemoveDuplicatesInVector(std::vector<T> & vec)
{
set<T> values;
vec.erase(std::remove_if(vec.begin(), vec.end(), [&](const T & value) { return !values.insert(value).second; }), vec.end());
}
其他回答
我同意R. Pate和Todd Gardner的观点;std::set在这里可能是个好主意。即使你在使用向量时遇到了困难，如果你有足够多的副本，你最好创建一个集合来做这些肮脏的工作。
让我们来比较三种方法:
用向量，sort + unique
sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );
转换为set(手动)
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() );
下面是它们在重复数量变化时的表现:
总结:当副本的数量足够大时，实际上更快地将数据转换为一个集合，然后将数据转储回一个向量。
出于某种原因，手动进行set转换似乎比使用set构造函数更快——至少在我使用的随机数据上是这样。
效率是一个复杂的概念。有时间和空间的考虑，以及一般的测量(你只能得到模糊的答案，如O(n))和特定的(例如冒泡排序可以比快速排序快得多，这取决于输入特征)。
如果你有相对较少的副本，那么排序，然后唯一和擦除似乎是要走的路。如果您有相对较多的副本，则从向量创建一个集合，并让它完成繁重的工作，可以轻松击败它。
也不要只关注时间效率。Sort+unique+erase操作在O(1)空间，而set构造操作在O(n)空间。而且这两种方法都不能直接用于map-reduce并行化(对于真正庞大的数据集)。
大部分答案似乎是使用O(nlogn)，但使用unordered_set，我们可以将其减少到O(n)。我看到了一些使用集合的解决方案，但我发现了这个解决方案，使用集合和迭代器似乎更优雅。
using Intvec = std::vector<int>;
void remove(Intvec &v) {
// creating iterator starting with beginning of the vector
Intvec::iterator itr = v.begin();
std::unordered_set<int> s;
// loops from the beginning to the end of the list
for (auto curr = v.begin(); curr != v.end(); ++curr) {
if (s.insert(*curr).second) { // if the 0 curr already exist in the set
*itr++ = *curr; // adding a position to the iterator
}
}
// erasing repeating positions in the set
v.erase(itr, v.end());
}
我不知道你在用这个干什么，所以我不能100%肯定地说，但通常当我想到“排序的，唯一的”容器时，我想到std::set。它可能更适合你的用例:
std::set<Foo> foos(vec.begin(), vec.end()); // both sorted & unique already
否则，在调用unique之前进行排序(正如其他答案所指出的那样)才是正确的方法。
更多可理解的代码来自:https://en.cppreference.com/w/cpp/algorithm/unique
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cctype>
int main()
{
// remove duplicate elements
std::vector<int> v{1,2,3,1,2,3,3,4,5,4,5,6,7};
std::sort(v.begin(), v.end()); // 1 1 2 2 3 3 3 4 4 5 5 6 7
auto last = std::unique(v.begin(), v.end());
// v now holds {1 2 3 4 5 6 7 x x x x x x}, where 'x' is indeterminate
v.erase(last, v.end());
for (int i : v)
std::cout << i << " ";
std::cout << "\n";
}
增长:
1 2 3 4 5 6 7
