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

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

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

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

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

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


当前回答

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

action::unique(vec);

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

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

其他回答

关于alexK7基准测试。我尝试了它们,得到了类似的结果,但是当值的范围为100万时,使用std::sort (f1)和使用std::unordered_set (f5)的情况产生类似的时间。当取值范围为1000万时,f1比f5快。

如果值的范围是有限的,并且值是无符号int,则可以使用std::vector,其大小对应于给定的范围。代码如下:

void DeleteDuplicates_vector_bool(std::vector<unsigned>& v, unsigned range_size)
{
    std::vector<bool> v1(range_size);
    for (auto& x: v)
    {
       v1[x] = true;    
    }
    v.clear();

    unsigned count = 0;
    for (auto& x: v1)
    {
        if (x)
        {
            v.push_back(count);
        }
        ++count;
    }
}

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

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());
}
void removeDuplicates(std::vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++)
    {
        for (int j = i + 1; j < arr.size(); j++)
        {
            if (arr[i] > arr[j])
            {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
    std::vector<int> y;
    int x = arr[0];
    int i = 0;
    while (i < arr.size())
    {
        if (x != arr[i])
        {
            y.push_back(x);
            x = arr[i];
        }
        i++;
        if (i == arr.size())
            y.push_back(arr[i - 1]);
    }
    arr = y;
}

如果你的类很容易转换为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 结果是一样的

unique只适用于重复元素的连续运行,所以你最好先排序。但是,它是稳定的,所以你的向量是有序的。