Using std::unordered_map to create associative containers

Maps are a form of data structure where every element in the collection is a pair of related values. For example, a character’s equipment set is a common use for a map. It would be a collection of equipment slots, and the item equipped in each one.

Because every item in the map is a pair of two associated objects (eg, an equipment slot, and a piece of equipment in that slot), maps are an example of an associative container.

The two items that make up each pair within the map are commonly called the "key" and "value". Maps are designed such that, if you have a specific key, you can find the associated value quickly.

Because of this property, maps are sometimes also called "dictionaries" in other programming languages.

Maps can either be ordered or unordered. An ordered map means the elements are evaluated in a controllable order when iterated over. That advantage comes with two drawbacks:

• Extra computing resources need to be diverted into maintaining that order, causing a performance impact.
• The type of the key used needs to define what it means to be "in order". If our keys are of type int, it's generally understood what "in order" would look like, but it's less clear what it means to put something like Character or Weapon objects in order.

The need to iterate over a map in a specific order is somewhat uncommon. As a result, unordered maps tend to be much more common, and they're what we'll focus on in this lesson.

Creating Maps

The standard library's implementation of an unordered map is available by including <unordered_map>

1#include <unordered_map>
2

To create a map, we need to provide the type of each key and value. For example, an Equipment map for storing all of a characters equipped items might have a key type of Slot and a value of type Item:

1#include <unordered_map>
2using std::unordered_map, std::cout;
3
4enum class Slot { Chest, Legs, Weapon };
5struct Item { string Name; };
6
7unordered_map<Slot, Item> Equipment;
8

Adding and Accessing Elements in Maps

Access to any element in the map is done using the [] operator, along with the key we want the associated value for:

1Item Pants { "Pants of Invulnerability" };
2Equipment[Slot::Legs] = Pants;
3cout << "I have "
4     << Equipment[Slot::Legs].Name
5     << " on my legs!";
6

Within a std::unordered_map, each pair of elements is a std::pair with the corresponding type.

For example, every element in a map<Slot, Item> is a pair<Slot, Item>.

If we have such a pair, we can add it directly using the insert method.

1Item Sword { "Sword of Poking" };
2pair EquippedWeapon { Slot::Weapon, Sword };
3Equipment.insert(EquippedWeapon);
4
5// We can also create the pair inline
6Item Armour { "Shiny Breastplate" };
7Equipment.insert({ Slot::Chest, Armour });
8
9cout << "I'm wielding a "
10     << Equipment[Slot::Weapon].Name
11     << "!\n";
12
13cout << "I'm wearing a "
14     << Equipment[Slot::Chest].Name
15     << "!\n";
16

If we have these pairs before our map is created, we can also use them to initialise our map:

1Item Sword { "Sword of Poking" };
2pair EquippedWeapon { Slot::Weapon, Sword };
3
4Item Pants { "Pants of Invulnerability" };
5pair EquippedPants { Slot::Legs, Pants };
6
7unordered_map Equipment { EquippedWeapon, EquippedPants };
8

We can also create the items at the same time as the map that will contain them:

1unordered_map Equipment {
2  pair { Slot::Weapon, Item { "Sword of Poking" },
3  pair { Slot::Legs, Item { "Pants of Invulnerability" };
4};
5

In the above example, we never specify the exact type of either our pair or our map. This is another example of class template argument deduction (CTAD). Each pair can infer its required type based on the types of values it is initialised with. The map can, in turn, infer its type from the types of pair it is initialised with.

Finding how many elements are in a map

Maps have the size() method, which will return how many elements are being stored.

1Item Sword { "Sword of Poking" };
2Item Pants { "Pants of Invulnerability" };
3
4Equipment[Slot::Weapon] = Sword;
5Equipment[Slot::Legs] = Pants;
6
7cout << "I have "
8     << Equipment.size()
9     << " items equipped!";
10

Storing Multiple Values under the same Key

In a map, we can have duplicate values, but we cannot have duplicate keys. If we add an entry to our map, and an existing entry already has that key, the existing entry will be overwritten.

1Item Sword { "Sword of Poking" };
2Item Axe { "Axe of Chopping" };
3Equipment[Slot::Weapon] = Sword;
4Equipment[Slot::Weapon] = Axe;
5
6cout << "I am wielding an "
7     << Equipment[Slot::Weapon].Name
8     << " and I have " << Equipment.size()
9     << " items in total!";
10

If we need to store multiple values per key, we could use a different data structure. A map that can have duplicate keys is sometimes called a "multimap". We won't be covering them in this course, as they're not that useful.

Instead, the need to store multiple values under the same key is often better solved by making the value a collection type, such as an array or a vector. For example:

1unordered_map<Slot, vector<Item>> Equipment;
2
3Item Sword { "Sword of Poking" };
4Item Axe { "Axe of Chopping" };
5Equipment[Slot::Weapon].push_back(Sword);
6Equipment[Slot::Weapon].push_back(Axe);
7
8cout << "I only have " << Equipment.size()
9     << " slot filled but I have "
10     << Equipment[Slot::Weapon].size()
11     << " weapons in that one slot!";
12

Removing Elements from a Map

Maps have the erase() method, which will remove the element with the specific key. They also have the clear() method, which will remove all the elements, leaving an empty map with a size of 0.

1Item Sword { "Sword of Poking" };
2Equipment[Slot::Weapon] = Sword;
3
4Item Breastplate { "Shiny Breastplate" };
5Equipment[Slot::Chest] = Breastplate;
6
7Item Pants { "Pants of Invulnerability" };
8Equipment[Slot::Legs] = Pants;
9
10cout << "I have " << Equipment.size()
11     << " items equipped!\n";
12
13Equipment.erase(Slot::Weapon);
14cout << "Now I have " << Equipment.size() << " item\n";
15
16Equipment.clear();
17cout << "And now I have " << Equipment.size();
18

Iterating Over Maps

The standard library implementation of maps supports iterators, so we can use the same technique covered in the iterator lesson. The most common technique is the range-based for loop:

1for (auto Entry : Equipment) {
2  // Do stuff
3}
4

With the standard library's maps, each entry is a std::pair, so we can access the key and value using the first and second values respectively:

1for (auto Entry : Equipment) {
2  cout << "Slot: " << Entry.first << ", "
3       << "Item: " << Entry.second.Name << "\n";
4}
5

Each element of the pair gets passed to the for block by value - we will often want to switch that to pass by reference instead. As with functions, we can do that by adding an & to the type:

1for (auto& Entry : Equipment) {
2  cout << "Slot: " << Entry.first << ", "
3       << "Item: " << Entry.second.Name << "\n";
4}
5

Given we are not changing Entry within the for loop, we can also mark it as const:

1for (const auto& Entry : Equipment) {
2  cout << "Slot: " << Entry.first << ", "
3       << "Item: " << Entry.second.Name << "\n";
4}
5

Finally, we could also switch to using structured bindings. This removes the need to have the intermediate Entry variable in our loop heading, and also gives us the opportunity to give first and second more meaningful names :

1for (const auto& [Slot, Item] : Equipment) {
2  cout << "Slot: " << Slot << ", "
3       << "Item: " << Item.Name << "\n";
4}
5

Remember, with an unordered_map, there is no guarantee on the order in which we iterate over these items. If the order is important, we should switch to an ordered map instead.

Key Requirements

Similar to sets, the type of data we can use for keys in a map has some requirements:

• It needs to define a hash function
• It needs the ability to compare itself against other objects of the same type, using the == operator

Many of the C++ built-in types already have these abilities.

However, many types will not, and this includes custom types we create. As a result, the following will not work, because the type we are using as the key - Slot - doesn’t meet either of the two requirements:

1#include <unordered_map>
2#include <string>
3
4struct Item {
5  std::string Name;
6};
7
8int main() {
9  // Item cannot be hashed in its current form
10  // Therefore, it cannot be the key in a hashmap
11  std::unordered_map<Item, int> MapA;
12  
13  // This also applies to references to Items
14  std::unordered_map<Item&, int> MapB;
15
16  // It can still be the value in a hashmap - only
17  // the keys need to be hashable
18  std::unordered_map<int, Item> MapC;
19}
20

However, when we’re dealing with pointers to a custom type, this issue will not exist. Behind the scenes, pointers are just numbers, so the compiler is able to compare and hash those without requiring any help from us:

1std::unordered_map<Slot,  int> MapA; // Error
2std::unordered_map<Slot&, int> MapB; // Error
3std::unordered_set<Slot*, int> MapC; // This Works
4

For now, the important thing to recognize is just that a type needs to meet these hashing requirements in order to be used in a map. Implementing the requirements for our custom types is an advanced topic that we’ll cover in a later lesson.