Modern C++ has eight associative containers, but your special friends should be std::map and std::unordered_map. Why? Let me explain it in this post.
In my last post, C++ Core Guidelines: std::array and std::vector are your friends; I stated: In 99 % of your use-cases, you are lovely with a std::array or a std::vector. A similar statement exists for associative containers: In 95 % of your use cases, you are lovely with a std::map or std::unordered_map. In seldom cases, you don’t need the value associated with the key. These are the missing 5 %. Before I begin this post and give an overview and numbers to both associative containers, here is my rule of thumb for today: If you want a container with a key/value association and the keys should be ordered, use std::map; if not, use a std::unordered_map.
Here is the first overview. For more details, please read my previous posts about associative containers.
The eight Variations
To get an ordering into the eight variations of associative containers, you have to answer three questions. Each question can be answered by yes or no. 2 ^ 3 == 8. Here are the three questions:
- Is the container ordered?
- Does the key have an associated value?
- Are several identical keys possible?
And here are the answers.
- When the container is not ordered, it’s called unordered.
- When the key does have a value associated, it’s called map; if not set.
- When the container can have more than one identical key, it’s called multi.
When I speak of the ordered container, I mean the ordering of the keys.
Maybe this taxonomy was too complicated. Let me give you a more straightforward picture.
A Phone Book
The eight variations are just different versions of a phone book. What is a phone book? A phone book is a sequence of key/value pairs. You use the keys (family names) to get the values (phone numbers).
The family names of a phone book can be ordered or unordered; the phone book can have a phone number associated with the family name or not and can have only one or more identical family names. If you want to store your mobile and landline numbers in a phone book, you are pretty happy that you can use two identical keys.
The reason for this post is not to explain the associative containers: The reason is a different one. The access time to an ordered associative container is logarithmic, but the access time to an unordered associative container is amortized constant.
Performance of a std::map and a std::unordered::map
What does amortized constant access time mean for an unordered associative container such as std::unordered_map? It means that your query for a phone number is independent of the size of the phone book. Don’t you believe me? Let me show you a performance test.
I have a phone book with roughly 89,000 entries. I will increase its size successively by ten until it has almost 89,000,000 entries. After each step, I will ask for all its phone numbers. This means I randomly use all family names.
The following image shows you a part of the initial phone book. You can see the name/number pairs separated by a colon and the name separated from the number by a comma.
The program should be pretty easy to read.
Let me start with the main program. I open the file, read the content, create a phone book (std::map or std::unordered_map), get an arbitrary permutation of the family names, and make the performance test finally. Okay, this was too concise.
Line 1 is the most interesting one. A std::unordered_map supports a superset of the interface of a std::map. This makes it quite convenient for me to make my performance test. I first did it by using map = std::map<std::string, int>; and then changed the line to using map = std::unordered_map<std::string, int>;. The according to relations holds for the pairs (std::set/std::unordered_set),(std::mulitset, std::unordered_multiset), and (std::multimap, std::unordered_multimap). I assume the following functions are also quite interesting for you:
- the while loop iterates over all name/number tokens created by the regular expression regColon (line 2)
- each token is separated by a comma (line 3)
- in the end, the name/number pair is added to the phone book (line 4)
- puts all names onto a vector (line 5)
- shuffles the names (line 6)
- asks for each name in the phone book (line 7)
And now, finally, the performance numbers for a std::map and a std::unordered_map.
The screenshots show precisely how big the phone books are. The numbers confirm the access time I showed in the first table: The access time of a std::map depends logarithmic on its size, and the access time of a std::unordered_map is amortised constant. The following plot shows the performance relation between a std::map and a std::unordered_map.
For 100,000 entries, the std::map is three times slower than the std::unordered_map, and for 100,000,000 entries 7 1/2 times slower.
After this slight detour from the C++ core guidelines, I will write in my next post about bounds errors and how to avoid them.
Thanks a lot to my Patreon Supporters: Matt Braun, Roman Postanciuc, Tobias Zindl, G Prvulovic, Reinhold Dröge, Abernitzke, Frank Grimm, Sakib, Broeserl, António Pina, Sergey Agafyin, Андрей Бурмистров, Jake, GS, Lawton Shoemake, Jozo Leko, John Breland, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, Kris Kafka, Mario Luoni, Friedrich Huber, lennonli, Pramod Tikare Muralidhara, Peter Ware, Daniel Hufschläger, Alessandro Pezzato, Bob Perry, Satish Vangipuram, Andi Ireland, Richard Ohnemus, Michael Dunsky, Leo Goodstadt, John Wiederhirn, Yacob Cohen-Arazi, Florian Tischler, Robin Furness, Michael Young, Holger Detering, Bernd Mühlhaus, Matthieu Bolt, Stephen Kelley, Kyle Dean, Tusar Palauri, Dmitry Farberov, Juan Dent, George Liao, Daniel Ceperley, Jon T Hess, Stephen Totten, Wolfgang Fütterer, Matthias Grün, Phillip Diekmann, Ben Atakora, Ann Shatoff, Rob North, Bhavith C Achar, and Marco Parri Empoli.
Thanks, in particular, to Jon Hess, Lakshman, Christian Wittenhorst, Sherhy Pyton, Dendi Suhubdy, Sudhakar Belagurusamy, Richard Sargeant, Rusty Fleming, John Nebel, Mipko, Alicja Kaminska, Slavko Radman, and David Poole.
|My special thanks to Embarcadero|
|My special thanks to PVS-Studio|
|My special thanks to Tipi.build|
|My special thanks to Take Up Code|
I’m happy to give online seminars or face-to-face seminars worldwide. Please call me if you have any questions.
- Embedded Programmierung mit modernem C++ 12.12.2023 – 14.12.2023 (Präsenzschulung, Termingarantie)
Standard Seminars (English/German)
Here is a compilation of my standard seminars. These seminars are only meant to give you a first orientation.
- C++ – The Core Language
- C++ – The Standard Library
- C++ – Compact
- C++11 and C++14
- Concurrency with Modern C++
- Design Pattern and Architectural Pattern with C++
- Embedded Programming with Modern C++
- Generic Programming (Templates) with C++
- Clean Code with Modern C++
- Phone: +49 7472 917441
- Mobil:: +49 176 5506 5086
- Mail: schulung@ModernesCpp.de
- German Seminar Page: www.ModernesCpp.de
- Mentoring Page: www.ModernesCpp.org
Modernes C++ Mentoring,