我什么时候应该选择一个而不是另一个?对于使用正确的 STL 容器,您有什么建议可以推荐吗?
5 回答
hash_set
是不属于 C++ 标准的扩展。对于 的查找应该是 O(1) 而不是 O(log n) set
,因此在大多数情况下它会更快。
当您遍历容器时,将看到另一个差异。set
将按排序顺序交付内容,而hash_set
基本上是随机的(感谢 Lou Franco)。
编辑:引入的 C++ 标准的 C++11 更新unordered_set
应该是首选而不是hash_set
. 性能将相似,并由标准保证。名称中的“无序”强调迭代它会产生没有特定顺序的结果。
stl::set
实现为二叉搜索树。
hashset
实现为哈希表。
这里的主要问题是许多人stl::set
认为它是一个查找 O(1) 的哈希表,但事实并非如此,也没有。它确实有 O(log(n)) 用于查找。除此之外,阅读二叉树与哈希表以更好地了解数据结构。
要记住的另一件事是,使用 hash_set 你必须提供散列函数,而一个集合只需要一个比较函数 ('<'),它更容易定义(并且为原生类型预定义)。
我认为还没有人回答问题的另一部分。
使用 hash_set 或 unordered_set 的原因通常是 O(1) 查找时间。我说通常是因为每隔一段时间,根据实现,可能必须将散列复制到更大的散列数组,或者散列桶最终可能包含数千个条目。
使用集合的原因是您经常需要集合中最大或最小的成员。哈希没有顺序,因此没有快速找到最小项目的方法。一棵树有秩序,所以最大或最小的很快。O(log n) 对于一个简单的树,O(1) 如果它持有指向末端的指针。
hash_set 将由散列表实现,该表主要具有 O(1) 操作,而集合由具有 O(log n) 操作的某种树(AVL、红黑等)实现,但按排序顺序。
编辑:我写过树是 O(n)。这是完全错误的。