c++ - 迭代 unordered_map 的复杂性是什么

Question

遍历使用散列和链接实现的 unordered_map 的复杂性是多少？具体来说，这是否涉及遍历所有存储桶，在这种情况下，复杂性是O(Buckets + NElements)理想的，例如O(NElements)

标签： c++c++11unordered-map

Answer 1

迭代的复杂性是unordered_map多少？

O(N) 其中 N 是存储的元素数。标准中最相关的部分：

迭代器的所有类别只需要在恒定时间内（摊销）对给定类别可实现的那些函数。因此，迭代器的需求表没有复杂性列。

你可以看到更多关于这个 - 和讨论 - 例如这个答案

..使用带有链接的散列实现？

所有无序映射都使用带有链接的散列 - 请参见此处。

具体来说，这是否涉及遍历所有桶，在这种情况下，复杂度是 O(Buckets + NElements) 与理想的，例如 O(NElements)

它做你所说的“理想”。在 GCC 的情况下，桶将迭代器保存到一个单链表中，并且在迭代容器时通常会遍历更短的列表。通常是因为即使不更改默认值max_load_factor()1.0，桶的数量也可能完全等于元素的数量 - 任何比这更多的元素都会触发调整大小。但是，当几乎所有元素都被删除时，迭代的大 O 效率变得更加重要，因为桶的数量不会自动向下调整（即减少）。