C++的std :: unordered_map复杂

我读过很多关于unordered_map（C++ 11）时间复杂度计算器在这里，但我还没有找到我的问题的答案。C++的std :: unordered_map复杂

让我们整（只是举例）假设索引：

插入/在功能不断地努力（平均时间），所以这个例子将采取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}例如可能需要长达百万迭代（如果阵列表示）

是否有任何其他的容器，其可以线性迭代和值由给定的密钥访问不断？

什么我真正需要的是（伪）

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

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

来源

2013-10-26 petrbel

如果您担心枚举需要走过您已经*插入到容器中的配对，请放心。决定使用一个普通的'map' vs'unordered_map'应该基于你是否需要一个相对严格的弱键排序*保留*。如果你这样做，你需要一个定期的“地图”。如果你不这样做，'unordered_map'是最合理的选择（只要密钥可以散列到合理的分布）。 – WhozCraig

@WhozCraig：在选择'map'或'unordered_map'时要考虑的另一个功能因素是在'insert' /'emplace' /'['''触发重新哈希处理过程中后者对现有迭代器/引用/指针的无效是否可接受， '性能差异*倾向于'在unordered_map'有利的情况下，但应该由那些其分析器/仪器设备说明必须真正在意的人来衡量。 –

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

来源

2013-10-26 18:56:04

我似乎无法找到增量的复杂性要求（也没有提及这个问题）。你有引用吗？ – jxh

根据SGI的'前向迭代器'概念*，前向迭代器操作的复杂性保证被保证为分期恒定时间*。 C++标准第24.4.4节仅对输入，前向和双向迭代器[*]说明它们使用++来提供线性时间实现*。 – Escualo

@Arrieta：对于'unordered_map'的情况，“线性”意味着什么是模糊的。它可以表示“桶数”或“容器中的元素”。是否有更具体的表明后者？ – jxh

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

在第一种情况下，您有一个链接列表数组。数组中的每个条目都可以是空的，散列表中的每个条目都会在某个存储桶中。所以迭代是沿着数组走下来，并沿着它的每个非空列表走。显然O（N），但可能会非常低效，这取决于链表如何分配。

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

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

来源

2013-10-26 18:50:59 Barry

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

std::unordered_map元素访问和元素插入的平均复杂度要求为O(1)，最坏的情况为O(N)（参见图3）。第23.5.4.3和23.5.4.4节;第797-798页）。

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

来源

2013-10-26 18:51:05 Escualo

这种复杂性在最坏的情况下也是'O（N）'什么时候使用迭代器？（更具体地说，迭代器递增1？） – memo1288

正如上面已经回答的那样，所有容器的遍历都需要为'O（N）'（一个'std :: unordered_map'迭代器满足前向迭代器概念）。访问**特定**元素或**插入**元素平均为“O（1）”，最坏情况为“O（N）”。 – Escualo

C++的std :: unordered_map复杂

回答

相关问题