Associative Containers: Performance Comparison

In 95% of our use-cases, we use std::map or std::unordered_map. In fewer cases, we do not need the value associated with the key. Before we begin this lesson and give an overview of numbers to both associative containers, here is one simple rule to remember:

If we want to have a container with ordered key/value associations, use std::map; if not, use a std::unordered_map.

A Phone Book

The eight variations are like different versions of a phone book. What is a phone book? A phone book is a sequence of key/value pairs. We 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. It can either have only one family name or multiple identical family names. If we want to store our mobile number and our landline number in a phone book, we are using two identical keys.

The reason for this lesson is not to explain the associative containers. Rather, we want to discuss how the access time to an ordered associative container is logarithmic, but the access time to an unordered associative container is amortized constant.