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

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

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

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

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

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


当前回答

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());

其他回答

unique只删除重复的元素,如果它们是邻居:你必须先对向量排序,然后它才能像你想的那样工作。

unique被定义为稳定的,所以在vector上运行unique之后,它仍然会被排序。

Unique只删除连续的重复元素(这是它在线性时间内运行所必需的),因此应该首先执行排序。调用unique后,它将保持排序。

大部分答案似乎是使用O(nlogn),但使用unordered_set,我们可以将其减少到O(n)。我看到了一些使用集合的解决方案,但我发现了这个解决方案,使用集合和迭代器似乎更优雅。

using Intvec = std::vector<int>;

void remove(Intvec &v) {
    // creating iterator starting with beginning of the vector 
    Intvec::iterator itr = v.begin();
    std::unordered_set<int> s;
    // loops from the beginning to the end of the list 
    for (auto curr = v.begin(); curr != v.end(); ++curr) {
        if (s.insert(*curr).second) { // if the 0 curr already exist in the set
            *itr++ = *curr; // adding a position to the iterator 
        }
    }
    // erasing repeating positions in the set 
    v.erase(itr, v.end());
}
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>。

你可以这样做:

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