我需要采取一个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之前进行排序(正如其他答案所指出的那样)才是正确的方法。
其他回答
效率是一个复杂的概念。有时间和空间的考虑，以及一般的测量(你只能得到模糊的答案，如O(n))和特定的(例如冒泡排序可以比快速排序快得多，这取决于输入特征)。
如果你有相对较少的副本，那么排序，然后唯一和擦除似乎是要走的路。如果您有相对较多的副本，则从向量创建一个集合，并让它完成繁重的工作，可以轻松击败它。
也不要只关注时间效率。Sort+unique+erase操作在O(1)空间，而set构造操作在O(n)空间。而且这两种方法都不能直接用于map-reduce并行化(对于真正庞大的数据集)。
下面是使用std::unique()出现重复删除问题的示例。在LINUX机器上，程序崩溃。详情请阅读评论。
// Main10.cpp
//
// Illustration of duplicate delete and memory leak in a vector<int*> after calling std::unique.
// On a LINUX machine, it crashes the progam because of the duplicate delete.
//
// INPUT : {1, 2, 2, 3}
// OUTPUT: {1, 2, 3, 3}
//
// The two 3's are actually pointers to the same 3 integer in the HEAP, which is BAD
// because if you delete both int* pointers, you are deleting the same memory
// location twice.
//
//
// Never mind the fact that we ignore the "dupPosition" returned by std::unique(),
// but in any sensible program that "cleans up after istelf" you want to call deletex
// on all int* poitners to avoid memory leaks.
//
//
// NOW IF you replace std::unique() with ptgi::unique(), all of the the problems disappear.
// Why? Because ptgi:unique merely reshuffles the data:
// OUTPUT: {1, 2, 3, 2}
// The ptgi:unique has swapped the last two elements, so all of the original elements in
// the INPUT are STILL in the OUTPUT.
//
// 130215 dbednar@ptgi.com
//============================================================================
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include "ptgi_unique.hpp"
// functor used by std::unique to remove adjacent elts from vector<int*>
struct EqualToVectorOfIntegerStar: public std::equal_to<int *>
{
bool operator() (const int* arg1, const int* arg2) const
{
return (*arg1 == *arg2);
}
};
void printVector( const std::string& msg, const std::vector<int*>& vnums);
int main()
{
int inums [] = { 1, 2, 2, 3 };
std::vector<int*> vnums;
// convert C array into vector of pointers to integers
for (size_t inx = 0; inx < 4; ++ inx)
vnums.push_back( new int(inums[inx]) );
printVector("BEFORE UNIQ", vnums);
// INPUT : 1, 2A, 2B, 3
std::unique( vnums.begin(), vnums.end(), EqualToVectorOfIntegerStar() );
// OUTPUT: 1, 2A, 3, 3 }
printVector("AFTER UNIQ", vnums);
// now we delete 3 twice, and we have a memory leak because 2B is not deleted.
for (size_t inx = 0; inx < vnums.size(); ++inx)
{
delete(vnums[inx]);
}
}
// print a line of the form "msg: 1,2,3,..,5,6,7\n", where 1..7 are the numbers in vnums vector
// PS: you may pass "hello world" (const char *) because of implicit (automatic) conversion
// from "const char *" to std::string conversion.
void printVector( const std::string& msg, const std::vector<int*>& vnums)
{
std::cout << msg << ": ";
for (size_t inx = 0; inx < vnums.size(); ++inx)
{
// insert comma separator before current elt, but ONLY after first elt
if (inx > 0)
std::cout << ",";
std::cout << *vnums[inx];
}
std::cout << "\n";
}
我不知道你在用这个干什么，所以我不能100%肯定地说，但通常当我想到“排序的，唯一的”容器时，我想到std::set。它可能更适合你的用例:
std::set<Foo> foos(vec.begin(), vec.end()); // both sorted & unique already
否则，在调用unique之前进行排序(正如其他答案所指出的那样)才是正确的方法。
如前所述，unique需要一个排序的容器。此外，unique实际上并没有从容器中删除元素。相反，它们被复制到末尾，unique返回一个指向第一个重复元素的迭代器，并且您需要调用erase来实际删除这些元素。
假设a是一个向量，使用
a.erase(独特(a.begin (), a.end ()), a.end ());运行时间为O(n)。
