c++ - 追加重复时哪个数据结构提供替换操作？

Question

是否有一种数据结构可以消除复杂度较低的重复项？添加新值时，如果已经存在相同的值，则不应添加。

这可以用堆来实现吗？

谢谢！

Answer 1

std::set 这样做。事实上，如果你不希望这种情况发生，你需要切换到多组。

从集合的文档

因为集合中的元素是唯一的，所以插入操作检查每个插入的元素是否与容器中已有的元素等价，如果是，则不插入该元素，返回一个迭代器到这个现有元素（如果函数返回值）。

Answer 2

不，我不认为堆有助于解决这个问题。

可能最快的方法是使用哈希表。它们在 C++11 或 Boost 中作为 unordered_set 可用（尽管 unordered_multiset 允许重复）。

第二种方法可能是使用二叉搜索树，如 C++98 标准 std::set（同样，multiset 允许重复），它通常由红黑树实现。

第三个但有限的选择是首先对元素进行排序，然后删除重复项，这些重复项现在是连续的。仅当您首先添加所有元素并在此之后进行所有查找时，这才是可行的。否则，您将仅限于前两个选项。C++ 为您提供了 std::sort 和 std::unique 来使用这种方法。

关于性能：

• 哈希表：每次访问 O(1)，假设你有一个好的哈希函数。
• 平衡二叉搜索树：最坏情况下每次访问 O(log n)。
• 排序 + 删除重复项：对于所有 n 个元素 O(n * log n)，但可能具有比二叉树更低的常数因子。