Tutorial on std::unordered_set in C++

std::unordered_set is part of the C++ Standard Library and is available under the <unordered_set> header.

It provides an unordered collection of unique elements, where each element is stored in a hash table.

Unlike std::set, which keeps elements in a specific order, std::unordered_set does not maintain any order, allowing faster insertion, deletion, and search operations (with an average time complexity of O(1)O(1)).

In this tutorial, we’ll cover:

Table of Contents

1. Basic Syntax and Initialization

To use std::unordered_set, include the <unordered_set> header file.

#include <iostream>
#include <unordered_set>

int main() {
    // Initialize an empty unordered set
    std::unordered_set<int> mySet;

    // Initialize with values
    std::unordered_set<int> anotherSet = {1, 2, 3, 4, 5};

    // Print initial elements
    std::cout << "Elements in anotherSet: ";
    for (const int& elem : anotherSet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

2. Inserting and Removing Elements

std::unordered_set offers insert to add elements and erase to remove elements. Duplicate elements are not allowed, so adding an already-existing element has no effect.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> mySet;

    // Inserting elements
    mySet.insert(10);
    mySet.insert(20);
    mySet.insert(30);

    // Attempt to insert duplicate
    mySet.insert(20);

    // Printing the set
    std::cout << "Elements in mySet: ";
    for (const int& elem : mySet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // Removing elements
    mySet.erase(20); // Remove element with value 20

    // Print set after removal
    std::cout << "Elements in mySet after erasing 20: ";
    for (const int& elem : mySet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

3. Searching for Elements

You can use the find method to search for elements in std::unordered_set. If the element is found, find returns an iterator to the element; otherwise, it returns end().

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> mySet = {10, 20, 30, 40};

    // Searching for an element
    int searchValue = 30;
    if (mySet.find(searchValue) != mySet.end()) {
        std::cout << searchValue << " is in the set." << std::endl;
    } else {
        std::cout << searchValue << " is not in the set." << std::endl;
    }

    // Checking for non-existing element
    searchValue = 50;
    if (mySet.find(searchValue) == mySet.end()) {
        std::cout << searchValue << " is not in the set." << std::endl;
    }

    return 0;
}

4. Common Member Functions

size(): Returns the number of elements.
empty(): Checks if the set is empty.
clear(): Removes all elements from the set.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> mySet = {1, 2, 3, 4};

    // Size of the set
    std::cout << "Size of mySet: " << mySet.size() << std::endl;

    // Check if set is empty
    if (!mySet.empty()) {
        std::cout << "mySet is not empty." << std::endl;
    }

    // Clear the set
    mySet.clear();
    std::cout << "Size of mySet after clearing: " << mySet.size() << std::endl;

    return 0;
}

5. Iterating Through an unordered_set

You can use a range-based for loop or an iterator to iterate through all elements in an unordered_set.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<std::string> mySet = {"apple", "banana", "cherry"};

    // Range-based for loop
    std::cout << "Using range-based for loop: ";
    for (const auto& fruit : mySet) {
        std::cout << fruit << " ";
    }
    std::cout << std::endl;

    // Iterator
    std::cout << "Using iterator: ";
    for (auto it = mySet.begin(); it != mySet.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

6. Custom Hash Function and Comparators

You can use std::unordered_set with custom types by defining a custom hash function and an equality function.

#include <iostream>
#include <unordered_set>

struct Point {
    int x, y;

    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// Custom hash function
struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ std::hash<int>()(p.y << 1);
    }
};

int main() {
    // Define an unordered_set of Points with custom hash function
    std::unordered_set<Point, PointHash> pointSet;

    // Inserting points
    pointSet.insert({1, 2});
    pointSet.insert({3, 4});
    pointSet.insert({5, 6});

    // Iterating through the set
    std::cout << "Points in pointSet:" << std::endl;
    for (const auto& p : pointSet) {
        std::cout << "(" << p.x << ", " << p.y << ")" << std::endl;
    }

    // Check if a specific point exists
    Point searchPoint = {3, 4};
    if (pointSet.find(searchPoint) != pointSet.end()) {
        std::cout << "Point (3, 4) is in the set." << std::endl;
    } else {
        std::cout << "Point (3, 4) is not in the set." << std::endl;
    }

    return 0;
}

In this example:

Point is a custom structure with x and y coordinates.
PointHash defines a custom hash function that combines x and y to create a unique hash.
The custom hash function is provided as a second argument to the unordered_set template, allowing std::unordered_set to work with Point objects.

Summary

In this tutorial, we covered:

Basic Syntax and Initialization of std::unordered_set
Inserting and Removing Elements with insert and erase
Searching for Elements using find
Common Member Functions like size, empty, and clear
Iterating Through Elements with range-based for loops and iterators
Custom Hash Functions and Comparators for using unordered_set with custom data types

std::unordered_set is highly efficient for scenarios where you need unique elements with fast insertion, deletion, and lookup operations, making it a valuable container in C++.

std::unordered_set