Implementing Hash Sets using std::unordered_set

In this lesson, we’ll cover the C++ Standard Library’s implementation of a hash set, which is the std::unordered_set.

• It is a collection of unique elements, ensuring each element appears only once - no duplicates.
• Elements are stored in no particular order. This has implications for iteration, which we’ll cover.
• The set uses a hash function to organize its elements, which allows for efficient insertion and searching.

In the first part of the lesson, we'll explore the basics of std::unordered_set, including its creation and initialization. You'll learn how this container leverages hashing to store elements efficiently, ensuring quick access and manipulation.

As we progress, we'll delve into more advanced topics such as customizing hash functions, customizing the load factor, and more.

This lesson builds on the theory we established in the previous section, which may be helpful to review for those less familiar with hashing, and how it can be used to create data structures:

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.

Creating Unordered Sets

The std::unordered_set class is available once the <unordered_set> header is included. They can be constructed in the same way as other containers - we specify the type of data they will contain as a template parameter:

1#include <unordered_set>
2
3int main() {
4  std::unordered_set<int> MySet;
5}

The container can be populated with initial values:

1#include <unordered_set>
2
3int main() {
4  std::unordered_set<int> MySet { 1, 2, 3 };
5}

When providing initial values, the type of those values can inferred using class template argument deduction (CTAD), so we do not need to specify it:

1#include <unordered_set>
2
3int main() {
4  std::unordered_set MySet { 1, 2, 3 };
5}

Initializing a std::unordered_set using iterators

The std::unordered_set constructor has an overload that allows us to pass an iterator pair. This will initialize our container with the values contained within that range:

1#include <vector>
2#include <unordered_set>
3
4int main() {
5  std::vector MyVec{1, 2, 2, 2, 3};
6  std::unordered_set MySet{
7    MyVec.begin(), MyVec.end()};
8}

Remember, a std::unordered_set cannot contain duplicates, so it may be initialized with fewer values than the original range.

In this case, MySet will have only three objects - 1, 2, and 3. The additional duplicate 2s are omitted.

Iteration

Unordered sets support iteration but, as the name suggests, the containers are not ordered. This means that when we iterate over the container, we cannot easily predict our objects' order.

If we want to iterate over them anyway, they implement begin() and end() methods which return iterators. As such, we can use them with range and iterator-based functions and algorithms.

For example, they’re compatible with range-based loops:

1#include <unordered_set>
2#include <iostream>
3
4int main() {
5  std::unordered_set MySet { 1, 2, 3 };
6  for (int x : MySet) {
7    std::cout << x << ", "; 
8  }
9}

11, 2, 3,

Below, we call the iterator-based std::vector constructor to create an array from the contents of an unordered set:

1#include <unordered_set>
2#include <vector>
3#include <iostream>
4
5int main() {
6  std::unordered_set MySet { 1, 2, 3 };
7  std::vector<int> MyVec{
8    MySet.begin(), MySet.end()};
9
10  for (int x : MyVec) {
11    std::cout << x << ", "; 
12  }
13}

11, 2, 3,

Here, we use the iterator-based std::for_each() algorithm with an unordered set:

1#include <unordered_set>
2#include <algorithm>
3#include <iostream>
4
5void Log(int x) { std::cout << x << ", "; }
6
7int main() {
8  std::unordered_set Set { 1, 2, 3 };
9  std::for_each(Set.begin(), Set.end(), Log);
10}

11, 2, 3,

Inserting Objects

We can add new data to our container in a few different ways:

1. Constructing Objects in Place using emplace()

The preferred way to add a single object to our set is to construct it in place, if possible. We do this using the emplace(). method. Any arguments we provide to emplace() will be forwarded to the constructor of the underlying type. In this case, that is int:

1#include <unordered_set>
2#include <iostream>
3
4int main() {
5  std::unordered_set<std::string> Set;
6  Set.emplace("Hello");
7
8  for (const std::string& S : Set) {
9    std::cout << S;
10  }
11}

1Hello

2. Inserting Existing Objects using insert()

Emplacing an object directly into the container is more performant than creating it outside and then moving it in. But, if our object already exists, we can copy (or move) it into the set using insert():

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set<std::string> Set;
6
7  std::string Greeting{"Hello"};
8  Set.insert(Greeting);
9
10  std::string Target{"Everyone"};
11  Set.insert(std::move(Target));
12
13  for (const std::string& S : Set) {
14    std::cout << S << ' ';
15  }
16}

1Hello Everyone

We can insert() a list of objects in a single call:

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set<std::string> Set;
6
7  Set.insert({"Hello", "Everyone"});
8
9  for (const std::string& S : Set) {
10    std::cout << S << ' ';
11  }
12}

1Hello Everyone

We can also pass an iterator pair to insert() to add multiple elements from some other container:

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set Set{1, 2, 3};
6  std::vector Vec{4, 5, 6};
7
8  Set.insert(Vec.begin(), Vec.end());
9
10  for (int x : Set) {
11    std::cout << x << ", ";
12  }
13}

11, 2, 3, 4, 5, 6,

3. Inserting a Range using insert_range() (C++23)

Note: the insert_range() method was added in C++23, and may not yet be supported by all compilers.

C++20 introduced the concept of a range. We’ll cover ranges in more detail later in the course, but for now, we can think of them as a way of representing an iterator pair as a single object.

Most of the sequential containers we’ve seen so far, such as std::vector and std::list are valid ranges. As such, we can insert the contents of such a container into our set using std::insert_range():

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set Set{1, 2, 3};
6  std::vector Vec{4, 5, 6};
7
8  Set.insert_range(Vec);
9
10  for (int x : Set) {
11    std::cout << x << ", ";
12  }
13}

11, 2, 3, 4, 5, 6,

Getting the Object Count

The size() method returns the number of items in a set:

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set Set{1, 2, 3};
6
7  std::cout << "Size: " << Set.size();
8}

1Size: 3

If we want to check if a set is empty - that is, the size is 0, we can do that using the more descriptive empty() method:

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set Set{1, 2, 3};
6
7  std::cout << "The set "
8            << (Set.empty() ? "is" : "is not")
9            << " empty";
10}

1The set is not empty

Removing Objects

We can remove items from a set using the erase() method:

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set Set{1, 2, 3};
6
7  Set.erase(1);
8
9  for (int x : Set) {
10    std::cout << x << ", ";
11  }
12}

12, 3,

We don’t need to check if the container contains an object before trying to erase it - we safely call erase() and it will simply have no effect if the object wasn’t in our set:

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set Set{1, 2, 3};
6
7  Set.erase(4);
8
9  for (int x : Set) {
10    std::cout << x << ", ";
11  }
12}

11, 2, 3,

Removing all Objects using clear()

We can remove all the items from a set using clear():

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set Set{1, 2, 3};
6
7  std::cout << "Size: " << Set.size();
8  Set.clear();
9  std::cout << "\nSize: " << Set.size();
10}

1Size: 3
2Size: 0

Searching for Objects

There are several ways we search for objects within our std::unordered_set. The most common are:

1. Using the contains() method

The contains() method is the simplest and most common option. It will return true if the object we pass as an argument is in the set, and false otherwise:

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set Set{1, 2, 3};
6
7  if (Set.contains(2)) {
8    std::cout << "2 is in the set";
9  }
10}

12 is in the set

2. Before C++20: using count()

The contains() method was only added in C++20. When targeting older specifications, we would use the count() method, which returns the number of matching objects that were found.

Given a std::unordered_set cannot contain duplicates, that return value would be either 0 or 1. Typically we’d just coerce that return value to a boolean, meaning count() is used in the same way as contains():

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set Set{1, 2, 3};
6
7  if (Set.count(2)) {
8    std::cout << "2 is in the set";
9  }
10}

12 is in the set

3. Using the insert() return value

Often, we will want to check if our set contains an object, and insert it if it doesn’t.

We can do this using the basic variation of the insert() method, which accepts a single value we want to insert. This function returns a struct with the result of the insertion.

It specifically returns a std::pair - a simple container that we cover in detail in the next lesson. The pair contains two member variables:

• first: An iterator to where the object we tried to insert is within the set
• second: A bool representing whether the insertion happened

In other words:

• If second is false, that means the insertion didn’t happen, because the object was already in the set
• If second is true, that means the object wasn’t previously in the set, but our insert() call has now added it:

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set Set{1, 2, 3};
6
7  auto [it, wasInserted]{Set.insert(4)};
8
9  if (wasInserted) {
10    std::cout << "4 wasn't in the set";
11  }
12
13  if (Set.contains(4)) {
14    std::cout << ", but now it is";
15  }
16}

14 wasn't in the set, but now it is

4. Using the erase() return value

Another common requirement we’ll have is the desire to check if our set contains an object, and erase that object if it does.

The erase() method can let us implement this, as it returns an integer representing the number of items that it removed. Given an unordered set cannot contain duplicates, erasing an object by value will therefore return 1 if our set contained the value, or 0 otherwise:

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set Set{1, 2, 3};
6
7  if (Set.erase(3)) {
8    std::cout << "3 was in the set";
9  }
10
11  if (!Set.contains(3)) {
12    std::cout << ", but not any more";
13  }
14}

13 was in the set, but not any more

5. Using find() to generate an iterator

We can also search our set using the find() method. This will return an iterator to the object if it was found, or an iterator equal to the end() return value otherwise:

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set Set{1, 2, 3};
6
7  auto A{Set.find(3)};
8
9  if (A != Set.end()) {
10    std::cout << "3 was found: " << *A;
11  }
12
13  auto B{Set.find(4)};
14
15  if (B == Set.end()) {
16    std::cout << "\n4 was not found";
17  }
18}

13 was found: 3
24 was not found

Modifying Objects

Modifying an object within a hash set is a little more complex than we might expect. This is because an object’s value determines where that object exists within the container, via the hash function.

Modifying an object’s value in place risks leaving the object in the wrong position, thereby compromising the integrity of our container. The container implements some protections using const to prevent us from doing this accidentally:

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set Set{1, 2, 3};
6
7  auto It{Set.find(3)};
8  (*It)++;
9}

1'It': you cannot assign to a variable that is const

An obvious workaround would be to copy the value, erase the original, modify the copy, and then insert it.

However, as of C++17, we have a more efficient approach to this, using the extract() method. The extract() method transfers ownership of the node containing the object to the caller. The node is effectively removed from the set at this point:

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set Set{1, 2, 3};
6
7  auto Node{Set.extract(3)};
8
9  for (int x : Set) {
10    std::cout << x << ", ";
11  }
12}

11, 2,

We can then access and update the value contained within that node, using the value() method. Once we’re done with our changes, we transfer the node back to the container.

We do this using an overload of the insert() method that accepts an rvalue reference to the node, and ensures it is rehashed and positioned correctly:

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set Set{1, 2, 3};
6
7  auto Node{Set.extract(3)};
8  Node.value() = 4;
9  Set.insert(std::move(Node));
10
11  for (int x : Set) {
12    std::cout << x << ", ";
13  }
14}

11, 2, 4,

Custom Types in Unordered Sets

Unlike with arrays, we can’t just add any type of data to an unordered set. To meet the performance characteristics, our data type needs to have some capabilities:

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

Many of the C++ built-in types already have this ability.

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 - Item doesn’t meet either of the two requirements:

1#include <unordered_set>
2#include <string>
3
4struct Item {
5  std::string Name;
6};
7
8int main() {
9  // In their current form, Item objects
10  // cannot be in a hash set
11  std::unordered_set<Item> SetA;
12
13  // References to this type will have the
14  // same issue
15  std::unordered_set<Item&> SetB;
16
17  // Pointers to any type can be hashed and
18  // compared, so this would work
19  std::unordered_set<Item*> SetC;
20}

There are two ways we can enable this. The first option is to implement std::hash and operator==() for our type. We walked through the implementation of this in our previous lesson:

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

Alternatively, we can provide a hash function and an equality function that our std::unordered_set can use We cover these in the next two sections.

Setting the Hash Function

As we saw above, std::unordered_set uses std::hash as its default hash function. However, when creating our set, we have the option of providing a custom hash function.

This allows us to create sets for storing a type that does not implement std::hash.

We provide the hash function as the second template parameter. Specifically, we need to provide a class that overloads the () operator:

1#include <unordered_set>
2#include <string>
3#include <iostream>
4
Unchanged Code|Show
5struct User {/*...*/}
12
13struct Hasher {
14  size_t operator()(const User& U) const {
15    return std::hash<std::string>{}(U.Name);
16  }
17};
18
19int main() {
20  std::unordered_set<User, Hasher> Set;
21  Set.emplace("Bob");
22
23  if (Set.contains(User{"Bob"})) {
24    std::cout << "Found Bob";
25  }
26}

1Found Bob

The Hasher syntax above may seem slightly unusual. We’re defining a type that can be used to create function objects - that is, objects that can be "called" using the () operator. These are sometimes referred to as functors, and we cover them in more detail in a dedicated lesson 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.

Setting the Equality Function

By default, when the std::unordered_set container needs to determine if two objects are equal, it does that using the == operator. We can provide a different function for this by providing a functor type as the third template parameter.

This allows us to store types that do not overload the == operator:

1#include <unordered_set>
2#include <string>
3#include <iostream>
4
5struct User {
6  std::string Name;
7};
8
Unchanged Code|Show
9struct Hasher {/*...*/}
15
16struct Comparer {
17  bool operator()(
18    const User& A, const User& B) const {
19    return A.Name == B.Name;
20  }
21};
22
23int main() {
24  std::unordered_set<User, Hasher, Comparer> Set;
25  Set.emplace("Bob");
26
27  if (Set.contains(User{"Bob"})) {
28    std::cout << "Found Bob";
29  }
30}

1Found Bob

1#include <unordered_set>
2#include <iostream>
3
4struct Comparer {
5  bool operator()(int a, int b) const {
6    return std::abs(a) == std::abs(b);
7  }
8};
9
10int main() {
11  std::unordered_set<
12    int, std::hash<int>, Comparer
13  > Set{1, 2, 3};
14
15  if (Set.contains(1)) {
16    std::cout << "The set contains 1";
17  }
18
19  if (!Set.contains(-1)) {
20    std::cout << " but not std::abs(-1)?";
21  }
22}

1The set contains 1 but not std::abs(-1)?

1#include <unordered_set>
2#include <string>
3#include <iostream>
4
5struct Hasher {
6  size_t operator()(int x) const {
7    return std::hash<int>{}(std::abs(x));
8  }
9};
10
Unchanged Code|Show
11struct Comparer {/*...*/}
17
18int main() {
19  std::unordered_set<int, Hasher, Comparer>
20    Set{1, 2, 3};
21
22  if (Set.contains(-1)) {
23    std::cout << "Set contains std::abs(-1)";
24  }
25}

1Set contains std::abs(-1)

Collisions and Buckets

The C++ specification doesn’t state what collision resolution strategy should be used for std::unordered_set.

However, it does prescribe an API that is much easier to implement using secondary chaining, so this is the approach that compilers tend to take.

The specification refers to these secondary chains as buckets.

We can determine how many buckets our set is using with the bucket_count() method:

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set Nums{1, 2, 3};
6
7  std::cout << "Bucket Count: "
8    << Nums.bucket_count();
9}

1Bucket Count: 8

Behind the scenes, each bucket is just an index of the underlying array. At each index, we have the secondary chain - often a linked list - of objects that hash to that index.

If we insert more items into the unordered set, it will eventually decide to rehash. That is, resizing the underlying array to provide more buckets:

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set Nums{1, 2, 3, 4, 5};
6
7  std::cout << "Bucket Count: "
8    << Nums.bucket_count();
9
10  Nums.emplace(6);
11  Nums.emplace(7);
12  Nums.emplace(8);
13  Nums.emplace(9);
14
15  std::cout << "\nBucket Count: "
16    << Nums.bucket_count();
17}

1Bucket Count: 8
2Bucket Count: 64

For a std::unordered_set specifically, rehashing will happen once the container exceeds its maximum load factor.

Load Factor

The load factor of a hash-based container is equivalent to the number of elements it contains, divided by the number of buckets it uses.

This is made available through the load_factor() method.

In the following example, our unordered set is using 8 buckets to store a combined 4 objects, meaning its load factor is 0.5:

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set Nums{1, 2, 3, 4};
6
7  std::cout << "Buckets: "
8    << Nums.bucket_count();
9
10  std::cout << "\nSize: "
11    << Nums.size();
12
13  std::cout << "\nLoad Factor: "
14    << Nums.load_factor();
15}

1Buckets: 8
2Size: 4
3Load Factor: 0.5

The load factor of a hash container is the main heuristic we use to balance memory usage vs collisions:

• A low load factor means our container has a lot of unused space. This reduces collisions but increases memory usage
• A high load factor means our container doesn’t have a lot of unused space. This is optimal for reducing memory consumption but means collisions are more frequent, degrading performance.

Setting the Maximum Load Factor

The std::unordered_set container lets us specify the maximum load factor using the max_load_factor() method.

Any insertion that would cause our set’s load factor to go over this value will cause a rehash:

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set Nums{1, 2, 3, 4};
6  std::cout << "Bucket Count: "
7    << Nums.bucket_count()
8    << "\nLoad Factor: "
9    << Nums.load_factor();
10
11  Nums.max_load_factor(0.25);
12  Nums.insert(5);
13  std::cout << "\n\nBucket Count: "
14    << Nums.bucket_count()
15    << "\nLoad Factor: "
16    << Nums.load_factor();
17}

1Bucket Count: 8
2Load Factor: 0.5
3
4Bucket Count: 64
5Load Factor: 0.078125

Getting the Currently Configured Max Load Factor

A variation of max_load_factor() that takes no arguments is available. This overload currently configured maximum load factor.

By default, this is set to 1.0 for a std::unordered_set:

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set Nums{1, 2, 3, 4};
6  std::cout << "Max Load Factor: "
7    << Nums.max_load_factor();
8}

1Max Load Factor: 1

Rehashing and Reserving

If we have an approximate idea of how many objects our set is likely going to need to store, it can be helpful to allocate enough space up-front.

This can reduce the amount of rehashing that needs to occur during the lifecycle of our container.

The rehash() Function

The rehash() method lets us manually rehash the container. We pass the number of buckets we want as an argument, and our container will then be rehashed to use at least that many buckets:

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set<int> Nums;
6  std::cout << "Bucket Count: "
7    << Nums.bucket_count();
8
9  Nums.rehash(500);
10
11  std::cout << "\nBucket Count: "
12    << Nums.bucket_count();
13}

1Bucket Count: 8
2Bucket Count: 512

The reserve() Method

The reserve() method is very similar to rehash(), except the argument we provide is the number of items we expect our container to have.

The key difference is that the number of buckets reserve() will rehash to consider our max_load_factor().

Below, we reserve space for 500 items. Given our max load factor is 0.25, we therefore allocate space for at least 2,000 buckets:

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set<int> Nums;
6  Nums.max_load_factor(0.25);
7  Nums.reserve(500);
8  std::cout << "Bucket Count: "
9    << Nums.bucket_count();
10}

1Bucket Count: 2048

Summary

In this lesson, we have explored std::unordered_set - the C++ standard library’s implementation of a hash set. We covered everything from initialization and iteration to customization for complex types.

Key Learnings

• The basics of creating and initializing std::unordered_set with various methods, including class template argument deduction (CTAD).
• Different ways to iterate over std::unordered_set, emphasizing its unordered nature.
• Techniques for inserting objects using emplace(), insert(), and C++23's insert_range() methods.
• Methods to determine the size() of a set, and whether the set is empty().
• Removing elements from the set using erase() and clearing the entire set with clear().
• Searching for objects using methods like contains(), count(), insert() return value, erase() return value, and find().
• The complexity and approach for modifying objects in a set, particularly using the extract() method.
• Requirements and methods for using custom types in std::unordered_set, including the implementation of hash functions and equality operators.
• Setting custom hash functions and equality comparators for std::unordered_set.
• Understanding the internal mechanism of collision handling and buckets in std::unordered_set.
• Managing performance with concepts like load factor, and methods such as rehash() and reserve() for optimizing space and reducing collisions.

Next Lesson

Using std::pair

Master the use of std::pair with this comprehensive guide, encompassing everything from simple pair manipulation to template-based applications

ContinueView Course