C++ STL 映射：访问时间是 O(1) 吗？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16068151/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
C++ STL map: is access time O(1)?
提问by stewart99
Is key look up on std::mapO(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?
关键是在std::mapO(1)上查找吗？我以为是，直到我想多了。它基于树实现，因此查找时间应该是 O(log N)，对吗？
And, is it possible to have O(1) look up on string key, std::unordered_mapperhaps?
并且，是否有可能让 O(1) 查找字符串键std::unordered_map？
回答by Andy Prowl
The complexity of lookup for std::mapis O(log N) (logarithmic in the size of the container).
查找的复杂度std::map为 O(log N)（容器大小的对数）。
Per Paragraph 23.4.4.3/4 of the C++11 Standard on std::map::operator []:
根据 C++11 标准的第 23.4.4.3/4 段std::map::operator []：
Complexity: logarithmic.
复杂度：对数。
The complexity of lookup for std::unordered_mapis O(1) (constant) in the average case, and O(N) (linear) in the worst case.
查找的复杂度std::unordered_map在平均情况下为 O(1)（常数），在最坏情况下为 O(N)（线性）。
Per Paragraph 23.5.4.3/4 of the C++11 Standard on std::unordered_map::operator []
根据 C++11 标准的第 23.5.4.3/4 段 std::unordered_map::operator []
Complexity: Average case O(1), worst case O(
size()).
复杂度：平均情况 O(1)，最坏情况 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 stringrather than to the size of the container, then the answer is that std::unordered_mapwon't meet your requirements.
但是，如果您正在寻找一种在使用字符串键的容器上执行 O(1) 查找的方法，并且查找的复杂性相对于字符串的长度而不是容器的大小是恒定的，那么答案是std::unordered_map不会满足您的要求。
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.
为了查找键，首先需要生成它的散列；当键是字符串时，此操作本身可能与字符串的大小呈线性关系。然后，实现必须将键与同一存储桶中的所有字符串键进行比较，并且这些比较中的每一个都与这些字符串的大小呈线性关系。
回答by Shafik Yaghmour
Yes, indeed std::mapwill be O(log N)and std::unordered_mapwill have average constant-time complexity and O(N)in the worst case if there are too many hash collisions.
是的，确实std::map将会O(log N)并且std::unordered_map将具有平均恒定时间复杂度，并且O(N)在最坏的情况下，如果有太多哈希冲突。
回答by Savaliya Vivek
Basicaly std::map is implimented using red-black tree. In red-black tree insert ans delete operation take O(LogN) time, so in std::map time complexity is O(LogN) of every element.
基本上 std::map 是使用红黑树实现的。在红黑树中插入和删除操作需要 O(LogN) 时间，所以在 std::map 中时间复杂度是每个元素的 O(LogN)。
std::unodered_map is implememted using hashing ,where every operation take O(1) time.
std::unodered_map 使用散列实现，其中每个操作都需要 O(1) 时间。
