C++ STL 映射:访问时间是 O(1) 吗? [英] C++ STL map: is access time O(1)?

问题描述

键查找std::map O(1) 吗?我以为是，直到我想多了.它基于树实现，所以查找时间应该是 O(log N)，对吗?

Is key look up on std::map O(1)? I thought it was until I thought about it more. It is based on a tree implementation so the lookup time should be O(log N), correct?

而且，是否有可能让 O(1) 查找字符串键，std::unordered_map 也许?

And, is it possible to have O(1) look up on string key, std::unordered_map perhaps?

推荐答案

std::map 是 O(log N)(容器大小的对数).

The complexity of lookup for std::map is O(log N) (logarithmic in the size of the container).

根据 C++11 标准中关于 std::map::operator [] 的第 23.4.4.3/4 段:

Per Paragraph 23.4.4.3/4 of the C++11 Standard on std::map::operator []:

复杂度:对数.

std::unordered_map 查找的复杂性 在平均情况下是 O(1)(常数)，在最坏情况下是 O(N)(线性).

The complexity of lookup for std::unordered_map is O(1) (constant) in the average case, and O(N) (linear) in the worst case.

根据 C++11 标准第 23.5.4.3/4 段关于 std::unordered_map::operator []

Per Paragraph 23.5.4.3/4 of the C++11 Standard on std::unordered_map::operator []

复杂度:平均情况 O(1)，最坏情况 O(size()).

Complexity: Average case O(1), worst case O(size()).

注意:

如果您的问题只与计算复杂性有关，那么上面写的内容应该可以回答它.事实上，一个操作的计算复杂度是根据容器的大小(它包含的元素数量)来衡量的.

If your question is only concerned with computational complexity, then what written above should answer it. The computational complexity of an operation, in fact, is measured in terms of the size of the container (the number of elements it contains).

但是，如果您正在寻找一种在使用字符串键的容器上执行 O(1) 查找的方法，并且查找的复杂性相对于字符串的长度是恒定的 而不是容器的大小，那么答案是 std::unordered_map 不符合您的要求.

However, if you are looking for a way to perform O(1) lookup on a container that uses string keys, and where the complexity of the lookup is constant with respect to the length of the string rather than to the size of the container, then the answer is that std::unordered_map won't meet your requirements.

为了查找键，首先需要生成它的哈希值；当键是字符串时，此操作本身可能与字符串的大小呈线性关系.然后，实现必须将键与同一个桶中的所有字符串键进行比较，并且这些比较中的每一个都与这些字符串的大小呈线性关系.

In order to lookup a key, it is first necessary to produce a hash of it; when the key is a string, this operation itself could be linear in the size of the string. Then, the implementation has to compare the key to all the string keys in the same bucket, and each of these comparisons is in turn linear in the size of those strings.

这篇关于C++ STL 映射:访问时间是 O(1) 吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！