如果我将有序(递增)元素序列插入到映射中,最终的二叉树是否会以某种方式进行优化？或者每个元素都会有一个孩子"它是对的"？这会使这样一棵树非常低效,因为那时查找将是线性的.
我找不到有关插入STL地图的过程的详细信息.
Fre*_*Foo 23
C++ 11标准(23.1)规定了对象insert和find容器的对数复杂性.从两个迭代器构造它们i并j使得[i, j)表示的值的适当排序的范围甚至需要具有线性时间复杂度.这是否意味着"最终二叉树被优化",或者地图是否是二进制树,是未指定的.
在实践中,虽然std::set,std::map和他们多的朋友几乎总是红黑树,因为那是STL的原装HP/SGI参考实现了什么,我知道从执行中获取所有现代C++库.