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

Question

对于诸如vectorand之类的 C++ STL 容器list，查找元素以及插入或删除元素的复杂性是不言自明的。但是，对于map容器，即使我从阅读中知道访问和插入复杂性/性能是 O(log(n))，我也无法弄清楚为什么。我显然没有像我需要的那样理解地图，因此非常感谢您对这个主题的一些启发。

Answer 1

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

Answer 2

作为 slavik262 点，地图通常使用自平衡的红黑树来实现。检查红黑树的复杂性，例如在维基百科中 我不知道带有二叉树的地图的任何实现；如果 Mark Ransom 知道一个，我很高兴知道是哪一个。