c++ - 有效地删除 C++ STL 向量中的双重条目？

Question

可能重复：
C++ 删除向量中的重复条目

我需要删除 C++ STL 向量中的双重条目。重要的一点是结果向量中元素的顺序必须与输入向量中的顺序相同。有没有一种算法（例如在stl，boost）可以做到这一点？

Answer 1

这里有两种可能的情况：向量已经排序或者没有。

如果是，std::erase并且std::unique可以轻松解决此问题，如其他答案所示。

如果不是，那么您可以实现目标

v.erase(std::remove_if(v.begin(), v.end(), predicate), v.end());

但是有一个问题，具体说明predicate并非易事：它是一个接受一个参数（要考虑的值）的函数，它需要回答“向量前面是否有任何相等的值？”的问题。由于没有告诉您提供的参数在向量中的确切位置，这意味着您必须保持相当多的手动状态才能回答这个问题。

这里一个方便的选择是使用 anstd::set来完成一些繁重的工作：

std::set<decltype(v)::value_type> set(v.begin(), v.end());
v.erase(
    std::remove_if(
        v.begin(), 
        v.end(), 
        [&set] (decltype(v)::value_type item) { return !set.erase(item); }), 
    v.end());

这样做是std::set用向量中的值预先填充一个，然后通过查看它是否已从集合中删除来检查之前是否已经看到过一个项目。这样，结果将仅保留输入中比较相等的每组项目中的第一项。

看到它在行动。

Answer 2

如果你的向量没有排序，因此你不能只使用std::unique（同样不能排序会破坏你的订单），你可以使用类似这个函数的东西（使用 C++11 lambdas）：

template<typename FwdIt> FwdIt unordered_unique(FwdIt first, FwdIt last)
{
    typedef typename std::iterator_traits<FwdIt>::value_type value_type;
    std::set<value_type> unique;
    return std::remove_if(first, last, [&unique](const value_type &arg) { 
                                           return !unique.insert(arg).second; });
}

可以使用通常的 erase-romve-idiom 调用它：

v.erase(unordered_unique(v.begin(), v.end()), v.end());

当然，在平均情况下，您也可以使用 C++11std::unordered_set而不是 a std::set（当然，对于可散列类型）来避免 O(n log n)。

Answer 3

怎么样std::unique？

auto firstDup = std::unique(myvector.begin(), myvector.end());

Answer 4

接下来使用：
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );