C++中std::map使用方括号查找已存在元素的时间复杂度

当目标元素已存在时，std::map的operator[]（方括号访问）时间复杂度是O(log n)，和map.find(key)的时间复杂度一致。

原因很明确：std::map底层基于红黑树实现，这是一种有序平衡二叉树结构。无论元素是否存在，使用方括号访问时，都会先执行一次键的查找操作——通过树的遍历定位到目标节点，这一步的时间复杂度是对数级的O(log n)。即使元素已经存在，不会触发新元素的插入，但查找过程的开销依然存在，并不会变成常数时间。

以你给出的示例代码为例：

m[1] = 2;
if (m[1] == 2)
  ...

第二行的m[1]访问，依然会对键1执行一次O(log n)的红黑树查找，找到已存在的节点后返回其值的引用，再进行比较操作。

需要注意的是，这和std::unordered_map不同——unordered_map的operator[]在元素存在时平均时间复杂度是O(1)，因为它底层是哈希表结构。但std::map作为有序容器，所有基于键的查找、访问操作（包括find、operator[]、at()）在元素存在时的时间复杂度都是O(log n)。

内容的提问来源于stack exchange，提问作者The B-52s Bassist