c++ - 为什么有人会使用 set 而不是 unordered_set？

Question

C++0x 正在引入 unordered_set，它可以在 boost 和许多其他地方使用。我的理解是 unordered_set 是具有 O(1) 查找复杂度的哈希表。另一方面，set 只不过是一棵具有 log(n) 查找复杂度的树。 为什么会有人使用 set 而不是 unordered_set？即是否需要 set 了？

Answer 1

无序集必须通过以下几种方式为其 O(1) 平均访问时间付费:

• set比 unordered_set 使用 更少的内存存储相同数量的元素。
• 对于少量元素，在 set 中查找可能比 unordered_set 中的查找更快 .
• 尽管 unordered_set 的 平均情况 中许多操作更快，对于 set，它们通常保证具有更好的最坏情况复杂性 (例如 insert )。
• 那个 set如果您想按顺序访问它们，对元素进行排序很有用。
• 您可以按字典顺序比较不同的set与 < , <= , >和 >= . unordered_set不需要 s 来支持这些操作。