std::map的begin()方法要求常数复杂度是否过于严苛？

std::map 符合C++标准中容器的要求，而容器规范明确要求begin()操作的复杂度为常数时间。但我们知道std::map通常基于自平衡二叉搜索树实现，常规找最左节点的操作是O(log n)复杂度，这就带来了疑问：如何实现常数时间的begin()？标准库实现真的符合要求吗？

实现方式：额外维护最小节点指针 #

主流标准库实现都满足begin()的常数时间要求，核心方案是在树的内部结构中额外维护一个指向最左节点（即容器首个元素）的指针：

• 插入元素时：如果新插入的元素键值比当前最左节点的键更小，直接更新这个指针指向新节点；
• 删除元素时：如果被删除的正是当前最左节点，通过节点的父指针或预存的后继指针，快速定位新的最左节点（无需遍历整棵树）。

调用begin()时，直接返回这个预存指针对应的迭代器，就能做到O(1)的时间复杂度。

很多实现还会同步维护最右节点的指针，用来保证rbegin()等相关操作也达到常数时间。

结论 #

通过这种额外维护节点指针的方式，标准库实现可以轻松满足begin()的常数时间要求，GCC的libstdc++、Clang的libc++、MSVC的STL等主流实现均采用该方案。

内容的提问来源于stack exchange，提问作者Jan Schultke