为什么会有人使用set而不是unordered_set?

C ++ 0x引入了unordered_set ,它可以在boost和许多其他地方使用。 我的理解是unordered_setO(1)查找复杂度的散列表。 另一方面, set只不过是一个log(n)查找复杂度的树。 为什么人们会使用set而不是unordered_set 即是否需要set

对于想要遍历集合中的项目的人来说,顺序很重要。

无序集必须以几种方式支付他们的O(1)平均访问时间:

  • set使用较less的内存然后unordered_set存储相同数量的元素。
  • 对于less数元素set查找可能比unordered_set查找更快
  • 即使在unordered_set平均情况下 ,许多操作的速度unordered_set较快,但是它们通常可以保证对于set (例如insert )具有更好的最坏情况的复杂度
  • 如果要按顺序访问这些元素 ,那么对这些元素进行sorting就很有用。
  • 您可以按字典方式将不同的set<<=>>=unordered_set不需要支持这些操作。

每当你喜欢树到一个哈希表。

例如,哈希表在最坏的情况下是“O(n)”。 O(1)是平均情况。 最糟糕的是树木是“O( log n)”。

考虑扫描线algorithm。 这些algorithm会完全失败哈希表,但与平衡的树木漂亮地工作。 给你一个扫描线algorithm的具体例子考虑算命的algorithm。 http://en.wikipedia.org/wiki/Fortune%27s_algorithm

因为std :: set是标准C ++的一部分,而unordered_set不是。 C ++ 0x不是一个标准,也不是Boost。 对于我们很多人来说,便携性是必不可less的,这意味着坚持标准。

还有一件事,除了其他人已经提到的。 尽pipe向unordered_set插入元素的期望分摊复杂度是O(1),但是现在每隔一段时间需要O(n),因为需要重新构造哈希表(桶的数量需要改变) – 即使一个“好”的散列函数。 就像在一个向量中插入一个元素一样,O(n)每隔一段时间,因为底层数组需要重新分配。

插入一个集合总是最多需要O(log n)。 这在一些应用中可能是优选的。

对不起,还有一件事值得注意的是sorting的属性:

如果您想在容器中使用一系列数据 ,例如:您将时间存储在集合中 ,并且您需要2013-01-01到2014-01-01的时间。

对于unordered_set是不可能的。

当然,这个例子对于mapunordered_map之间的用例更有说服力。

如果你想把它转换成不同的格式,我想说,把事情放在关系中是很方便的。

当访问速度更快时,build立索引或创build和/或访问所使用的内存的时间也更长。

如果你想对事物进行sorting,那么你将使用set而不是unordered_set。 订购时使用unordered_set设置存储没有关系。