我需要采取一个c++向量与潜在的很多元素，擦除重复，并排序。
我目前有下面的代码，但它不起作用。
vec.erase(
std::unique(vec.begin(), vec.end()),
vec.end());
std::sort(vec.begin(), vec.end());
我怎样才能正确地做到这一点呢?
此外，是先删除副本(类似于上面的编码)还是先执行排序更快?如果我先执行排序，它是否保证在std::unique执行后保持排序?
或者是否有另一种(也许更有效的)方法来完成这一切?
当前回答
我不知道你在用这个干什么，所以我不能100%肯定地说，但通常当我想到“排序的，唯一的”容器时，我想到std::set。它可能更适合你的用例:
std::set<Foo> foos(vec.begin(), vec.end()); // both sorted & unique already
否则，在调用unique之前进行排序(正如其他答案所指出的那样)才是正确的方法。
其他回答
你可以这样做:
std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());
unique只适用于重复元素的连续运行，所以你最好先排序。但是，它是稳定的，所以你的向量是有序的。
效率是一个复杂的概念。有时间和空间的考虑，以及一般的测量(你只能得到模糊的答案，如O(n))和特定的(例如冒泡排序可以比快速排序快得多，这取决于输入特征)。
如果你有相对较少的副本，那么排序，然后唯一和擦除似乎是要走的路。如果您有相对较多的副本，则从向量创建一个集合，并让它完成繁重的工作，可以轻松击败它。
也不要只关注时间效率。Sort+unique+erase操作在O(1)空间，而set构造操作在O(n)空间。而且这两种方法都不能直接用于map-reduce并行化(对于真正庞大的数据集)。
更多可理解的代码来自: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
如果你的类很容易转换为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 结果是一样的
