Associative Containers: Performance Comparison
Modern C++ has eight associative containers, but we should use std::map and std::unordered_map. Why? Let’s disucss in this lesson.
We'll cover the following
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 astd::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.
Get hands-on with 1400+ tech skills courses.