遍历C++无序映射的时间复杂度

Question

我知道C++ STL中的unordered_map是由哈希表实现的，包含对应于哈希值的桶(bucket)。插入、删除和元素查找的时间保证为平均常数时间(amortized constant)。然而，我不太理解迭代器在这个数据结构上的工作原理。当我递增迭代器时，它如何知道下一个位置在哪里？使用迭代器遍历unordered_map的时间复杂度是多少？在查找下一个迭代器位置时所需的时间是恒定的吗？我在书The C++ Standard Library: A tutorial and Reference中找到了有关unordered_map内部结构的一些信息，但我没有找到我的问题的答案。希望有人可以帮助！

谢谢。

- eaglesky

---

这篇文章(https://dev59.com/O2Ik5IYBdhLWcg3wE6h8?rq=1)说任何标准容器都必须提供O(1)的迭代器。(我建议删除这个问题，除非它实际上与链接的问题不同)。 - Sam

从其中一个评论中提取了这个内容：“C++标准的24.4.4节”规定了前向迭代器上++运算符的要求。好问题。我喜欢这次旅行。 :) - Sam

@sam 如果这是一个“好”的问题，那么没有理由删除它！如果适用，可以标记为重复。 - C. K. Young

@sam 谢谢你提供的链接！ - eaglesky

Answer 1

哈希表是使用包含链接列表的桶实现的。因此，迭代很容易：

1. 查看当前节点是否有下一个指针。如果有，请转到该指针。
2. 如果当前节点没有下一个指针，请转到下一个具有节点的桶。
3. 如果没有这样的节点，则完成迭代。

(通过查找第一个包含节点的桶来找到第一个节点。)

直观地说，使用上述算法遍历整个哈希表的时间复杂度为O(n)，因此每个“next”操作的平摊常数时间应该是常数时间。

- C. K. Young

---

这就是我要找的答案。谢谢！ - eaglesky

不是精确的O(n)，而是O(N+n)，其中N是桶的数量。这是因为即使桶中没有元素，每个桶都至少需要被访问一次。它们通常相差一个常数因子，这就是为什么这样做没问题的原因。 - EyasSH