Internal Implementation of STL::MAP in C++

Question

I wanted to know , how is the MAP available in C++ , not MultiMap just simple Map , implemented internally .

What i could best think of is :

For Integer Mapping : A Balanced Binary Search Tree could be used .

For String Mapping : Compressed Trie or something similar could be used .

I am really curious , how is it really implemented in STL Map .Is some hashing function employed or is it something totally different from this .

Answer 1

The ordered containers, including std::map are implemented as balanced binary trees (usually RB trees, but any other balanced tree would fit the requirements).

For this type of questions, the most important piece of information you need is the complexity requirements of each one of the operations in the container, which is what the standard mandates. That is also, the most important answer, that is, as long as the complexity requirements are met, the actual implementation does not really matter.

Answer 2

std::map in c++ are implemented using Red-Black Tree.

Internally, class 'map' inherits '__Tree' class publicly which gives an implementation for Red-Black Tree. See this snipped of 'class map' from <map.h>

This __Tree class is used for map/multimap/set/multiset. See this snippet from 'class __Tree' from <xtree.h>