C++ std::unordered_map复杂度

Question

我在堆栈溢出网站上读了很多关于time-complexity ( 地图 (c++11) )的文章，但是我还没有找到问题的答案。

让我们假设按整数进行索引(例如)：

Insert/at函数持续工作(平均时间)，因此本例将采用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_map元素访问和元素插入需要具有平均复杂度O(1)和O(N)最坏情况(cf )。第23.5.4.3和23.5.4.4节；第797-798页)。

特定的实现(即特定供应商对标准库的实现)可以选择他们想要的任何数据结构。然而，要符合标准，它们的复杂性必须至少与指定的相同。

Answer 3

哈希表的实现有几种不同的方式，如果您感兴趣，我建议您阅读更多哈希表，但主要的两种方法是通过链接和开放寻址。

在第一种情况下，您有一个链接列表数组。数组中的每个条目都可以是空的，哈希表中的每一项都在某个桶中。所以迭代是沿着数组走，然后沿着数组中的每个非空列表走下去。显然O(N)，但可能是非常低的内存效率取决于链表本身是如何分配的。

在第二种情况下，您只有一个非常大的数组，它将有大量的空槽。在这里，迭代显然是线性的，但是如果表大部分是空的(这应该是为了查找目的)，则可能效率低下，因为实际存在的元素将位于不同的缓存行中。

不管是哪种方式，你都要进行线性迭代，并且只需要接触每一个元素一次。请注意，对于std::map也是如此，迭代也是线性的。但是在映射的情况下，迭代肯定要比迭代向量效率低得多，所以请记住这一点。如果您的用例需要快速查找和快速迭代，如果您在前面插入了所有元素，并且从不擦除，那么实际拥有地图和向量可能会好得多。为增加的性能占用额外的空间。