std::unordered_map
to create associative containersstd::unordered_map
container class.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:
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.
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;
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.
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!";
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!";
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();
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.
Similar to sets, the type of data we can use for keys in a map has some requirements:
==
operatorMany 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.
Comprehensive course covering advanced concepts, and how to use them on large-scale projects.