C ++ STL映射：访问时间为O（1）吗？ [英] C++ STL map: is access time O(1)?

问题描述

键是否在 std :: map O（1）上查找？我以为是直到我进一步考虑为止。它是基于树的实现，因此查找时间应该是O（log N），对吗？

而且，可以让O（1）进行查找字符串键，也许 std :: unordered_map ？

解决方案

查找 std :: map 是O（log N）（容器大小的对数）。

根据C ++ 11标准第23.4.4.3/4段 std :: map :: operator [] ：

Complexity ：对数。

std :: unordered_map 在通常情况下为O（1）（恒定），并且

根据 std的C ++ 11标准的23.5.4.3/4段： ：unordered_map :: operator []

复杂度：平均情况O（1），最坏情况O（ size（））。

注意：

如果您的问题仅涉及计算复杂性，那么上面写的内容应该可以回答。实际上，操作的计算复杂度是根据容器的大小 （其中包含的元素数）来衡量的。

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

<为了查找一个密钥，首先必须产生一个哈希值；当键是字符串时，此操作本身的长度可能是线性的。然后，该实现必须将该键与同一存储桶中的所有字符串键进行比较，并且这些比较中的每一个在这些字符串的大小上都是线性的。

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?

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

解决方案

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

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

Complexity: logarithmic.

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

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

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

NOTE:

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).

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屋！