C++ unordered_multimap

---

Introduction

The std::unordered_multimap is an associative container in the C++ Standard Library that stores key-value pairs with the same key being allowed to appear multiple times. It is similar to std::unordered_map, but unlike the unordered_map, it allows multiple elements with the same key. Internally, it uses a hash table to store the key-value pairs, which gives it average constant-time complexity for insertion, searching, and deletion operations.

---

Syntax

To declare an unordered multimap, use the following syntax:

Copy Codestd::unordered_multimap<KeyType, ValueType> unordered_multimap_name;

Where:

• KeyType is the type of the key.
• ValueType is the type of the value associated with the key.

You can also specify a custom hash function and comparison function:

Copy Codestd::unordered_multimap<KeyType, ValueType, Hash, Compare> unordered_multimap_name;

Where:

• Hash is the hash function used for the keys (default is std::hash).
• Compare is a comparison function used to compare keys (optional).

---

Declaring and Initializing an Unordered Multimap

Example 1: Basic Unordered Multimap Declaration

Copy Code#include <iostream>
#include <unordered_map>

int main() {
    // Declare an unordered multimap of integers as keys and strings as values
    std::unordered_multimap<int, std::string> ummap;

    // Insert key-value pairs into the unordered multimap
    ummap.insert({1, "Apple"});
    ummap.insert({2, "Banana"});
    ummap.insert({2, "Blueberry"});
    ummap.insert({3, "Cherry"});
    ummap.insert({1, "Avocado"});

    // Display the unordered multimap
    for (const auto& pair : ummap) {
        std::cout << pair.first << " -> " << pair.second << std::endl;
    }

    return 0;
}

Output:

Copy Code1 -> Apple
2 -> Banana
2 -> Blueberry
3 -> Cherry
1 -> Avocado

Note: As shown, an unordered multimap allows multiple values with the same key (2 -> Banana and 2 -> Blueberry), and the order of the elements is not guaranteed.

---

Operations on Unordered Multimap

1. Insert Elements

You can insert key-value pairs into the unordered multimap using the insert() method. Multiple entries with the same key are allowed.

Copy Codeummap.insert({3, "Cantaloupe"});
ummap.insert({2, "Grapefruit"});

2. Find Elements

To search for a key in the unordered multimap, you can use the find() method, which returns an iterator to the first element with that key (or unordered_multimap::end() if not found).

Copy Codeauto it = ummap.find(2);  // Find the first occurrence of key 2
if (it != ummap.end()) {
    std::cout << "Found: " << it->first << " -> " << it->second << std::endl;
} else {
    std::cout << "Element not found!" << std::endl;
}

3. Count Elements

To get the number of elements with a specific key, use the count() method. This will return the number of elements that have the given key. Since unordered_multimap allows multiple elements with the same key, count() will return a value greater than 1 if the key is duplicated.

Copy Codestd::cout << "Count of key 2: " << ummap.count(2) << std::endl;  // Output: 2

4. Erase Elements

You can erase elements using the erase() method. If you provide a key, it will remove all elements with that key. If you provide an iterator, it will remove the specific element at that position.

• Remove by key:

  Copy Codeummap.erase(2);  // Removes all elements with key 2
  

• Remove by iterator:

  Copy Codeauto it = ummap.find(3);  // Find an element with key 3
  ummap.erase(it);  // Removes that specific element
  

5. Size and Emptiness

You can check the size of the unordered multimap and whether it is empty using the size() and empty() methods.

Copy Codestd::cout << "Size of unordered multimap: " << ummap.size() << std::endl;
std::cout << "Is unordered multimap empty? " << (ummap.empty() ? "Yes" : "No") << std::endl;

6. Clear the Unordered Multimap

To remove all elements from the unordered multimap, use the clear() method:

Copy Codeummap.clear();  // Removes all elements from the unordered multimap

---

Iterating Over an Unordered Multimap

You can iterate over the elements of an unordered multimap using iterators or a range-based for loop. Since an unordered multimap allows multiple values with the same key, each occurrence of a key-value pair will be visited.

Example 1: Using Iterator

Copy Codefor (auto it = ummap.begin(); it != ummap.end(); ++it) {
    std::cout << it->first << " -> " << it->second << std::endl;
}

Example 2: Using Range-Based For Loop

Copy Codefor (const auto& pair : ummap) {
    std::cout << pair.first << " -> " << pair.second << std::endl;
}

---

Custom Hash Function for Unordered Multimap

When using a custom type as a key in the unordered multimap, you need to provide a custom hash function.

Example: Custom Hash Function for a Class

Copy Code#include <iostream>
#include <unordered_map>
#include <string>

class Product {
public:
    std::string name;
    int id;

    Product(std::string name, int id) : name(name), id(id) {}

    bool operator==(const Product& other) const {
        return id == other.id;
    }
};

struct ProductHash {
    size_t operator()(const Product& p) const {
        return std::hash<int>()(p.id);  // Hash by product ID
    }
};

int main() {
    std::unordered_multimap<Product, std::string, ProductHash> ummap;

    ummap.insert({Product("Laptop", 101), "Available"});
    ummap.insert({Product("Smartphone", 102), "Out of Stock"});
    ummap.insert({Product("Laptop", 101), "On Sale"});  // Inserting duplicate key

    for (const auto& pair : ummap) {
        std::cout << pair.first.name << " (ID: " << pair.first.id << ") -> " << pair.second << std::endl;
    }

    return 0;
}

Output:

Copy CodeLaptop (ID: 101) -> Available
Smartphone (ID: 102) -> Out of Stock
Laptop (ID: 101) -> On Sale

---

Advantages of Using std::unordered_multimap

1. Efficient Lookups: Provides O(1) average time complexity for insertion, deletion, and searching operations, thanks to the hash table-based implementation.
2. Supports Duplicate Keys: Allows multiple key-value pairs with the same key, which is not possible in unordered_map.
3. Unordered Storage: The unordered nature of the multimap makes insertion and deletion operations faster, although the order of elements is not guaranteed.
4. Efficient Range Queries: Supports efficient range queries and is useful when you need to find multiple values associated with a single key.

---

When to Use std::unordered_multimap

• Storing Multiple Values for the Same Key: When you need to store multiple values associated with the same key but don't care about the order in which they are stored or retrieved.
• Efficient Search Operations: When you need fast insertion, deletion, and search operations, especially when dealing with large datasets.
• Frequency Counting: When counting the frequency of items (e.g., counting words in a document), but allowing multiple values to share the same key.

---

---