C++ std::unordered_map 复杂度

Question

我已经阅读了很多关于 unordered_map 的内容(c++11) 时间复杂度 在 stackoverflow，但我还没有找到问题的答案。

让我们假设按整数索引(仅作为示例):

Insert/at 函数持续工作(平均时间)，所以这个例子需要 O(1)

std::unordered_map<int, int> mymap = {
            { 1, 1},
            { 100, 2},
            { 100000, 3 }
};

我很好奇的是迭代存储在 map 中的所有(未排序的)值需要多长时间 - 例如

for ( auto it = mymap.begin(); it != mymap.end(); ++it ) { ... }

我可以假设每个存储的值只被访问一次(或两次或常数次)吗？这意味着迭代所有值是在 N 值映射 O(N) 中。另一种可能性是我的带有键 {1,10,100000} 的示例最多可能需要 1000000 次迭代(如果用数组表示)

是否有任何其他容器可以线性迭代并通过给定键不断访问值？

我真正需要的是(伪代码)

myStructure.add(key, value) // O(1)
value = myStructure.at(key) // O(1)
for (auto key : mySructure) {...} // O(1) for each key/value pair = O(N) for N values

std::unordered_map 是我需要的结构吗？

整数索引就足够了，平均复杂度也是如此。

Answer 1

无论它们是如何实现的，标准容器都会提供满足迭代器要求的迭代器。递增迭代器需要是常数时间，因此遍历任何标准容器的所有元素是 O(N)。