Tutorial on std::unordered_multimap in C++

std::unordered_multimap is part of the C++ Standard Library, available under the <unordered_map> header. It provides an unordered collection of key-value pairs, similar to std::unordered_map, but it allows multiple values for the same key.

Since it is implemented as a hash table, std::unordered_multimap provides average O(1) complexity for insertion, deletion, and search operations.

In this tutorial, we’ll cover:

1. Basic Syntax and Initialization

To use std::unordered_multimap, include the <unordered_map> header.

#include <iostream>
#include <unordered_map>

int main() {
    // Initialize an empty unordered multimap
    std::unordered_multimap<std::string, int> myMultimap;

    // Initialize with values
    std::unordered_multimap<std::string, int> anotherMultimap = {{"Alice", 25}, {"Bob", 30}, {"Alice", 28}, {"Charlie", 35}};

    // Print initial elements
    std::cout << "Elements in anotherMultimap:" << std::endl;
    for (const auto& pair : anotherMultimap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

2. Inserting Elements

std::unordered_multimap allows duplicate keys, so you can insert multiple values for the same key using insert or emplace.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_multimap<std::string, int> ageMap;

    // Inserting elements
    ageMap.insert({"Alice", 25});
    ageMap.insert({"Bob", 30});
    ageMap.insert({"Alice", 28});  // Duplicate key "Alice"

    // Printing elements
    std::cout << "Elements in ageMap:" << std::endl;
    for (const auto& pair : ageMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

Output:

Elements in ageMap:
Alice: 25
Bob: 30
Alice: 28

3. Accessing Elements with a Specific Key

Since std::unordered_multimap allows multiple values for the same key, find only returns an iterator to the first matching element. Use equal_range to access all values for a specific key.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_multimap<std::string, int> ageMap = {{"Alice", 25}, {"Bob", 30}, {"Alice", 28}, {"Charlie", 35}};

    // Accessing all values for a specific key
    std::cout << "All ages for Alice:" << std::endl;
    auto range = ageMap.equal_range("Alice");
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->second << std::endl;
    }

    return 0;
}

Output:

All ages for Alice:
25
28

4. Counting Occurrences of a Key

Use the count function to find the number of times a specific key appears in the unordered_multimap.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_multimap<std::string, int> ageMap = {{"Alice", 25}, {"Bob", 30}, {"Alice", 28}, {"Charlie", 35}};

    // Counting occurrences of a key
    std::cout << "Number of entries for Alice: " << ageMap.count("Alice") << std::endl;
    std::cout << "Number of entries for Bob: " << ageMap.count("Bob") << std::endl;

    return 0;
}

Output:

Number of entries for Alice: 2
Number of entries for Bob: 1

5. Removing Elements

The erase function allows you to remove elements by key or by iterator.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_multimap<std::string, int> ageMap = {{"Alice", 25}, {"Bob", 30}, {"Alice", 28}, {"Charlie", 35}};

    // Remove all instances of a specific key
    ageMap.erase("Alice");

    // Printing elements after removal
    std::cout << "Elements in ageMap after removing Alice:" << std::endl;
    for (const auto& pair : ageMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

Output:

Elements in ageMap after removing Alice:
Bob: 30
Charlie: 35

Note: erase(“Alice”) removes all entries with the key “Alice”.

6. Iterating Through Elements

You can use a range-based for loop or an iterator to go through all elements in the unordered_multimap. Elements are not stored in any specific order.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_multimap<std::string, int> ageMap = {{"Alice", 25}, {"Bob", 30}, {"Alice", 28}, {"Charlie", 35}};

    // Using a range-based for loop
    std::cout << "Using range-based for loop:" << std::endl;
    for (const auto& pair : ageMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // Using an iterator
    std::cout << "Using iterator:" << std::endl;
    for (auto it = ageMap.begin(); it != ageMap.end(); ++it) {
        std::cout << it->first << ": " << it->second << std::endl;
    }

    return 0;
}

Output (order may vary):

Using range-based for loop:
Alice: 25
Bob: 30
Alice: 28
Charlie: 35
Using iterator:
Alice: 25
Bob: 30
Alice: 28
Charlie: 35

7. Using Custom Hash Functions and Comparators

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

#include <iostream>
#include <unordered_map>

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_multimap of Points with a custom hash function
    std::unordered_multimap<Point, std::string, PointHash> pointMap;

    // Insert points
    pointMap.insert({{1, 2}, "A"});
    pointMap.insert({{3, 4}, "B"});
    pointMap.insert({{1, 2}, "C"});  // Duplicate key with value "C"

    // Print points in the map
    std::cout << "Points in pointMap:" << std::endl;
    for (const auto& pair : pointMap) {
        std::cout << "(" << pair.first.x << ", " << pair.first.y << "): " << pair.second << std::endl;
    }

    return 0;
}

Output:

Points in pointMap:
(1, 2): A
(3, 4): B
(1, 2): C

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

Summary

In this tutorial, we covered:

1. Basic Syntax and Initialization of std::unordered_multimap
2. Inserting Elements and handling duplicate keys
3. Accessing Elements with a Specific Key using equal_range
4. Counting Occurrences of a Key using count
5. Removing Elements by key or by iterator
6. Iterating Through Elements with range-based for loops and iterators
7. Using Custom Hash Functions and Comparators for handling custom data types

std::unordered_multimap is highly useful when you need a hash-based container that can store multiple values for the same key with efficient average O(1) performance for insertion, deletion, and lookups.