Ed *_*ing 10 c++ performance stl map
对于诸如vector和的C++ STL容器list,查找元素以及插入或删除元素的复杂性是不言自明的.但是,对于map容器,即使我从我的阅读中知道访问和插入复杂性/性能是O(log(n)),我也无法理解为什么.我显然不了解我需要的地图,所以对这个主题的一些启示将非常感激.
Mar*_*som 12
地图或集合的元素包含在树结构中; 每次检查树的节点时,都要确定要尝试查找/插入的元素是否小于或大于节点.您需要执行此操作的次数(对于正确平衡的树)是log2(N),因为每次比较都会抛出一半的可能性.