associative containers

When you access an element outside a container of the STL, the result is not so promising. You effect may be an error or undefined behaviour. Undefined behaviour 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. 

The hash function maps a potential 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 reason for the constant access time (best cast) of the unordered associative containers are the hash functions. As ever, C++ offers a lot of ways to adjust the behaviour of the hash functions. On one hand, C++ has a lot of different hash functions; on the other hand, you can define your own 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 at 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 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.