c++ - C ++ STL中的set和hashset有什么区别？

Question

我什么时候应该选择一个而不是另一个？对于使用正确的 STL 容器，您有什么建议可以推荐吗？

Answer 1

hash_set是不属于 C++ 标准的扩展。对于 的查找应该是 O(1) 而不是 O(log n) set，因此在大多数情况下它会更快。

当您遍历容器时，将看到另一个差异。set将按排序顺序交付内容，而hash_set基本上是随机的（感谢 Lou Franco）。

编辑：引入的 C++ 标准的 C++11 更新unordered_set应该是首选而不是hash_set. 性能将相似，并由标准保证。名称中的“无序”强调迭代它会产生没有特定顺序的结果。

Answer 2

stl::set实现为二叉搜索树。 hashset实现为哈希表。

这里的主要问题是许多人stl::set认为它是一个查找 O(1) 的哈希表，但事实并非如此，也没有。它确实有 O(log(n)) 用于查找。除此之外，阅读二叉树与哈希表以更好地了解数据结构。

Answer 3

要记住的另一件事是，使用 hash_set 你必须提供散列函数，而一个集合只需要一个比较函数 ('<')，它更容易定义（并且为原生类型预定义）。

Answer 4

我认为还没有人回答问题的另一部分。

使用 hash_set 或 unordered_set 的原因通常是 O(1) 查找时间。我说通常是因为每隔一段时间，根据实现，可能必须将散列复制到更大的散列数组，或者散列桶最终可能包含数千个条目。

使用集合的原因是您经常需要集合中最大或最小的成员。哈希没有顺序，因此没有快速找到最小项目的方法。一棵树有秩序，所以最大或最小的很快。O(log n) 对于一个简单的树，O(1) 如果它持有指向末端的指针。

Answer 5

hash_set 将由散列表实现，该表主要具有 O(1) 操作，而集合由具有 O(log n) 操作的某种树（AVL、红黑等）实现，但按排序顺序。

编辑：我写过树是 O(n)。这是完全错误的。