C++ 中集合和哈希集有什么区别？标准格式？
我什么时候应该选择其中之一？ 您是否有任何关于使用正确的 STL 容器的建议？
When should I choose one over the other?
Are there any pointers that you would recommend for using the right STL containers?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
我认为还没有人回答问题的其他部分。
使用 hash_set 或 unordered_set 的原因是查找时间通常为 O(1)。我说“通常”是因为，根据实现的不同，哈希可能必须复制到更大的哈希数组，或者哈希桶最终可能包含数千个条目。
使用集合的原因是您经常需要集合中最大或最小的成员。哈希没有顺序，因此没有快速的方法来找到最小的项目。一棵树是有顺序的，所以最大或最小的速度很快。对于简单的树，O(log n)；如果它保存指向末端的指针，则 O(1)。
I don't think anyone has answered the other part of the question yet.
The reason to use hash_set or unordered_set is the usually O(1) lookup time. I say usually because every so often, depending on implementation, a hash may have to be copied to a larger hash array, or a hash bucket may end up containing thousands of entries.
The reason to use a set is if you often need the largest or smallest member of a set. A hash has no order so there is no quick way to find the smallest item. A tree has order, so largest or smallest is very quick. O(log n) for a simple tree, O(1) if it holds pointers to the ends.
hash_set 将由哈希表实现，其主要具有 O(1) 操作，而集合则由某种类型的树（AVL、红黑等）实现，其具有 O(log n) 操作，但按排序顺序。
编辑：我写过树的复杂度是 O(n)。这是完全错误的。
A hash_set would be implemented by a hash table, which has mostly O(1) operations, whereas a set is implemented by a tree of some sort (AVL, red black, etc.) which have O(log n) operations, but are in sorted order.
Edit: I had written that trees are O(n). That's completely wrong.
hash_set是一个扩展，不属于 C++ 标准的一部分。set的查找时间应该是 O(1) 而不是 O(log n)，因此在大多数情况下会更快。当您迭代容器时，会看到另一个区别。
set将按排序顺序传递内容，而hash_set基本上是随机的（感谢 Lou Franco）。编辑：C++11 对 C++ 标准的更新引入了
unordered_set应该是首选，而不是hash_set。性能将相似并由标准保证。名称中的“无序”强调迭代它不会产生任何特定顺序的结果。hash_setis an extension that is not part of the C++ standard. Lookups should be O(1) rather than O(log n) forset, so it will be faster in most circumstances.Another difference will be seen when you iterate through the containers.
setwill deliver the contents in sorted order, whilehash_setwill be essentially random (Thanks Lou Franco).Edit: The C++11 update to the C++ standard introduced
unordered_setwhich should be preferred instead ofhash_set. The performance will be similar and is guaranteed by the standard. The "unordered" in the name stresses that iterating it will produce results in no particular order.stl::set被实现为二叉搜索树。hashset是作为哈希表实现的。这里的主要问题是，许多人使用
stl::set认为它是一个查找 O(1) 的哈希表，但事实并非如此，也不具备。它确实具有 O(log(n)) 的查找时间。除此之外，请阅读二叉树与哈希表的相关内容，以更好地了解数据结构。stl::setis implemented as a binary search tree.hashsetis implemented as a hash table.The main issue here is that many people use
stl::setthinking it is a hash table with look-up of O(1), which it isn't, and doesn't have. It really has O(log(n)) for look-ups. Other than that, read about binary trees vs hash tables to get a better idea of the data structures.另一件需要记住的事情是，使用 hash_set 时，您必须提供哈希函数，而集合只需要一个比较函数（“<”），该函数更容易定义（并为本机类型预定义）。
Another thing to keep in mind is that with hash_set you have to provide the hash function, whereas a set only requires a comparison function ('<') which is easier to define (and predefined for native types).