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

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

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

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

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

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


当前回答

更多可理解的代码来自: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

其他回答

如前所述,unique需要一个排序的容器。此外,unique实际上并没有从容器中删除元素。相反,它们被复制到末尾,unique返回一个指向第一个重复元素的迭代器,并且您需要调用erase来实际删除这些元素。

取决于用例。如果你期望有少于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;
}

我重做了内特·科尔的侧写得到了不同的结果。对于我的测试用例,直接对向量排序总是比使用集合更有效。我添加了一个新的更有效的方法,使用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::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";
}

我同意R. Pate和Todd Gardner的观点;std::set在这里可能是个好主意。即使你在使用向量时遇到了困难,如果你有足够多的副本,你最好创建一个集合来做这些肮脏的工作。

让我们来比较三种方法:

用向量,sort + unique

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

转换为set(手动)

set<int> s;
unsigned size = vec.size();
for( unsigned i = 0; i < size; ++i ) s.insert( vec[i] );
vec.assign( s.begin(), s.end() );

转换为set(使用构造函数)

set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );

下面是它们在重复数量变化时的表现:

总结:当副本的数量足够大时,实际上更快地将数据转换为一个集合,然后将数据转储回一个向量。

出于某种原因,手动进行set转换似乎比使用set构造函数更快——至少在我使用的随机数据上是这样。