C++ std::map is an associative container, allowing you to store keys associated with values, for easy and efficient retrieval.
It is part of the containers library of C++, as can be seen in cppreference.
You probably know already of std::vector (contiguous storage container) and std::list, both are Sequence containers (as also std::array and std::deque).
Let’s build an example using std::map
If you refer to https://www.incredibuild.com/incredibuild-version-history you will get a changelog of how our system was built over time. Let us say I am asking you to create a data structure to model this changelog. You come up with something along the lines of a linked list. I am impressed since you anticipated the change when version 9.4.6 comes out already.
What information would you model in each of the nodes of the linked list? I would say:
- Version number
- Release date
- Changelog Text
I know that changelogs are sequential in the way they come out. But when I need to retrieve the information about a changelog that happened many moons ago, say for version 4.5, I have to sequentially traverse the list looking for it. This is inefficient. I need a fast way to retrieve information about a changelog given its version. This is an excellent use case for a C++ map example.
If I change this data structure to a map with version number as key and other two data points as value
#include <map>
#include <string>
#include <chrono>
using date = std::chrono::time_point<std::chrono::steady_clock>;
std::map<std::string, std::pair<date, std::string>> changelog;How does this data structure look in memory? Rather than a linear linked list, now our data structure becomes a tree (C++ map is stored as a red, black tree although this is an implementation detail of the library writer)
How is the retrieval faster? Rather than going through linearly, the tree just cuts through it. How? See the animation below:
It was easy to add a new changelog to the list that you designed. It was a matter of creating a new changelog node and adjusting some pointers. Whereas in a tree, adding a new changelog might change the structure of the tree. Let us see what changes when I add a new changelog version 9.5 to the map.
Well, that didn’t look too bad, isn’t it? The tree just found a new place for the new changelog 9.5. What happens we go further and add the changelog 9.6?
C++ maps are efficient data structures even for insertion just because the underlying data structure (a red black tree) ‘balances’ itself after every operation if required.
Remember the list data structure you created for changelog? Assume the “many moons ago” version was a beta version and I would like you to mark it as such. You could just iterate through the list, find the node with version number “many moons ago” and just change it to “many moons ago beta”.
This wouldn’t be simple on a map. Keys are immutable in a map. You will have to remove the item and reinsert it with new detail. See the below animation to get a feel as to what internal restructurings the tree has to undergo to achieve this:
Enough theory you say? Show me some C++ map example code you say? Sure. Let us start with fleshing out the changelog data structure using maps. Here is some creation code:
#include <map>
#include <string>
#include <chrono>
using sclock = std::chrono::steady_clock;
using date = std::chrono::time_point<sclock>;
using namespace std::chrono_literals;
using changelog = std::map<std::string, std::pair<date, std::string>>;
int main()
{
changelog incredibuild;
incredibuild["version 3.5.1"] = std::make_pair(date(1267920000s),
"Visual Studio build system support.");
incredibuild["version 3.6.0"] = std::make_pair(date(1305158400s),
"Added support for distributed Visual Studio 2010.");
incredibuild["version 4.6"] = std::make_pair(date(1365811200s),
"Added support for Visual Studio 2012.");
incredibuild["version 5.5"] = std::make_pair(date(1405814400s),
"Added support for Android NDK builds.");
}Here changelog is a map. [pro tip: consider using typedef or the modern alternative “using”, to simplify your type definitions.
What can you do with such a map? Let us try out the CRUD operations. Let us create a new changelog:
incredibuild.insert(std::make_pair("version 9.4.5",
std::make_pair(date(1585094400s),
"IncrediBuild for Unit Tests solution now supports Google Test(GTest) framework.")));I wanted to show two different ways to create items in a map in traditional C++:
- operator []
- insert
What is the difference? The operator[] doesn’t care if the key being added already exists in the map. The insert member function first checks if the key being added already exists in the map, and if present, does not change the map. Because C++ map does not allow for duplicates if there is an existing element it will not insert anything.
In modern C++, there is yet another way to add items to a map. And that is:
- emplace
Using emplace is more efficient since the element is constructed in-place by calling the perfect forwarding constructor.
incredibuild.emplace("version 9.4.5", std::pair<date, std::string>(date(1585094400s),
"IncrediBuild for Unit Tests solution now supports Google Test(GTest) framework."));How to find a changelog by its key in such a map? The traditional way is to use the find member function and check for the validity of the returned iterator. Like so:
auto it = incredibuild.find("version 3.6.0");
if (it != incredibuild.end())
{
// Do something with the found element.
}If you just want to check if a key exists in a map, you can use the count member function:
if (incredibuild.count("version 3.6.0"))
{
// We know the map contains this key...
}Above trick doesn’t actually count, when used on a map, as key is unique in a map (the `count` method is provided for associative containers mainly to for use in multimap).
Since C++20 std::map has the method contains, which would be a better match:
if (incredibuild.contains("version 3.6.0"))
{
// We know the map contains this key...
}Of course, if you need the value, use `find` as seen above.
To remove an element from the map, use the erase member function.
incredibuild.erase("version 3.6.0");To remove all the elements from the map, use the clear member function.
incredibuild.clear();That completes the CRUD code samples for our map. I cannot possibly close the blog post without mentioning the multimap: a map that allows multiple equivalent keys. It is defined in the same header <map > and implemented as binary search trees. We mentioned multimap, though I don’t have C++ multimap example in this blog, the member function usages are similar. I hope you enjoyed this C++ std::map quick intro!
