如果我将有序（递增）的元素序列插入到地图中，最终的二叉树会以某种方式优化吗？或者每个元素都会有一个“正确”的孩子？这将使这样的树非常低效，因为那时查找将是线性的。
我找不到任何有关将过程插入 STL 映射的详细信息。
问问题
5646 次
5 回答
23
C++11 标准 (23.1) 规定了关联容器insert和find关联容器的对数复杂度。从两个迭代器构造它们i并j表示[i, j)适当排序的值范围甚至需要具有线性时间复杂度。这是否意味着“最终的二叉树被优化”，或者地图是否完全是二叉树，都没有说明。
但在实践中std::set，std::map和他们的多朋友实际上总是红黑树，因为这是 STL 的原始 HP/SGI 参考实现所具有的，并且我所知道的所有现代 C++ 库都派生自该实现。
于 2012-05-03T09:20:20.343 回答
4
一般来说，astd::map是使用红黑树实现的，它是自平衡的。所以是的，它已经过优化。
如果插入有序数据，自平衡可能会花费更少，因为节点之间的交换不会那么频繁。
于 2012-05-03T09:14:36.040 回答
1
C++ 标准要求 std::map 中任何元素的对数访问时间（ISO/IEC 14882 的 23.4.4.3），因此 std::map 必须实现为自平衡树。
于 2012-05-03T09:36:57.980 回答
0
并且通常会进行树平衡set，map因此 find 是 O(log n)。此处显示了许多操作的复杂性：
http ://www.cplusplus.com/reference/stl/
于 2012-05-03T09:17:47.430 回答
0
已优化！
查看SGI 的标准模板库程序员指南。您会发现以下用于插入和查找元素的复杂性规范：
- 插入范围的平均复杂度最多为 O(N * log(size() + N))，
- 其中 N 是 j - i。find 的平均复杂度最多为对数。
于 2012-05-03T09:27:14.540 回答