我需要采取一个c++向量与潜在的很多元素，擦除重复，并排序。
我目前有下面的代码，但它不起作用。
vec.erase(
std::unique(vec.begin(), vec.end()),
vec.end());
std::sort(vec.begin(), vec.end());
我怎样才能正确地做到这一点呢?
此外，是先删除副本(类似于上面的编码)还是先执行排序更快?如果我先执行排序，它是否保证在std::unique执行后保持排序?
或者是否有另一种(也许更有效的)方法来完成这一切?
当前回答
在调用unique之前需要对它进行排序，因为unique只删除相邻的重复项。
编辑:38秒……
其他回答
我重做了内特·科尔的侧写得到了不同的结果。对于我的测试用例，直接对向量排序总是比使用集合更有效。我添加了一个新的更有效的方法，使用unordered_set。
请记住，unordered_set方法仅适用于您需要唯一和排序的类型的良好哈希函数。对于int型，这很简单!(标准库提供了一个默认的哈希，它只是标识函数。)另外，不要忘记在最后排序，因为unordered_set是无序的:)
我深入研究了set和unordered_set实现，发现构造函数实际上为每个元素构造了一个新节点，然后检查其值以确定是否应该实际插入(至少在Visual Studio实现中是这样)。
以下是5种方法:
f1:只是使用向量，sort + unique
sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );
f2:转换为set(使用构造函数)
set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );
f3:转换为set(手动)
set<int> s;
for (int i : vec)
s.insert(i);
vec.assign( s.begin(), s.end() );
f4:转换为unordered_set(使用构造函数)
unordered_set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );
sort( vec.begin(), vec.end() );
f5:转换为unordered_set(手动)
unordered_set<int> s;
for (int i : vec)
s.insert(i);
vec.assign( s.begin(), s.end() );
sort( vec.begin(), vec.end() );
我在[1,10]，[1,1000]和[1,100000]的范围内随机选择了100,000,000 int的向量进行测试
结果(以秒为单位，越小越好):
range f1 f2 f3 f4 f5
[1,10] 1.6821 7.6804 2.8232 6.2634 0.7980
[1,1000] 5.0773 13.3658 8.2235 7.6884 1.9861
[1,100000] 8.7955 32.1148 26.5485 13.3278 3.9822
你可以这样做:
std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());
大部分答案似乎是使用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());
}
关于alexK7基准测试。我尝试了它们，得到了类似的结果，但是当值的范围为100万时，使用std::sort (f1)和使用std::unordered_set (f5)的情况产生类似的时间。当取值范围为1000万时，f1比f5快。
如果值的范围是有限的，并且值是无符号int，则可以使用std::vector，其大小对应于给定的范围。代码如下:
void DeleteDuplicates_vector_bool(std::vector<unsigned>& v, unsigned range_size)
{
std::vector<bool> v1(range_size);
for (auto& x: v)
{
v1[x] = true;
}
v.clear();
unsigned count = 0;
for (auto& x: v1)
{
if (x)
{
v.push_back(count);
}
++count;
}
}
unique只适用于重复元素的连续运行，所以你最好先排序。但是，它是稳定的，所以你的向量是有序的。
