Using std::unordered_set to store unique objects

An introduction to a "hash sets" - the ideal container type for when we want to store collections of unique objects
This lesson is part of the course:

Professional C++

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

05a.jpg
Ryan McCombe
Ryan McCombe
Posted

A set is a container that can store collections of unique values. The C++ standard library’s implementation of a set is called an unordered set.

Unordered sets cannot contain duplicate items. Additionally, as the name suggests, the items stored within them are not in any particular order. If we want to iterate over our set, and have that iteration be done in a predictable order, we can’t use unordered sets.

However, if we don’t have that particular requirement, unordered sets have extremely favorable performance characteristics. Inserting, removing and searching for an item can all be done in constant time.

Creating Unordered Sets

Unordered sets are available once the <unordered_set> header is included. They can be constructed in the same way as other containers - by specifying the type of data they will contain:

#include <unordered_set>
using std::unordered_set;

int main() {
  unordered_set<int> MySet;
}

The set can be populated with initial values:

unordered_set<int> MySet { 1, 2, 3 };

When providing initial values, the type of the set can be inferred using class template argument deduction (CTAD), so we can exclude the type:

unordered_set MySet { 1, 2, 3 };

Inserting Data Into Unordered Sets

We can add new data to our set in one of two ways. The preferred way is to construct the new object directly, using emplace. This will pass the argument to the constructor of type is containing - in this case, integers:

unordered_set<int> MySet;
MySet.emplace(4);

Using emplace is the preferred way of adding items to containers. But, sometimes we cannot construct our object in place, because it may already exist. For those scenarios, we can copy the element into the set using insert:

unordered_set<int> MySet;
int MyInt { 4 };
MySet.insert(MyInt);

The insert method is also what we would use if we need to move an item into the set:

unordered_set<unique_ptr<int>> MySet;
auto Pointer { std::make_unique<int>(4) };
MySet.insert(std::move(Pointer)); 

Removing Items from an Unordered Set

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

unordered_set MySet { 1, 2, 3 };
MySet.erase(1);

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

unordered_set MySet { 1, 2, 3 };
MySet.clear();

Checking if an Item is in an Unordered Set

The contains method returns true if the thing we pass as an argument is in the set:

unordered_set MySet { 1, 2, 3 };
if (MySet.contains(1)) {
  // true
}
if (MySet.contains(42)) {
  // false
}

The erase method additionally returns an integer representing the number of items that it removed. Given an unordered set cannot contain duplicates, it will therefore return 1 or 0.

This allows us to use it as a boolean, meaning we can both check if an item exists, and remove it in a single statement:

unordered_set MySet { 1, 2, 3 };
if (MySet.erase(1)) {
  // true
}
if (MySet.erase(1)) {
  // false
}

Counting Number of Items in an Unordered Set

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

unordered_set MySet { 1, 2, 3 };
MySet.size(); // 3

If we want to check if a set is empty, we can do that directly using the empty method:

unordered_set MySet { 1, 2, 3 };
MySet.empty(); // false

Iterating Over Unordered Sets

Iterators implement the begin, cbegin, end and cend methods, so can be iterated over using a range-based for-loop, with or without const:

unordered_set MySet { 1, 2, 3 };
for (const auto& num : MySet) {
  std::cout << num;
}

As the name suggests, an unordered_set does not guarantee any particular order when iterated over. In this case, the output was 321.

If controlling the order is important, the standard library’s set container keeps its items in order, at the expense of some performance overhead.

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:

#include <unordered_set>
#include <string>

struct Item {
  std::string Name;
};

int main() {
  // In their current form, Item objects cannot be in a hash set
  std::unordered_set<Item> SetA;

  // References to custom types have the same issue
  std::unordered_set<Item&> SetB;
}

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_set<Item>  SetA; // Error
std::unordered_set<Item&> SetB; // Error
std::unordered_set<Item*> SetC; // This Works

For now, the important thing to recognise is just that a type needs to meet these hashing requirements in order to be used in a set. 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

Using unordered maps to create associative containers

Create maps / dictionaries in C++ using the standard library's std::unordered_map container class.
DreamShaper_v7_fantasy_male_pirate_Sidecut_hair_swords_black_c_1.jpg
Contact|Privacy Policy|Terms of Use
Copyright © 2023 - All Rights Reserved