Implementing Hash Maps using `std::unordered_map`

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.

Free, Unlimited Access

Ryan McCombe

Updated 3 months ago

In previous lessons, we introduced the idea of hashing and std::pair. By combining these ideas, we can create hash maps, among the most useful data structures we’ll encounter.

Every element in a hash map is a std::pair, of two related values, whose type we are free to set.

The first object in each pair is called the key. Alongside each key is the second object in our pair, called the value.

The key is used as an input to the hash function, which determines where exactly our pair gets inserted. Because of this, if we have a key, we can retrieve the value associated with that key in fast, constant time.

Associative Arrays and Dictionaries

Because the primary operation we perform on hash maps is providing the key to retrieve the value associated with it, map data structures are sometimes called associative arrays or dictionaries in other programming languages.

`std::unordered_map`

The C++ standard library’s implementation of a hash map is std::unordered_map. This is available by including the <unordered_map> header:

1#include <unordered_map>

We create a std::unordered_map by providing two template parameters - the type we want to use for each key, and the type we want to use for each value, respectively. Below, we create a map where both the key and value will be a std::string:

1#include <unordered_map>
2#include <string>
3
4int main() {
5  using std::unordered_map, std::string;
6  unordered_map<string, string> Map;
7}

We can provide a collection of key-value pairs with which to initialize our map:

1#include <unordered_map>
2#include <string>
3
4int main() {
5  using std::unordered_map, std::string;
6
7  unordered_map<string, string> Map{
8    {"Bob", "robert@example.com"},
9    {"Anna", "anna@example.com"},
10    {"Dave", "dave@example.com"},
11  };
12}

Given each entry in a map is a std::pair, if we have such objects, we can also initialize a map from them:

1#include <unordered_map>
2#include <string>
3
4int main() {
5  using std::string;
6  using Person = std::pair<string, string>;
7
8  Person Anna{"Anna", "anna@example.com"};
9  Person Bob{"Bob", "robert@example.com"};
10  Person Dave{"Dave", "dave@example.com"};
11
12  std::unordered_map<string, string> Map{
13    Anna, Bob, Dave
14  };
15}

We can also use class template argument deduction (CTAD) as usual, to let the compiler deduce the type:

1#include <unordered_map>
2#include <string>
3
4int main() {
5  using namespace std::string_literals;
6  std::pair Anna{"Anna"s, "anna@example.com"s};
7  std::pair Bob{"Bob"s, "robert@example.com"s};
8  std::pair Dave{"Dave"s, "dave@example.com"s};
9
10  std::unordered_map Map{Anna, Bob, Dave};
11}

Map Size

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

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map{
7    {"Anna", "anna@example.com"},
8    {"Bob", "robert@example.com"},
9    {"Dave", "dave@example.com"}
10  };
11
12  std::cout << "Size: " << Map.size();
13}

1Size: 3

The `empty()` Method

If we explicitly want to know whether the map is empty or not - that is, where its size is 0 - we can use the more descriptive empty() method:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  std::unordered_map<int, bool> Map;
6
7  if (Map.empty()) {
8    std::cout << "The map is empty";
9  }
10}

1The map is empty

Element Access

There are several ways we can retrieve elements from our unordered map. They all rely on us having the key of the key-value pair we want to retrieve.

`contains()`

By passing a key to the contains() method, we create a bool representing whether or not our map contains that key:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map{
7    {"Anna", "anna@example.com"},
8    {"Bob", "robert@example.com"},
9    {"Dave", "dave@example.com"}
10  };
11
12  if (Map.contains("Bob")) {
13    std::cout << "The map has Bob";
14  }
15
16  if (!Map.contains("Steve")) {
17    std::cout << ", but not Steve";
18  }
19}

1The map has Bob, but not Steve

`count()`

The contains() method was only added in C++20. Before that, we used the less intuitive count() method, which returns how many entries match the key we provide.

Given a std::unordered_map cannot contain duplicates, count() will return either 0 or 1.

When coerced to a boolean, 0 and 1 return false and true respectively, so we can use count() in the same way we use contains():

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map{
7    {"Anna", "anna@example.com"},
8    {"Bob", "robert@example.com"},
9    {"Dave", "dave@example.com"}
10  };
11
12  if (Map.count("Bob")) {
13    std::cout << "The map has Bob";
14  }
15
16  if (!Map.count("Steve")) {
17    std::cout << ", but not Steve";
18  }
19}

1The map has Bob, but not Steve

The `[]` operator

The primary way we access elements within an unordered map is through the [] operator. We provide a key, and the associated value is returned by reference:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map{
7    {"Anna", "anna@example.com"},
8    {"Bob", "robert@example.com"},
9    {"Dave", "dave@example.com"}
10  };
11
12  std::cout << "Bob: " << Map["Bob"];
13}

1Bob: robert@example.com

If the key does not exist within our map, the [] operator will create a new entry. The entry will use this key, and default-construct a corresponding value:

1#include <iostream>
2#include <unordered_map>
3
4struct SomeType {
5  SomeType() {
6    std::cout << "Default Constructing";
7  }
8};
9
10int main() {
11  std::unordered_map<std::string, SomeType> Map;
12  Map["Hello"];
13}

1Default Constructing

If we do not want the behavior, we can first check if our map contains() the key we are about to access, or we can use the at() or find() methods instead.

The `at()` method

Like the [] operator, the at() method will return the value associated with the key we provide. The main difference is that, if the key does not exist in our map, at() will throw a std::out_of_range exception:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map{
7    {"Anna", "anna@example.com"},
8    {"Bob", "robert@example.com"},
9    {"Dave", "dave@example.com"}
10  };
11
12  std::cout << "Bob: " << Map.at("Bob");
13
14  try {
15    Map.at("Steve");
16  } catch (std::out_of_range& e) {
17    std::cout << "\nSteve is not in the map:\n"
18              << e.what();
19  }
20}

1Bob: robert@example.com
2Steve is not in the map:
3invalid unordered_map<K, T> key

The `find()` method

The find() method returns an iterator to the key-value pair associated with the key we provide:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map{
7    {"Anna", "anna@example.com"},
8    {"Bob", "robert@example.com"},
9    {"Dave", "dave@example.com"}
10  };
11
12  auto it{Map.find("Bob")};
13
14  std::cout << "Key: " << it->first
15            << "\nValue: " << it->second;
16}

1Key: Bob
2Value: robert@example.com

If the map doesn’t contain the key, find() will return a past-the-end iterator for our map. We can test for this by comparing it to the iterator returned by our map’s end() method:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map{
7    {"Anna", "anna@example.com"},
8    {"Bob", "robert@example.com"},
9    {"Dave", "dave@example.com"}
10  };
11
12  auto it{Map.find("Steve")};
13
14  if (it == Map.end()) {
15    std::cout << "Could not find Steve";
16  } else {
17    auto [key, value]{*it};
18    std::cout << "Key: " << key
19          << "\nValue: " << value;
20  }
21}

1Could not find Steve

Element Insertion

We can combine the [] and = operators to insert a new object:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map{
7    {"Anna", "anna@example.com"},
8    {"Bob", "robert@example.com"},
9    {"Dave", "dave@example.com"}
10  };
11
12  Map["Steve"] = "steve@example.com";
13
14  std::cout << "Steve: " << Map["Steve"];
15}

1Steve: steve@example.com

Duplicate Objects

Note, that it’s not possible to have duplicate keys in a std::unordered_map. If we use the = operator with a key that is already used, we will instead be updating that key:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map{
7    {"Anna", "anna@example.com"},
8    {"Bob", "robert@example.com"},
9    {"Dave", "dave@example.com"}
10  };
11
12  std::cout << "Size: " << Map.size();
13  Map["Bob"] = "new-bob@example.com";
14  std::cout << "\nSize: Still " << Map.size();
15  std::cout << "\nBob: " << Map["Bob"];
16}

1Size: 3
2Size: Still 3
3Bob: new-bob@example.com

However, we can have duplicate values stored under different keys:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map{
7    {"Anna", "anna@example.com"},
8    {"Bob", "robert@example.com"},
9    {"Dave", "dave@example.com"}
10  };
11
12  std::cout << "Size: " << Map.size();
13  Map["Robert"] = "robert@example.com";
14  std::cout << "\nSize: " << Map.size();
15
16  if (Map["Bob"] == Map["Robert"]) {
17    std::cout << "\nBob and Robert have the"
18      " same value";
19  }
20}

1Size: 3
2Size: 4
3Bob and Robert have the same value

A variation of std::unordered_map that supports duplicate keys is available - std::unordered_multimap.

The `insert()` method

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

For example, every element in a std::unordered_map<int, bool> is a std::pair<int, bool>.

If we have such a pair, we can add it directly using the insert() method:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map{
7    {"Anna", "anna@example.com"},
8    {"Bob", "robert@example.com"},
9    {"Dave", "dave@example.com"}
10  };
11
12  std::pair<string, string> Steve {
13    "Steve", "steve@example.com"};
14
15  Map.insert(Steve);
16
17  std::cout << "Steve: " << Map["Steve"];
18}

1Steve: steve@example.com

The `insert_or_assign()` method

The insert_or_assign() method gives us another way to add a new object, or update an existing one.

The main benefit of insert_or_assign() is that it returns a std::pair that lets us understand the effect of the function. The pair contains:

An iterator to where the new or updated entry is
A bool represents whether an insertion took place. If the boolean is true, our entry was inserted; if it is false, an existing entry was updated:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map{
7      {"Bob", "robert@example.com"},
8      {"Anna", "anna@example.com"},
9      {"Dave", "dave@example.com"},
10  };
11
12  auto [it, wasInserted]{Map.insert_or_assign(
13    "Bob", "bob@example.com")};
14
15  if (!wasInserted) {
16    std::cout << it->first << " already existed"
17              << " - its value is now "
18              << it->second;
19  }
20}

1Bob already existed - its value is now bob@example.com

The `emplace()` method

The emplace() method allows us to construct a std::pair in place, directly into the map. This is more performant than creating the pair outside of the container, and then moving and copying it in, so should be preferred where possible.

Arguments provided to emplace() are forwarded to the underlying std::pair constructor:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map{
7    {"Anna", "anna@example.com"},
8    {"Bob", "robert@example.com"},
9    {"Dave", "dave@example.com"}
10  };
11
12  Map.emplace("Steve", "steve@example.com");
13
14  std::cout << "Steve: " << Map["Steve"];
15}

1Steve: steve@example.com

The `try_emplace()` method

The try_emplace() method will emplace our std::pair into the map, but only if the map doesn’t already contain an entry with a matching key.

Below, try_emplace() adds "Steve" because our container doesn’t yet have an entry with a key of "Steve". But it does not insert "Bob", because "Bob" already exists:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map{
7    {"Anna", "anna@example.com"},
8    {"Bob", "robert@example.com"},
9    {"Dave", "dave@example.com"}
10  };
11
12  Map.try_emplace("Steve", "steve@example.com");
13  Map.try_emplace("Bob", "rob@example.com");
14
15  std::cout << "Steve: " << Map["Steve"];
16  std::cout << "\nBob: " << Map["Bob"];
17}

1Steve: steve@example.com
2Bob: robert@example.com

The try_emplace() method returns a std::pair containing an iterator and a boolean.

The iterator points to where the object is within the map
The boolean represents whether or not the insertion was successful. If the boolean is false, that means an entry with that key already existed, so try_emplace() did not create a new entry

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map{
7    {"Anna", "anna@example.com"},
8    {"Bob", "robert@example.com"},
9    {"Dave", "dave@example.com"}
10  };
11
12  auto[it, wasSuccessful]{
13    Map.try_emplace("Bob", "rob@example.com")};
14
15  if (!wasSuccessful) {
16    std::cout << "The container already had"
17                 " the key " << it->first
18              << "\nValue: " << it->second;
19  }
20}

1The container already had the key Bob
2Value: robert@example.com

Removing Elements from a Map

Maps have the erase() method, which will remove the element with the specific key.

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map{
7    {"Anna", "anna@example.com"},
8    {"Bob", "robert@example.com"},
9    {"Dave", "dave@example.com"}
10  };
11
12  std::cout << "Size: " << Map.size();
13  Map.erase("Bob");
14  std::cout << "\nSize: " << Map.size();
15}

1Size: 3
2Size: 2

They also have the clear() method, which will remove all the elements, leaving an empty map with a size of 0:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map{
7    {"Anna", "anna@example.com"},
8    {"Bob", "robert@example.com"},
9    {"Dave", "dave@example.com"}
10  };
11
12  std::cout << "Size: " << Map.size();
13  Map.clear();
14  std::cout << "\nSize: " << Map.size();
15}

1Size: 3
2Size: 0

Editing Values

When we have a key, we can update the value associated with that key in all the normal ways. For example, we can assign a new value using the = operator.

We can also modify the current value by calling operators or methods on it, or by passing it off to some other function by reference or pointer:

1#include <iostream>
2#include <unordered_map>
3
4void Double(int& x) { x *= 2; }
5
6int main() {
7  using std::string;
8  std::unordered_map<string, int> Map{
9    {"a", 1},
10    {"b", 2},
11    {"c", 3}
12  };
13
14  Map["a"] = 100;
15  ++Map["b"];
16  Double(Map["c"]);
17
18  std::cout << std::format("a={}, b={}, c={}",
19    Map["a"], Map["b"], Map["c"]);
20}

1a=100, b=3, c=6

Editing Keys

The keys we use are processed by the container’s hash function to determine where our object should be inserted. Because of this, we can’t directly modify them, as doing so would leave them in the incorrect position within the underlying array.

We could erase the existing key-value pair and insert a new one. However, this approach can be problematic, as destroying the existing objects might have side effects, or recreating them might be expensive.

As of C++17, there is a more efficient way to accomplish this, using the extract() method. This method removes the node from the container, leaving our original objects in place.

The extracted node provides editable references to the key and value using the key() and mapped() methods respectively:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map {
7      {"Bob", "robert@example.com"},
8      {"Anna", "anna@example.com"},
9      {"Dave", "dave@example.com"},
10  };
11
12  auto Node {Map.extract("Bob")};
13
14  std::cout << "Extracted Key: " << Node.key()
15            << ", Value: " << Node.mapped();
16}

1Extracted Key: Bob, Value: robert@example.com

From here, we can modify our node as needed and then insert it back into our map, which ensures our updated key is rehashed. To insert our node, we use an insert() overload that accepts an rvalue reference:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map {
7      {"Bob", "robert@example.com"},
8      {"Anna", "anna@example.com"},
9      {"Dave", "dave@example.com"},
10  };
11
12  auto Node {Map.extract("Bob")};
13  Node.key() = "Robert";
14  Map.insert(std::move(Node));
15
16  std::cout << "Robert: " << Map["Robert"];
17}

1Robert: robert@example.com

Map Iteration

The standard library implementation of maps supports iterators, so we can use the same techniques we introduced with other containers. The most common way we’ll iterate through a collection is using a range-based for loop.

Given each entry is a std::pair, we can access the key and value using the first and second member variables respectively:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map{
7    {"Anna", "anna@example.com"},
8    {"Bob", "robert@example.com"},
9    {"Dave", "dave@example.com"}
10  };
11
12  for (auto Pair : Map) {
13    std::cout << "\nKey: " << Pair.first;
14    std::cout << ", Value: " << Pair.second;
15  }
16}

1Key: Anna, Value: anna@example.com
2Key: Bob, Value: robert@example.com
3Key: Dave, Value: dave@example.com

Passing by Reference

Each element of the pair gets passed to the loop body 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.

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

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map{
7    {"Anna", "anna@example.com"},
8    {"Bob", "robert@example.com"},
9    {"Dave", "dave@example.com"}
10  };
11
12  for (const auto& Pair : Map) {
13    std::cout << "\nKey: " << Pair.first;
14    std::cout << ", Value: " << Pair.second;
15  }
16}

1Key: Anna, Value: anna@example.com
2Key: Bob, Value: robert@example.com
3Key: Dave, Value: dave@example.com

Structured Binding

Finally, we could also switch to using structured binding with the std::pair we receive. This removes the need to have the intermediate variable in our loop heading, and also allows us to give first and second more meaningful names:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map{
7    {"Anna", "anna@example.com"},
8    {"Bob", "robert@example.com"},
9    {"Dave", "dave@example.com"}
10  };
11
12  for (const auto& [key, value] : Map) {
13    std::cout << "\nKey: " << key;
14    std::cout << ", Value: " << value;
15  }
16}

1Key: Anna, Value: anna@example.com
2Key: Bob, Value: robert@example.com
3Key: Dave, Value: dave@example.com

Ordering

As the name suggests, a std::unordered_map is not ordered. That means, when we iterate over it, we can’t easily predict which order our elements will be accessed in.

An ordered map is available in the standard library as std::map. Rather than using hash-based techniques, std::map relies on a binary tree instead.

This approach allows elements to be stored in a predictable order, at a small cost to insertion and search performance. We cover trees and std::map in detail later in the course.

Using Custom Types

Naturally, we can store user-defined types within our unordered maps. In many use cases, our maps will contain a known set of keys, so it’s fairly common that we’ll be using enum types as our keys:

1#include <iostream>
2#include <unordered_map>
3
4enum class Slot {Weapon, Armor, Helmet};
5
6struct Item {
7  std::string Name;
8};
9
10int main() {
11  std::unordered_map<Slot, Item> Equipment{
12    {Slot::Weapon, Item{"Iron Sword"}},
13    {Slot::Armor,  Item{"Leather Armor"}},
14    {Slot::Helmet, Item{"Wooden Bucket"}},
15  };
16
17  std::cout << "Helmet: "
18    << Equipment[Slot::Helmet].Name;
19}

1Helmet: Wooden Bucket

Using Other Custom Types

We can use any user-defined type within maps, not just enum types. However, the type we use as a key has similar requirements to what we saw earlier when we introduced hash sets. Specifically:

The key type needs to implement std::hash, or we need to provide a custom hash function for our map
The key type needs to be able to compare its objects using the == operator, or we need to provide a custom comparison function

In our introduction to this chapter, we walked through how to implement std::hash and operator==() for a custom type:

1// User.h
2#pragma once
3#include <string>
4
5struct User {
6  std::string Name;
7  bool operator==(const User& Other) const {
8    return Name == Other.Name;
9  }
10};
11
12namespace std {
13template <>
14struct hash<User> {
15  size_t operator()(const User& U) const {
16    return std::hash<std::string>{}(U.Name);
17  }
18};
19}

3D art showing a character looking at a screen

Hashing and `std::hash`

This lesson provides an in-depth look at hashing in C++, including std::hash, collision strategies, and usage in hash-based containers.

The constraints on the value type are much looser. We can use almost any type although, outside of some advanced use cases, many std::unordered_map operators and methods require this type to be default constructible:

1#include <string>
2#include <unordered_map>
3
4struct SomeType {
5  SomeType() = delete;
6  SomeType(int){};
7};
8
9int main() {
10  std::unordered_map<std::string, SomeType> Map;
11  Map["Three"] = 3;
12}

1error: 'SomeType::SomeType(void)': attempting to reference a deleted function

Using a Custom Hash Function

If the type we want to use as the key to our map does not implement std::hash, or it does but we want to customize the hash function anyway, we do that by passing an additional template argument when creating our map:

1#include <unordered_map>
2#include <iostream>
3
4struct User {/*...*/}
11
12struct Hash {
13  size_t operator()(const User& U) const {
14    return std::hash<std::string>{}(U.Name);
15  }
16};
17
18int main() {
19  std::unordered_map<User, std::string, Hash> M;
20  M[User("Bob")] = "robert@example.com";
21
22  std::cout << "Bob: " << M[User("Bob")];
23}

1Bob: robert@example.com

As we saw in the earlier std::unordered_set lesson, the hasher template argument expects a type with which it can create function objects, or functors. We cover these in more detail later in the course.

Function Objects (Functors)

This lesson introduces function objects, or functors. This concept allows us to create objects that can be used as functions, including state management and parameter handling.

Using a Custom Comparison Function

Two different objects can hash to the same value so, like all hash-based containers, std::unordered_map additionally needs a way to determine if two keys are unequivocally equal.

By default, it uses the key type’s == operator to determine this, but we can override this by providing a custom functor type as the fourth template argument:

1#include <unordered_map>
2#include <iostream>
3
4struct User {
5  std::string Name;
6};
7
8struct Hasher {/*...*/}
14
15struct Comparer {
16  bool operator()(
17    const User& A, const User& B) const {
18    return A.Name == B.Name;
19  }
20};
21
22int main() {
23  std::unordered_map<
24    User, std::string, Hasher, Comparer> M;
25  M[User("Bob")] = "robert@example.com";
26
27  std::cout << "Bob: " << M[User("Bob")];
28}

1Bob: robert@example.com

Remember, if two objects are the same, they should hash to the same value. That is, if Comparer(A, B) is true, then Hasher(A) must return the same value as Hasher(B).

The onus is on us to ensure our implementation satisfies this constraint. If it doesn’t, the std::unordered_map will behave unpredictably.

Buckets, Load Factor, and Rehashing

The std::unordered_map handles collisions in much the same way as a std::unordered_set, and gives us the same suite of methods to inspect and control that process.

We’ll quickly review them here, but more thorough explanations are available in the std::unordered_set lesson:

Implementing Hash Sets using `std::unordered_set`

This lesson provides a thorough understanding of std::unordered_set, from basic initialization to handling custom types and collisions

`bucket_count()`

The size of the primary array our std::unordered_map is currently using is available through the bucket_count() method:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map {
7      {"Bob", "robert@example.com"},
8      {"Anna", "anna@example.com"},
9      {"Dave", "dave@example.com"},
10  };
11
12  std::cout << "Buckets: " << Map.bucket_count();
13}

1Buckets: 8

`load_factor()`

The load_factor() method returns the average number of objects per bucket. Our map contains 3 entries across 8 buckets in this example, so our load factor is 3/8:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map {
7      {"Bob", "robert@example.com"},
8      {"Anna", "anna@example.com"},
9      {"Dave", "dave@example.com"},
10  };
11
12  std::cout << "Load Factor: "
13    << Map.load_factor();
14}

1Load Factor: 0.375

`max_load_factor()`

When our load factor exceeds the maximum load factor, our container will resize and rehash. The max_load_factor() method is how we control this.

If we pass no arguments, the method returns the currently configured max load factor. If we provide a float, we can set a new value:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map {
7      {"Bob", "robert@example.com"},
8      {"Anna", "anna@example.com"},
9      {"Dave", "dave@example.com"},
10  };
11
12  std::cout << "Current Max Load Factor: "
13    << Map.max_load_factor();
14  std::cout << "\nCurrent Load Factor: "
15    << Map.load_factor();
16
17  Map.max_load_factor(0.25);
18
19  std::cout << "\nNew Max Load Factor: "
20    << Map.max_load_factor();
21
22  Map["Steve"] = "steve@example.com";
23  std::cout << "\nNew Load Factor: "
24    << Map.load_factor();
25}

1Current Max Load Factor: 1
2Current Load Factor: 0.375
3New Max Load Factor: 0.25
4New Load Factor: 0.0625

The `rehash()` Function

The rehash() function accepts an integer argument. It then updates our container to use at least this many buckets, and rehashes objects to make use of the new space:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map {
7      {"Bob", "robert@example.com"},
8      {"Anna", "anna@example.com"},
9      {"Dave", "dave@example.com"},
10  };
11
12  std::cout << "Current Bucket Count: "
13    << Map.bucket_count();
14
15  Map.rehash(500);
16
17  std::cout << "\nNew Bucket Count: "
18    << Map.bucket_count();
19}

1Current Bucket Count: 8
2New Bucket Count: 512

The `reserve()` Method

The reserve() method works similarly to rehash(), except it takes into consideration our maximum load factor. Below, we reserve enough space for 500 entries, using a max load factor of 0.25.

As such, our container rehashes to at least 2,000 buckets, that is 500 / 0.25:

1#include <iostream>
2#include <unordered_map>
3
4int main() {
5  using std::string;
6  std::unordered_map<string, string> Map {
7      {"Bob", "robert@example.com"},
8      {"Anna", "anna@example.com"},
9      {"Dave", "dave@example.com"},
10  };
11
12  std::cout << "Current Bucket Count: "
13    << Map.bucket_count();
14
15  Map.max_load_factor(0.25);
16  Map.reserve(500);
17
18  std::cout << "\nNew Bucket Count: "
19    << Map.bucket_count();
20}

1Current Bucket Count: 8
2New Bucket Count: 2048

Summary

In this comprehensive lesson, we explored the functionalities and use-cases of std::unordered_map, covering its creation, manipulation, and advanced features like custom hash functions and handling custom types.

We delved into its various methods and properties. The key takeaways included:

Introduction to std::unordered_map, including its creation and initialization with key-value pairs.
Understanding of map size methods like size() and empty().
Techniques for element access, including contains(), count(), the [] operator, at(), and find() methods.
Methods for element insertion, such as using the [] operator, insert(), insert_or_assign(), emplace(), and try_emplace().
Handling of duplicate objects and understanding the uniqueness of keys in std::unordered_map.
Strategies for removing elements using erase() and clear() methods.
Approaches to editing values and the limitations in directly modifying keys.
Efficient key modification using the extract() method from C++17.
Techniques for iterating over maps using range-based for loops and structured bindings.
Insight into using custom types as keys, including requirements for std::hash and operator==.
Implementing custom hash and comparison functions for more complex key types.
Understanding the internal workings of std::unordered_map, including concepts like buckets, load factor, and methods like rehash() and reserve().
Comparisons with ordered maps and the benefits of using std::unordered_map for specific scenarios.

Was this lesson useful?

Next Lesson

Nullable Values using `std::optional`

A comprehensive guide to using std::optional to represent values that may or may not be present.

Illustration representing computer hardware

Ryan McCombe

Updated 3 months ago

Lesson Contents