C ++ std :: unordered_map复杂性 [英] C++ std::unordered_map complexity

问题描述

我已经阅读了很多关于 unordered_map （c ++）的文章11） 时间复杂度这里是stackoverflow，但我没有找到我的问题的答案。

I've read a lot about unordered_map (c++11) time-complexity here at stackoverflow, but I haven't found the answer for my question.

让我们假设索引by integer（仅举例）：

Let's assume indexing by integer (just for example):

插入/在函数处不断工作（平均时间），所以这个例子需要O（1）

Insert/at functions work constantly (in average time), so this example would take 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次迭代（如果用数组表示）

Can I assume that each stored value is accessed only once (or twice or constant-times)? That would imply that iterate through all values is in N-valued map O(N). The other possibility is that my example with keys {1,10,100000} could take up to 1000000 iteration (if represented by array)

还有其他容器，那个可以线性迭代并且不断地通过给定键访问值吗？

Is there any other container, that can be iterated linearly and value accessed by given key constantly?

我真正需要的是（伪代码）

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

Is std::unordered_map the structure I need?

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

Integer indexing is sufficient, average complexity as well.

推荐答案

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

Regardless of how they're implemented, standard containers provide iterators that meet the iterator requirements. Incrementing an iterator is required to be constant time, so iterating through all the elements of any standard container is O(N).

这篇关于C ++ std :: unordered_map复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！