相关疑难解决方法(0)

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

我们假设按整数索引(仅举例):

插入/在函数不断工作(平均时间),所以这个例子需要O(1)

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

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

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是我需要的结构吗？

整数索引也足够,平均复杂度也很高.