为什么C ++ STL映射容器O（log（n））的复杂性？ [英] Why is the complexity of the C++ STL map container O(log(n))?

问题描述

对于C ++ STL容器，例如 vector 和 list ，查找元素和插入或删除元素的复杂性是不言自明的。然而，对于映射容器，即使我从阅读中知道访问和插入复杂性/性能是O（log（n）），我无法解决为什么。我显然不太了解地图，所以对这个话题的启发将会非常感激。

For C++ STL containers such as vector and list, the complexity of finding elements and inserting or removing them is self-explanatory. However, for the map container, even though I know from my reading that the access and insertion complexity/performance is O(log(n)), I can't work out why. I clearly don't understand maps as much as I need to, so some enlightenment on this topic would be very much appreciated.

推荐答案

地图或集合的元素包含在树结构中;每次检查树的节点时，都可以确定要尝试查找/插入的元素是否小于或大于节点。您需要执行此操作的次数（适合平衡树）为log2（N），因为每次比较都会抛出一半的可能性。

The elements of a map or set are contained in a tree structure; every time you examine a node of the tree, you determine if the element you're trying to find/insert is less than or greater than the node. The number of times you need to do this (for a properly balanced tree) is log2(N) because each comparison throws out half of the possibilities.

这篇关于为什么C ++ STL映射容器O（log（n））的复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！