C++ STL映射:访问时间是O(1)吗？
C++ STL映射:访问时间是O(1)吗？
提问于 2013-04-18 03:07:27
关键字查找在std::map O(1)上吗？我一直以为是这样的，直到我想得更多。它是基于树实现的，所以查找时间应该是O(log )，对吗？
还有，有没有可能让O(1)查找字符串键，也许是std::unordered_map？
回答 2
Stack Overflow用户
发布于 2013-04-18 03:08:33
是的，确实，如果有太多的散列冲突，std::map将是O(log N)，而std::unordered_map将具有平均恒定时间复杂度，并且在最坏的情况下是O(N)。
Stack Overflow用户
发布于 2018-10-28 23:57:55
基本来说，std::map是使用红黑树实现的。在红黑树中，插入和删除操作需要O(LogN)时间，所以在std::map中，复杂度是每个元素的O(LogN)。
std::unodered_map采用散列算法实现，每次操作耗时为O(1)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/16068151
复制相关文章
相似问题