我需要采取一个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);

其他回答

效率是一个复杂的概念。有时间和空间的考虑,以及一般的测量(你只能得到模糊的答案,如O(n))和特定的(例如冒泡排序可以比快速排序快得多,这取决于输入特征)。

如果你有相对较少的副本,那么排序,然后唯一和擦除似乎是要走的路。如果您有相对较多的副本,则从向量创建一个集合,并让它完成繁重的工作,可以轻松击败它。

也不要只关注时间效率。Sort+unique+erase操作在O(1)空间,而set构造操作在O(n)空间。而且这两种方法都不能直接用于map-reduce并行化(对于真正庞大的数据集)。

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

unique被定义为稳定的,所以在vector上运行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());
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;
}

如果您正在寻找性能并使用std::vector,我推荐使用本文档链接提供的方法。

std::vector<int> myvector{10,20,20,20,30,30,20,20,10};             // 10 20 20 20 30 30 20 20 10
std::sort(myvector.begin(), myvector.end() );
const auto& it = std::unique (myvector.begin(), myvector.end());   // 10 20 30 ?  ?  ?  ?  ?  ?
                                                                   //          ^
myvector.resize( std::distance(myvector.begin(),it) ); // 10 20 30