我需要采取一个c++向量与潜在的很多元素，擦除重复，并排序。
我目前有下面的代码，但它不起作用。
vec.erase(
std::unique(vec.begin(), vec.end()),
vec.end());
std::sort(vec.begin(), vec.end());
我怎样才能正确地做到这一点呢?
此外，是先删除副本(类似于上面的编码)还是先执行排序更快?如果我先执行排序，它是否保证在std::unique执行后保持排序?
或者是否有另一种(也许更有效的)方法来完成这一切?
当前回答
如果你的类很容易转换为int型，并且你有一些内存， Unique可以在没有排序的情况下完成，而且速度快得多:
#include <vector>
#include <stdlib.h>
#include <algorithm>
int main (int argc, char* argv []) {
//vector init
std::vector<int> v (1000000, 0);
std::for_each (v.begin (), v.end (), [] (int& s) {s = rand () %1000;});
std::vector<int> v1 (v);
int beg (0), end (0), duration (0);
beg = clock ();
{
std::sort (v.begin (), v.end ());
auto i (v.begin ());
i = std::unique (v.begin (), v.end ());
if (i != v.end ()) v.erase (i, v.end ());
}
end = clock ();
duration = (int) (end - beg);
std::cout << "\tduration sort + unique == " << duration << std::endl;
int n (0);
duration = 0;
beg = clock ();
std::for_each (v1.begin (), v1.end (), [&n] (const int& s) {if (s >= n) n = s+1;});
std::vector<int> tab (n, 0);
{
auto i (v1.begin ());
std::for_each (v1.begin (), v1.end (), [&i, &tab] (const int& s) {
if (!tab [s]) {
*i++ = s;
++tab [s];
}
});
std::sort (v1.begin (), i);
v1.erase (i, v1.end ());
}
end = clock ();
duration = (int) (end - beg);
std::cout << "\tduration unique + sort == " << duration << std::endl;
if (v == v1) {
std::cout << "and results are same" << std::endl;
}
else {
std::cout << "but result differs" << std::endl;
}
}
典型结果: Duration sort + unique == 38985 持续时间唯一+排序== 2500 结果是一样的
其他回答
我重做了内特·科尔的侧写得到了不同的结果。对于我的测试用例，直接对向量排序总是比使用集合更有效。我添加了一个新的更有效的方法，使用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::vector，我推荐使用本文档链接提供的方法。
std::vector<int> myvector{10,20,20,20,30,30,20,20,10}; // 10 20 20 20 30 30 20 20 10
std::sort(myvector.begin(), myvector.end() );
const auto& it = std::unique (myvector.begin(), myvector.end()); // 10 20 30 ? ? ? ? ? ?
// ^
myvector.resize( std::distance(myvector.begin(),it) ); // 10 20 30
你可以这样做:
std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());
void removeDuplicates(std::vector<int>& arr) {
for (int i = 0; i < arr.size(); i++)
{
for (int j = i + 1; j < arr.size(); j++)
{
if (arr[i] > arr[j])
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
std::vector<int> y;
int x = arr[0];
int i = 0;
while (i < arr.size())
{
if (x != arr[i])
{
y.push_back(x);
x = arr[i];
}
i++;
if (i == arr.size())
y.push_back(arr[i - 1]);
}
arr = y;
}
我不知道你在用这个干什么，所以我不能100%肯定地说，但通常当我想到“排序的，唯一的”容器时，我想到std::set。它可能更适合你的用例:
std::set<Foo> foos(vec.begin(), vec.end()); // both sorted & unique already
否则，在调用unique之前进行排序(正如其他答案所指出的那样)才是正确的方法。
