15

我在 stackoverflow 上阅读了很多关于unordered_map (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 是我需要的结构吗？

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

4

3 回答 3

18

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

于 2013-10-26T18:56:04.923 回答
4

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

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

特定的实现（即标准库的特定供应商的实现）可以选择他们想要的任何数据结构。但是，要符合标准，它们的复杂性必须至少符合规定。

于 2013-10-26T18:51:05.637 回答
3

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

在第一种情况下，您有一个链表数组。数组中的每个条目都可以是空的，哈希表中的每个项目都将位于某个桶中。所以迭代是遍历数组，遍历其中的每个非空列表。显然是 O(N)，但根据链表本身的分配方式，可能内存效率非常低。

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

无论哪种方式，您都将进行线性迭代，并且您将恰好接触每个元素一次。请注意，这也是如此，std::map那里的迭代也将是线性的。但是在地图的情况下，迭代肯定会比迭代向量的效率低得多，所以请记住这一点。如果您的用例涉及需要快速查找和快速迭代，如果您预先插入所有元素并且从不擦除，那么实际上同时拥有地图和矢量可能会好得多。为额外的性能腾出额外的空间。

于 2013-10-26T18:50:59.230 回答