For this, the final blog post of the Capstone project, I’ve decided to utilize this space and time to gain a deeper understanding of maps and, more specifically, the boost container called flat_map.
Recently in the Mahjong codebase I’ve been working with nested maps and accessing data stored in a nested map structure. Although maps were obviously a topic covered throughout my CS coursework, I honestly didn’t reach for them too often in my own projects and it took a fair amount of brainpower to unpack both what was in the nested map structure I was looking at and how to get the data from it that I needed.
Fast-forward through conversations with engineers, cppreference reading, and a supremely helpful video about maps in C++ from the Cherno and I succeeded in strengthening my understanding of maps, how to use them, and when to reach for them. But then, as often happens, my mentor/sensei asked me, “why do you think we’re using a boost container flat_map instead of just std::map?” to which, in the moment, I could only make assumptions and guesses around optimization, but nothing concrete. Back to the books for me!
First off, what the heck is a boost container flat_map? A flat_map is “an associative container that supports unique keys and provides fast retrieval of values of another type T based on the keys” (source). That sure sounds like a map… 🧐 Like std::map, flat_map also supports random access iterators.
Where I started to uncover some differences is in the following:
- flat_map <Key, T> has a value_type of std::pair<Key, T> whereas std::map<Key,T> has a value_type of std::pair<const Key, T>
- flat_map is implemented like an ordered vector, which means that insertion of new elements will invalidate previous iterators and references
- Random insertion into a std::map is faster than random insertion into flat_map (source)
- Random search between the two containers is comparable, though there is some debate that flat_map can be made faster and std::map cannot (source)
None of this necessarily answered my sensei’s question of why use a flat_map vs. a map. Thankfully though, a thorough and multiply cited above Stack Overflow post uncovered the answer to my query!
One very important, significant advantage of a boost container flat_map over std::map is the speed with which a flat_map can be iterated over. Although a std::map would work for the specific use case in our Mahjong game where we use a flat_map, the fact that our nested map structure needs to be iterated over in a couple of different places in the game to get the data we need, a flat_map is a much better choice because that iteration can be optimized.
Of course this is part of the job of a software engineer, however it’s still amazing to me that someone knew to or at least took the time to look into making that design decision. I am such a novice and constantly humbled by the intelligence and experience of my colleagues. It’s an incredible honor to work and learn from them, and I am eternally eager to continue growing in this field.
