c++ - STL map 容器在构造时是否优化(平衡树)？

Question

如果我将元素的有序(递增)序列插入到映射中，最终的二叉树会以某种方式得到优化吗？或者每个元素都会有一个“正确”的 child ？这将使这样的树非常低效，因为然后查找将是线性的。

我找不到任何关于插入 STL 映射过程的详细信息。

Answer 1

C++11 标准 (23.1) 要求关联容器的 insert 和 find 的对数复杂度。从两个迭代器 i 和 j 构造它们使得 [i, j) 表示适当排序的值范围甚至需要具有线性时间复杂。这是否意味着“最终的二叉树被优化”，或者 map 是否根本就是二叉树，尚无定论。

但实际上，std::set、std::map 和它们的多友元实际上总是红黑树，因为这是最初的 HP/STL 的 SGI 引用实现以及我所知道的所有现代 C++ 库都源自该实现。