我需要采取一个c++向量与潜在的很多元素，擦除重复，并排序。
我目前有下面的代码，但它不起作用。
vec.erase(
std::unique(vec.begin(), vec.end()),
vec.end());
std::sort(vec.begin(), vec.end());
我怎样才能正确地做到这一点呢?
此外，是先删除副本(类似于上面的编码)还是先执行排序更快?如果我先执行排序，它是否保证在std::unique执行后保持排序?
或者是否有另一种(也许更有效的)方法来完成这一切?
当前回答
void EraseVectorRepeats(vector <int> & v){
TOP:for(int y=0; y<v.size();++y){
for(int z=0; z<v.size();++z){
if(y==z){ //This if statement makes sure the number that it is on is not erased-just skipped-in order to keep only one copy of a repeated number
continue;}
if(v[y]==v[z]){
v.erase(v.begin()+z); //whenever a number is erased the function goes back to start of the first loop because the size of the vector changes
goto TOP;}}}}
这是我创建的一个函数，你可以用它来删除重复。所需的头文件只有<iostream>和<vector>。
其他回答
unique只删除重复的元素，如果它们是邻居:你必须先对向量排序，然后它才能像你想的那样工作。
unique被定义为稳定的，所以在vector上运行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 结果是一样的
我不知道你在用这个干什么，所以我不能100%肯定地说，但通常当我想到“排序的，唯一的”容器时，我想到std::set。它可能更适合你的用例:
std::set<Foo> foos(vec.begin(), vec.end()); // both sorted & unique already
否则，在调用unique之前进行排序(正如其他答案所指出的那样)才是正确的方法。
取决于用例。如果你期望有少于100个正整数的唯一值，并且你有一个cpu能够处理avx512f指令集，那么你可以以每个元素15个时钟周期或每秒3 -5亿个插入的速度插入元素，通过与一个小型查找表进行简单的比较。
接下来的实现使用CPU寄存器对~50个惟一值进行值查找，并对~1000个惟一值进行L1缓存。对于L1缓存版本，每次插入大约需要160个时钟周期，这相当于大约每秒25M个插入，并且比使用std::set慢。对于只有4个唯一值，它以每个元素5.8个周期的速率插入，高于500M/s。
//g++ 7.4.0
// time measurement taken from another answer
// valid C99 and C++
#include <stdint.h> // <cstdint> is preferred in C++, but stdint.h works.
#ifdef _MSC_VER
# include <intrin.h>
#else
# include <x86intrin.h>
#endif
// optional wrapper if you don't want to just use __rdtsc() everywhere
inline
uint64_t readTSC() {
_mm_lfence(); // optionally wait for earlier insns to retire before reading the clock
uint64_t tsc = __rdtsc();
_mm_lfence(); // optionally block later instructions until rdtsc retires
return tsc;
}
// requires a Nehalem or newer CPU. Not Core2 or earlier. IDK when AMD added it.
inline
uint64_t readTSCp() {
unsigned dummy;
return __rdtscp(&dummy); // waits for earlier insns to retire, but allows later to start
}
#include <iostream>
template<int n>
struct FastUnique
{
public:
FastUnique()
{
it=0;
for(int i=0;i<n;i++)
dict[i]=-1;
}
void insert(const int val)
{
if(!test(dict,val))
dict[it++]=val;
}
const int get(const int index)
{
return dict[index];
}
const int size()
{
return it;
}
private:
int dict[n];
int it;
bool test(const int * dict, const int val)
{
int c=0;
for(int i=0;i<n;i++)
c+=(dict[i]==val);
return c>0;
}
};
int main()
{
std::cout << "Hello, world!\n";
const int n=500000000;
FastUnique<64> fastSet;
auto t= readTSC();
for(int i=0;i<n;i++)
fastSet.insert(i&63);
auto t2=readTSC();
std::cout<<(t2-t)/(double)n<<"cycles per iteration"<<std::endl;
for(int i=0;i<fastSet.size();i++)
std::cout<<fastSet.get(i)<<std::endl;
return 0;
}
unique只适用于重复元素的连续运行，所以你最好先排序。但是，它是稳定的，所以你的向量是有序的。
