29

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

4

5 回答 5

48

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

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

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

于 2010-03-25T18:34:28.523 回答
22

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

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

于 2010-03-25T18:42:31.487 回答
4

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

于 2010-03-25T18:56:27.967 回答
3

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

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

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

于 2010-03-25T18:57:43.797 回答
2

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

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

于 2010-03-25T18:34:24.017 回答