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 .

I believe `std::map` is commonly implemented using a [Red-black tree](http://en.wikipedia.org/wiki/Red%E2%80%93black_tree) and `std::unordered_map` is a [Hash table](http://en.wikipedia.org/wiki/Hash_table). — Blastfurnace, Jul 23 '13 at 14:10
since it is a template, the source code must be available to the compiler. You find it in the header `` - where that is, depends on your compiler and installation. — Arne Mertz, Jul 23 '13 at 14:11
You can't use hashing for `map`, since the keys must be ordered. Binary search trees are common; specifically, the GNU and (I think) MS implementations use a red-black tree. Hashing is used for `unordered_map` (or `hash_map`, as it was known in the prehistoric STL). — Mike Seymour, Jul 23 '13 at 14:14
And better still to search on SO - http://stackoverflow.com/questions/5288320/why-is-stdmap-implemented-as-red-black-tree — SChepurin, Jul 23 '13 at 14:18
Note that a number of binary search trees (such as Splay Tree) cannot be used because of the complexity or behavior the Standard mandates for some operations. However, any AVL tree or Red-Black tree should in theory be fine. — Matthieu M., Jul 23 '13 at 14:20

score 9 · Answer 1 · answered Jul 23 '13 at 14:21

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.

score 3 · Answer 2 · answered Jan 26 '20 at 09:33

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>

score 1 · Answer 3 · answered Jul 23 '22 at 06:20

std::map is based on Balanced Binary Search Tree, example, AVL Tree and Red Black Tree. Worst Case Complexity of searching an element is O(log(n)). During the insertion of keys, comparison is done in balanced binary search tree to find the correct position of key. As the tree is balanced, maximum comparisons done during insertions would be maximum height of tree which is O(log(n)).

std::unordered_map is based on Hash Table. Average Case complexity of searching an element is O(1) but worst case complexity is still O(n) because collisions can happen if multiple keys mapped to same location in Hash Table.

Internal Implementation of STL::MAP in C++

3 Answers3