C++23: Four new Associative Containers

The four associative containers std::flat_map, std::flat_multimap, std::flat_set, and std::flat_multiset in C++23 are a drop-in replacement for the ordered associative containers std::map, std::multimap, std::set, and std::multiset. We have them for two reasons in C++23: memory consumption and performance.

With C++23, we have 12 associative Containers. Twelve? Right!

C++98: std::map, std::set, std::multimap, and std::multiset
C++11: std::unordered_map, std::unordered_set, std::unordered_multimap, and std::unordered_multiset
C++23: std::flat_map, std::flat_set, std::flat_multimap, and std::flat_multiset

Now, I need a systematic and start with the C++98 and C++11 associative containers.

Associative Container

All associative containers have in common that they associate a key with a value. Therefore, you can get the value by using the key. The C++98 associative containers are called ordered associative containers; the C++11 ones are unordered associative containers.

To classify the associative containers, you have to answer three simple questions:

Are the keys sorted?
Does the key have an associated value?
Can a key appear more than once?

The following table with 2^3= 8 rows answers the three questions. I answered a fourth question in the table. How fast is the access time in the average case?

I’d like to give you more information about the associative containers to understand their performance characteristics.cs.

Ordered Associative Containers

The keys of the ordered associative containers are ordered. The smaller relation (<) is used by default, and the containers are sorted in increasing order.

This ordering has interesting consequences.

The key has to support an ordering relation.
Associative containers are typically implemented as red-black trees. These are balanced binary search trees.
The access time to the key and, therefore, to the value is logarithmic.

The most often used ordered associative container is std::map:

Modernes C++ Mentoring

Be part of my mentoring programs:

"Fundamentals for C++ Professionals" (open)

"Design Patterns and Architectural Patterns with C++" (open)

"C++20: Get the Details" (open)

"Concurrency with Modern C++" (open)

Do you want to stay informed: Subscribe.

std::map<int, std::string> int2String{ {3, "three"}, {2, "two"}, {1, "one"},
                                       {5, "five"}, {6, "six"}, {4, "four"}, {7, "seven"} };

The balanced binary search tree may have the following structure:

Unordered Associative Containers

The crucial idea of the unordered associative containers is that the key is mapped onto the bucket with the help of the hash function. The value is just attached to the key.

The unordered associative containers store their keys in buckets. Which bucket the key goes to is due to the hash function, which maps the key to a unique number. This number is modulo-divided by the number of buckets. If different keys are mapped to the same bucket, it’s called a collision. The good hash function equally distributes the keys. The value is just associated with the key.

The usage of the hash function has very important consequences for the unordered associative container.

The hash function for the key must be available.
The keys must support equality comparison to deal with collisions.
The execution time of a hash function is a constant. Therefore, the access time to the keys of an unordered associative container is constant if the keys are equally distributed.

According to std::map, std::unordered_map is the most often used unordered associative container.

std::unordered_map<std::string, int> str2Int{ {"Grimm",491634333356}, {"Grimm-Jaud", 49160123335}, 
                                              {"Schmidt",4913333318},{"Huber",490001326} };

The graphic shows the mapping of the keys to their bucket using the hash function.

Container Adaptors

The flat-ordered associative containers in C++23 have the same interface as their C++98 pendants.

The flat-ordered associative containers are called container adaptors because they require separate sequence containers for their keys and values. This sequence container must support a random access iterator. By default, a std::vector is used, but a std::array, or a std::deque is also valid.

The following code snippet shows the declaration of std::flat_map, and std::flat_set:

template<class Key, class T, 
        class Compare = less<Key>,
        class KeyContainer = vector<Key>, class MappedContainer = vector<T>>
class flat_map;

template<class Key, 
         class Compare = less<Key>, 
         class KeyContainer = vector<Key>>
class flat_set;

The reason for the flat-ordered associative containers is performance.

Comparison of the Flat-Ordered Containers and their Non-Flat Pendants

The flat-ordered associative containers provide different time and space complexities than the ordered ones. They require less memory and are faster to read than their non-flat-ordered pendants. They support a random access iterator.

The non-flat-ordered associative containers improve writing performance if you insert or delete elements. Additionally, they guarantee that the iterators stay valid after inserting or deleting an element and support a bidirectional iterator.

So far, I cannot show you numbers about the flat-ordered associative containers because no compiler supports them. I will update my performance test “More special Friends with std::map and std::unordered_map” if std::flat_map is available.

What’s Next?

A std::mdspan is a non-owning multidimensional view of a contiguous sequence of objects. The contiguous sequence of objects can be a plain C-array, a pointer with a size, a std::array, a std::vector, or a std::string.

Post Views: 6,748

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, 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, Stephen Kelley, Kyle Dean, Tusar Palauri, 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, Marco Parri Empoli, Philipp Lenk, Charles-Jianye Chen, Keith Jeffery,and Matt Godbolt.

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
My special thanks to SHAVEDYAKS