Tutorial on std::unordered_multiset in C++

std::unordered_multiset is part of the C++ Standard Library, and it’s available under the <unordered_set> header.

It provides an unordered collection of elements stored in a hash table, allowing duplicate elements (unlike std::unordered_set, which only allows unique elements).

Since it uses hashing, std::unordered_multiset provides average O(1)O(1) complexity for insertion, deletion, and search operations.

In this tutorial, we’ll cover:

1. Basic Syntax and Initialization

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

#include <iostream>
#include <unordered_set>

int main() {
    // Initialize an empty unordered multiset
    std::unordered_multiset<int> myMultiset;

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

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

    return 0;
}

2. Inserting Elements and Handling Duplicates

std::unordered_multiset allows duplicate elements. Each call to insert adds a new element, even if it’s already present in the multiset.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_multiset<int> myMultiset;

    // Inserting elements (including duplicates)
    myMultiset.insert(10);
    myMultiset.insert(20);
    myMultiset.insert(10);
    myMultiset.insert(30);

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

    return 0;
}

Output:

Elements in myMultiset: 10 20 10 30 

3. Counting Elements

The count function returns the number of times a specific element appears in the unordered_multiset.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_multiset<int> myMultiset = {10, 20, 10, 30, 20, 10};

    // Counting occurrences of elements
    std::cout << "Count of 10: " << myMultiset.count(10) << std::endl;
    std::cout << "Count of 20: " << myMultiset.count(20) << std::endl;
    std::cout << "Count of 30: " << myMultiset.count(30) << std::endl;

    return 0;
}

Output:

Count of 10: 3
Count of 20: 2
Count of 30: 1

4. Searching for Elements

You can search for an element using find, which returns an iterator to the element if it exists, or end() if it doesn’t. find only finds one instance of the element.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_multiset<int> myMultiset = {10, 20, 10, 30};

    int searchValue = 10;
    auto it = myMultiset.find(searchValue);
    if (it != myMultiset.end()) {
        std::cout << searchValue << " is in the multiset." << std::endl;
    } else {
        std::cout << searchValue << " is not in the multiset." << std::endl;
    }

    return 0;
}

Output:

10 is in the multiset.

5. Iterating Through Elements

You can use a range-based for loop or an iterator to iterate through all elements in an unordered_multiset. Elements are not ordered.

#include <iostream>
#include <unordered_set>

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

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

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

    return 0;
}

Output (order may vary due to the unordered nature of unordered_multiset):

Using range-based for loop: apple banana apple cherry 
Using iterator: apple banana apple cherry 

6. Erasing Elements

The erase function removes elements from the multiset. It can be used to:

• Remove a single instance of an element.
• Remove all instances of an element using equal_range.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_multiset<int> myMultiset = {10, 20, 10, 30, 10};

    // Erasing a single instance of 10
    auto it = myMultiset.find(10);
    if (it != myMultiset.end()) {
        myMultiset.erase(it);
    }

    // Printing the multiset after removing one "10"
    std::cout << "After erasing one instance of 10: ";
    for (const int& elem : myMultiset) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // Erasing all instances of 10
    myMultiset.erase(10);

    // Printing the multiset after removing all "10"s
    std::cout << "After erasing all instances of 10: ";
    for (const int& elem : myMultiset) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

Output:

After erasing one instance of 10: 20 10 30 10 
After erasing all instances of 10: 20 30 

7. Using Custom Hash Functions and Comparators

If you want to store custom types in an unordered_multiset, you need to define a custom hash function and an equality operator.

#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 for Point
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_multiset of Points with a custom hash function
    std::unordered_multiset<Point, PointHash> pointMultiset;

    // Insert points
    pointMultiset.insert({1, 2});
    pointMultiset.insert({3, 4});
    pointMultiset.insert({1, 2});

    // Print the points in the multiset
    std::cout << "Points in pointMultiset:" << std::endl;
    for (const auto& p : pointMultiset) {
        std::cout << "(" << p.x << ", " << p.y << ")" << std::endl;
    }

    // Count occurrences of a specific point
    Point searchPoint = {1, 2};
    std::cout << "Count of point (1, 2): " << pointMultiset.count(searchPoint) << std::endl;

    return 0;
}

Output:

Points in pointMultiset:
(1, 2)
(3, 4)
(1, 2)
Count of point (1, 2): 2

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 template argument to unordered_multiset, allowing it to handle Point objects.

Summary

In this tutorial, we covered:

1. Basic Syntax and Initialization for std::unordered_multiset
2. Inserting Elements and handling duplicates
3. Counting Elements using the count function
4. Searching for Elements with find
5. Iterating Through Elements using range-based for loops and iterators
6. Erasing Elements either partially or entirely
7. Using Custom Hash Functions and Comparators for storing custom data types

std::unordered_multiset is useful when you need an unordered collection of elements that can have duplicates, with efficient average O(1) performance for insertion, deletion, and searching.

This makes it ideal for scenarios where duplicate values are required and fast access is necessary.