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.
