在构建时是否优化了STL映射容器（平衡树）？ [英] Is the STL map container optimized (balanced tree) while constructed?

问题描述

如果我将有序（增加）的元素序列插入到地图中，最终的二叉树会被优化吗？还是每一个元素都有一个孩子对吧？这将使这样的树效率很低，因为然后查找将是线性的。

我找不到任何有关插入的详细信息C ++ 11标准（23.1）强制要求的对数复杂度。

为关联容器插入和 find 。从两个迭代器 i 和 j 构造它们，使 [i，j）表示甚至需要具有线性时间复杂度的值的适当排序的范围。这是否意味着最终的二叉树被优化，或者地图是否是二叉树。留下未指定。

然而，在实践中， std :: set ， std :: map 和他们的多个朋友几乎总是红黑树，因为这是原来的HP / SGI引用的STL实现，以及我知道的所有现代C ++库从这个实现中获得。

If I insert an ordered (increasing) sequence of elements into a map, will the final binary tree be somehow optimized? Or will every element have a child "to it's right"? That would make such a tree very inefficient, since then the lookup would be linear.

I couldn't find any detailed information about the insertion process into STL map.

解决方案

The C++11 standard (23.1) mandates logarithmic complexity for both insert and find for associative containers. Constructing them from two iterators i and j such that [i, j) denotes a suitably sorted range of values is even required to have linear time complexity. Whether that means that "the final binary tree is optimized", or whether maps are binary trees at all, is left unspecified.

In practice, though, std::set, std::map and their multi-friends are virtually always red-black trees, since that's what the original HP/SGI reference implementation of the STL had, and all modern C++ libraries that I know derive from that implementation.

这篇关于在构建时是否优化了STL映射容器（平衡树）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！