c++ - 为什么C++ STL map容器的复杂度是O(log(n))？

Question

对于 vector 和 list 等 C++ STL 容器，查找元素并插入或删除它们的复杂性是不言自明的。然而，对于 map 容器，尽管我从阅读中知道访问和插入复杂度/性能是 O(log(n))，但我无法弄清楚为什么。显然，我对 map 的理解程度还不够，因此非常感谢对这个主题的一些启发。

Answer 1

映射或集合的元素包含在树结构中；每次检查树的节点时，您都​​会确定要查找/插入的元素是小于还是大于该节点。您需要执行此操作的次数(对于适当平衡的树)是 log2(N)，因为每次比较都会排除一半的可能性。