Unordered Set & Unordered Multiset

In this tutorial, we will explore the unordered_set and unordered_multiset containers in C++. These are hash-based sets that provide average O(1) time complexity for insertions, deletions, and lookups. Understanding these containers is crucial for scenarios where fast access to elements is required, but order does not matter.

Introduction

The unordered_set and unordered_multiset containers are part of the Standard Template Library (STL) in C++. They store unique elements (unordered_set) or multiple occurrences of the same element (unordered_multiset). The key advantage of these containers is their average constant time complexity for operations like insertion, deletion, and lookup. This makes them highly efficient for scenarios where order does not matter.

In this tutorial, we will cover:

• The basic syntax and usage of unordered_set and unordered_multiset.
• How to use custom hash functions.
• Differences between unordered_set and set.
• Practical examples demonstrating their usage.

Core Content

Basic Syntax

Both unordered_set and unordered_multiset are templated classes that require a type parameter. They also allow for specifying a hash function, equality comparator, and allocator.

Unordered Set

The unordered_set container stores unique elements. Here is the basic syntax:

1#include <iostream>
2#include <unordered_set>
3 
4int main() {
5  std::unordered_set<int> mySet = {10, 20, 30};
6 
7  // Inserting elements
8  mySet.insert(40);
9 
10  // Checking if an element exists
11  if (mySet.find(20) != mySet.end()) {
12      std::cout << "Element found!" << std::endl;
13  }
14 
15  // Removing an element
16  mySet.erase(30);
17 
18  // Iterating over elements
19  for (const auto& elem : mySet) {
20      std::cout << elem << " ";
21  }
22  return 0;
23}

Custom Hash Functions

You can specify a custom hash function when declaring an unordered_set. This is useful when you want to define how elements are hashed.

1#include <iostream>
2#include <unordered_set>
3#include <string>
4 
5struct MyHash {
6  std::size_t operator()(const std::string& key) const {
7      return std::hash<std::string>{}(key);
8  }
9};
10 
11int main() {
12  std::unordered_set<std::string, MyHash> mySet = {"apple", "banana", "cherry"};
13 
14  // Inserting elements
15  mySet.insert("date");
16 
17  // Checking if an element exists
18  if (mySet.find("banana") != mySet.end()) {
19      std::cout << "Element found!" << std::endl;
20  }
21 
22  // Iterating over elements
23  for (const auto& elem : mySet) {
24      std::cout << elem << " ";
25  }
26  return 0;
27}

Summary

• unordered_set: Stores unique elements with average O(1) time complexity for operations.
• unordered_multiset: Allows multiple occurrences of the same element, also with average O(1) time complexity for operations.
• Use custom hash functions when needed to define how elements are hashed.
• Choose unordered_set when order is not important and you need fast access. Use set when maintaining a sorted order is necessary.

What's Next?

In the next tutorial, we will explore iterators in C++. Iterators provide a way to traverse through elements of containers like unordered_set and unordered_multiset. Understanding iterators is essential for efficient manipulation and traversal of container elements. Stay tuned!