有效刪除C++ STL向量中的雙項？

可能重複：
C++ Delete Duplicate Entries in a vector 有效刪除C++ STL向量中的雙項？

我需要在C++ STL向量來刪除重複輸入。重要的一點是，結果向量中元素的順序必須等於輸入向量中的順序。有沒有一個算法（例如在stl，boost）會這樣做？

來源

2012-11-09 Thomas W.

你試過'std :: unique'嗎？ – 2012-11-09 09:09:24

'std :: unique'要求所有的double條目都是連續的。這是我無法完成的假設。 –

這裏有兩種可能的情況：矢量已經排序或者它不是。

如果是，std::erase和std::unique可以很容易地解決這個問題，如其他答案所示。

如果沒有，那麼你可以做實現與

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

的目標，但有在predicate一個問題是不平凡的規定：那就是接受一個參數（要考慮的值）的函數它需要回答這個問題：「在矢量的早期是否有任何相等的值？」。既然你沒有被告知所提供的參數在向量中的確切位置，這意味着你必須保持相當多的手動狀態才能夠回答這個問題。

一個方便的選擇這裏是使用一個std::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與向量中的值，然後檢查是否有項目已看到之前看到它是否已經從集合中刪除。通過這種方式，結果將僅保留每組輸入中比較相等的每組項目中的第一項。

See it in action。

來源

2012-11-09 09:36:28 Jon

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

來源

2012-11-09 09:08:17 Arseniy

這假定矢量是排序的。 – Jon

如何std::unique？

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

來源

2012-11-09 09:10:07 trojanfoe

如果你的載體沒有排序，你因此不能只使用std::unique（和同樣無法對它進行排序這將破壞你的訂單），你可以使用這樣的功能（使用C++ 11 lambda表達式）：

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

它可以調用使用通常的擦除romve-成語：

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

當然，你也可以使用C++ 11的std::unordered_set代替std::set（用於哈希的類型，當然），以獲得離O（n log n）的平均值SE。

來源

2012-11-09 09:44:19

有效刪除C++ STL向量中的雙項？

回答

相關問題