在使用哈希和链接实现的无序映射中迭代的复杂性是多少？具体来说，这是否涉及遍历所有桶，在这种情况下，复杂性是O(Buckets + NElements)与理想的，例如O(NElements)
在
unordered_map中迭代的复杂性是多少？
O(N(，其中N是存储的元素数。标准中最相关的部分：
所有类别的迭代器只需要那些在恒定时间(摊销(内对给定类别可实现的函数。因此，迭代器的需求表没有复杂性列。
你可以在例如这个答案中看到更多关于这一点和讨论
。。使用哈希和链接实现？
所有无序映射都使用哈希和链接-请参阅此处。
具体来说，这是否涉及遍历所有桶，在这种情况下，复杂性是O(桶+网元(与理想情况，例如O(网元(
它执行您所称的"理想"；。在GCC的情况下，bucket将迭代器保存到一个单链列表中，在容器上迭代时，通常会遍历较短的列表。通常情况下，因为即使不更改默认的max_load_factor()1.0，bucket的数量也可能与元素的数量完全相等——任何超过这个数量的元素都会触发调整大小。但是，当几乎所有元素都被删除时，迭代的大O效率变得更加重要，因为桶的数量不会自动向下调整(即减少(。