Introduction

After sequential containers, let's enter the world of associative containers and learn about the principle of key/value pairs.

We'll cover the following

C++ has eight different associative containers. Four of them are associative containers with sorted keys: std::set, std::map, std::multiset and std::multimap. The other four are associative containers with unsorted keys: std::unordered_set, std::unordered_map, std::unordered_multiset and std::unordered_multimap. The associative containers are special containers. That means they support all of the operations described in the chapter Interface of all containers.

Overview

All eight ordered and unordered containers have in common that they associate a key with a value. You can use the key to get the value. To get a classification of the associative containers, three simple questions need to be answered:

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

The following table with 232^3 = 8 rows give the answers to the three questions. I answer a fourth question in the table. How fast is the access time of a key in the best case?

Associative container Sorted Associated value More identical keys Access time
std::set yes no no logarithmic
std::unordered_set no no no constant
std::map yes yes no logarithmic
std::unordered_map no yes no constant
std::multiset yes no yes logarithmic
std::unordered_multiset no no yes constant
std::multimap yes yes yes logarithmic
std::unordered_multimap no yes yes constant

Characteristics for associative containers

Since C++98, C++ has ordered associative containers; with C++11, C++ has in addition unordered associative containers. Both classes have a very similar interface. That’s the reason that the following code sample is identical for std::map and std::unordered_map. To be more precise, the interface of std::unordered_map is a superset of the interface of std::map. The same holds for the remaining three unordered associative containers. So the porting of your code from the ordered to unordered containers is quite easy.

You can initialize the containers with an initialiser list and add new elements with the index operator. To access the first element of the key/value pair p, you have p.first, and for the second element, you have p.second. p.first is the key and p.second is the associated value of the pair.

Get hands-on with 1000+ tech skills courses.