C++ std :: unordered_map复杂性

Question

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

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

Answer 1

无论它们如何实现,标准容器都提供满足迭代器要求的迭代器.递增迭代器需要是恒定时间,因此迭代任何标准容器的所有元素都是O(N).

Answer 2

C++ 标准中指定了所有标准容器的复杂性保证。

std::unordered_mapO(1)元素访问和元素插入要求平均和最坏情况都具有复杂性O(N)（参见第 23.5.4.3 和 23.5.4.4 节；第 797-798 页）。

特定的实现（即标准库的特定供应商的实现）可以选择他们想要的任何数据结构。然而，为了符合该标准，它们的复杂性必须至少达到规定的程度。