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.

假设按整数索引(仅举例):

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

Insert/at 函数持续工作(平均时间)，所以这个例子需要 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 }
};

我很好奇的是遍历存储在 map 中的所有(未排序的)值需要多长时间 - 例如

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.

推荐答案

不管它们是如何实现的，标准容器都提供了满足迭代器要求的迭代器.增加一个迭代器需要是常数时间，所以遍历 any 标准容器的所有元素是 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屋！