Using std::unordered_map to create associative containers

Create maps / dictionaries in C++ using the standard library's std::unordered_map container class.
This lesson is part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

DreamShaper_v7_fantasy_male_pirate_Sidecut_hair_swords_black_c_1.jpg
Ryan McCombe
Ryan McCombe
Posted

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>

#include <unordered_map>

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:

#include <unordered_map>
using std::unordered_map, std::cout;

enum class Slot { Chest, Legs, Weapon };
struct Item { string Name; };

unordered_map<Slot, Item> Equipment;

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:

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

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.

Item Sword { "Sword of Poking" };
pair EquippedWeapon { Slot::Weapon, Sword };
Equipment.insert(EquippedWeapon);

// We can also create the pair inline
Item Armour { "Shiny Breastplate" };
Equipment.insert({ Slot::Chest, Armour });

cout << "I'm wielding a "
     << Equipment[Slot::Weapon].Name
     << "!\n";

cout << "I'm wearing a "
     << Equipment[Slot::Chest].Name
     << "!\n";

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

Item Sword { "Sword of Poking" };
pair EquippedWeapon { Slot::Weapon, Sword };

Item Pants { "Pants of Invulnerability" };
pair EquippedPants { Slot::Legs, Pants };

unordered_map Equipment { EquippedWeapon, EquippedPants };

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

unordered_map Equipment {
  pair { Slot::Weapon, Item { "Sword of Poking" },
  pair { Slot::Legs, Item { "Pants of Invulnerability" };
};

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.

Item Sword { "Sword of Poking" };
Item Pants { "Pants of Invulnerability" };

Equipment[Slot::Weapon] = Sword;
Equipment[Slot::Legs] = Pants;

cout << "I have "
     << Equipment.size()
     << " items equipped!";

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.

Item Sword { "Sword of Poking" };
Item Axe { "Axe of Chopping" };
Equipment[Slot::Weapon] = Sword;
Equipment[Slot::Weapon] = Axe;

cout << "I am wielding an "
     << Equipment[Slot::Weapon].Name
     << " and I have " << Equipment.size()
     << " items in total!";

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:

unordered_map<Slot, vector<Item>> Equipment;

Item Sword { "Sword of Poking" };
Item Axe { "Axe of Chopping" };
Equipment[Slot::Weapon].push_back(Sword);
Equipment[Slot::Weapon].push_back(Axe);

cout << "I only have " << Equipment.size()
     << " slot filled but I have "
     << Equipment[Slot::Weapon].size()
     << " weapons in that one slot!";

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.

Item Sword { "Sword of Poking" };
Equipment[Slot::Weapon] = Sword;

Item Breastplate { "Shiny Breastplate" };
Equipment[Slot::Chest] = Breastplate;

Item Pants { "Pants of Invulnerability" };
Equipment[Slot::Legs] = Pants;

cout << "I have " << Equipment.size()
     << " items equipped!\n";

Equipment.erase(Slot::Weapon);
cout << "Now I have " << Equipment.size() << " item\n";

Equipment.clear();
cout << "And now I have " << Equipment.size();

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:

for (auto Entry : Equipment) {
  // Do stuff
}

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:

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

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:

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

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

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

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 :

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

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:

#include <unordered_map>
#include <string>

struct Item {
  std::string Name;
};

int main() {
  // Item cannot be hashed in its current form
  // Therefore, it cannot be the key in a hashmap
  std::unordered_map<Item, int> MapA;
  
  // This also applies to references to Items
  std::unordered_map<Item&, int> MapB;

  // It can still be the value in a hashmap - only
  // the keys need to be hashable
  std::unordered_map<int, Item> MapC;
}

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:

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

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.

Was this lesson useful?

Ryan McCombe
Ryan McCombe
Posted
This lesson is part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

7a.jpg
This lesson is part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access!

This course includes:

  • 106 Lessons
  • 550+ Code Samples
  • 96% Positive Reviews
  • Regularly Updated
  • Help and FAQ
Next Lesson

C++ Queues using std::queue

Learn the many applications of queues in programming. Then see how we can create and use them in C++ using the standard library's std::queue
5d.jpg
Contact|Privacy Policy|Terms of Use
Copyright © 2023 - All Rights Reserved