Member-only story
How is C++ Map implemented?
Understand the underlying data structure of the map and compare it to a hash table.
Overview
In a previous post, I explained how hash table — std::unordered_map is implemented in C++. I also posted a follow-up article explaining how to measure element insertion, retrieval, and deletion performance to demonstrate and understand hash table behavior.
std::map, at first glance, looks very similar to std::unordered_map, the interface is nearly identical and both are of type associative arrays that can hold data in (key, value) pairs.
The main difference between the two is that as the name suggests std::map is an ordered data structure whereas std::unordered_map is not. But, how do you decide which one to use in your application? This article aims to describe the behavior of the Map data structure and compare it to a Hash Table so it’s clear to you which one is a better fit for your application.
How Map is implemented
Internally ordered associative arrays can be implemented by self-balancing binary search trees, usually implemented by red-black trees. There are good articles explaining the red-black tree algorithm on the internet, so I won’t re-explain it in this article. Check out this wikipedia link to get started.
As with a self-balancing binary search tree, insertion and deletion operations on a tree can trigger a height rebalancing process. This is to ensure that the tree does not skew.
There are many choices of algorithms, but red-black trees are usually used in language libraries because they are faster on insertion and deletion because they are not perfectly balanced, for example when compared to AVL trees.
