我需要采取一个c++向量与潜在的很多元素,擦除重复,并排序。

我目前有下面的代码,但它不起作用。

vec.erase(
      std::unique(vec.begin(), vec.end()),
      vec.end());
std::sort(vec.begin(), vec.end());

我怎样才能正确地做到这一点呢?

此外,是先删除副本(类似于上面的编码)还是先执行排序更快?如果我先执行排序,它是否保证在std::unique执行后保持排序?

或者是否有另一种(也许更有效的)方法来完成这一切?


当前回答

这里有一个模板来帮你做这件事:

template<typename T>
void removeDuplicates(std::vector<T>& vec)
{
    std::sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
}

这样称呼它:

removeDuplicates<int>(vectorname);

其他回答

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>。

如果你不想改变元素的顺序,那么你可以尝试这个解决方案:

template <class T>
void RemoveDuplicatesInVector(std::vector<T> & vec)
{
    set<T> values;
    vec.erase(std::remove_if(vec.begin(), vec.end(), [&](const T & value) { return !values.insert(value).second; }), vec.end());
}

取决于用例。如果你期望有少于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;
}
std::set<int> s;
std::for_each(v.cbegin(), v.cend(), [&s](int val){s.insert(val);});
v.clear();
std::copy(s.cbegin(), s.cend(), v.cbegin());

使用Ranges v3库,您可以简单地使用

action::unique(vec);

注意,它实际上删除了重复的元素,而不仅仅是移动它们。

不幸的是,动作在c++ 20中没有标准化,因为即使在c++ 20中,范围库的其他部分仍然必须使用原始库。