Associative Containers

When you access an element outside a container of the STL, the result is not so promising. Your effect may be an error or undefined behavior. Undefined behavior means all bets are open.

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.

My last German post C++ Core Guidelines: To Switch or not to Switch, that is the Question got a lot of attention. To use a hash table instead of a switch statement seems to be a highly emotional topic. So I change my original plan. Today, I will present different kinds of control structures. I will start with the if and switch statements, continue with the hash table, and end with dynamic and static polymorphism. Additionally, I will mark a few remarks about performance and maintainability. 

C++11 has eight associative containers. With C++17, you can more comfortably insert new elements into them, merge existing associative containers, or move elements from one container into another if they are similar. But that is not all. The access to the associative and sequential containers was unified.

My favorite example, the dispatch table, shows how nicely the features in modern C++ work together. A dispatch table is a table of pointers to functions. In my case, it is a table of handles for polymorphic function wrappers.

The hash function maps a potentially infinite number of keys on a finite number of buckets. What is the strategy of the C++ runtime and how can you tailor it to your needs, that is what this article is all about.

The hash function is responsible for the unordered associative containers' constant access time (best cast). As ever, C++ offers many ways to adjust the behavior of the hash functions. On the one hand, C++ has a lot of different hash functions; on the other hand, you can define your hash function. You can even adjust the number of buckets.

Before I take a deeper look insight the interface of the hash tables - officially called unordered associative containers - I will first compare the performance of the associative containers. The best candidates are std::unordered_map and the ordered pendant std::map because both are used most frequently.

We missed the hash table in C++ for a long time. They promise to have constant access time. C++11 has hash tables in four variations. The official name is unordered associative containers. Unofficially, they are called dictionaries or just simple associative arrays.