Is the STL map container optimized (balanced tree) while constructed?

Question

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.

Answer 1

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.

Answer 2

In general, a std::map is implemented using a red-black tree, which is self-balancing. So yes, it's optimized.

If you insert ordered data, the self-balancing will probably take less, since swaps between nodes will not be that frequent.