哪些數據結構在追加重複時提供替換操作？

Question

是否有數據結構可以消除低複雜度的重複？在附加新值時，如果已經有相同的值，則不應該添加。

這可以通過堆實現嗎？

謝謝！

Answer 1

std :: set這樣做。事實上，如果你不希望這種情況發生，你需要切換到multisets。

從集

因爲在一組元件是唯一的，插入操作檢查 的documentation每個插入的元件是否等效於一個元件已在 容器中，並且如果是這樣，該元件沒有插入，返回一個 迭代器到這個存在的元素（如果該函數返回一個值）。

Answer 2

不，我不認爲堆在這個問題上有所幫助。

可能最快的方法是使用散列表。它們可以在C++ 11中或作爲unordered_set在boost中使用（unordered_multiset允許重複）。

第二種方法可能是使用二叉搜索樹，如C++ 98標準std :: set（同樣，multiset允許重複），通常由紅黑樹實現。

第三個但有限的選項是先對元素進行排序，然後刪除現在連續的重複項。只有首先添加所有元素，並且所有查找都在此之後纔可行，這是可行的。否則，你只限於前兩個選項。 C++爲你提供了std :: sort和std :: unique來使用這種方法。

關於服務表現：

• 哈希表：每個接入O（1），假設你有一個好的哈希函數。
• 平衡的二叉搜索樹：最壞情況下的每個訪問O（log n）。
• 排序+刪除重複項：對於所有n個元素O（n * log n），但可能具有比二元樹低的常數因子。