C++ multimaps

---

Introduction

In C++, a multimap is an associative container that allows multiple elements with the same key. Unlike the std::map, where each key is unique, the std::multimap allows duplicate keys. The elements are automatically sorted according to the key, and they are stored in ascending order by default.

A multimap stores key-value pairs, where the key can appear more than once. It uses a self-balancing binary search tree (often a Red-Black Tree) for efficient operations such as insertion, deletion, and search. Like a map, operations in a multimap are performed in logarithmic time (O(log n)).

---

Syntax

The syntax to declare a multimap is:

std::multimap<KeyType, ValueType> multimap_name;

Where:

• KeyType: The type of the key (e.g., int, std::string).
• ValueType: The type of the value associated with each key.

You can also specify a custom comparator to order the keys:

std::multimap<KeyType, ValueType, Compare> multimap_name;

Where:

• Compare is a custom comparison function for the keys.

---

Declaring and Initializing a Multimap

Example 1: Basic Multimap Declaration

#include <iostream>
#include <map>

int main() {
    // Declare a multimap that associates an integer key with a string value
    std::multimap<int, std::string> multimap;

    // Inserting elements into the multimap
    multimap.insert({1, "Apple"});
    multimap.insert({1, "Banana"});
    multimap.insert({2, "Cherry"});
    multimap.insert({2, "Date"});
    multimap.insert({3, "Elderberry"});

    // Displaying the elements in the multimap
    for (const auto& pair : multimap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

Output:

1: Apple
1: Banana
2: Cherry
2: Date
3: Elderberry

Explanation:

• The key 1 appears twice with two different values: "Apple" and "Banana". Similarly, the key 2 appears twice.
• The elements are automatically ordered in ascending order based on the key.

---

Operations on Multimaps

1. Insert Elements

You can insert elements into a multimap using the insert() method. A multimap allows duplicate keys:

multimap.insert({1, "Grapes"});  // Key 1 is duplicated with value "Grapes"
multimap.insert({2, "Fig"});  // Key 2 is duplicated with value "Fig"

2. Erase Elements

You can remove elements by key or by iterator.

• Remove by key:

  multimap.erase(1);  // Removes all elements with key 1
  

• Remove by iterator:

  auto it = multimap.find(2);
  multimap.erase(it);  // Removes the element pointed to by the iterator
  

3. Find Elements

You can search for an element by key using the find() function. This function returns an iterator to the first element with the given key, or multimap.end() if the key does not exist.

auto it = multimap.find(2);
if (it != multimap.end()) {
    std::cout << "Found: " << it->first << " => " << it->second << std::endl;
} else {
    std::cout << "Key not found!" << std::endl;
}

4. Count Elements

You can count the number of elements with a particular key using the count() function. Since a multimap can have duplicate keys, count() will return the number of elements with the given key.

std::cout << "Count of key 1: " << multimap.count(1) << std::endl;  // Output: 2
std::cout << "Count of key 3: " << multimap.count(3) << std::endl;  // Output: 1

5. Size and Emptiness

You can check the size of the multimap and whether it is empty:

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

6. Clear the Multimap

You can remove all elements from the multimap using the clear() method:

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

---

Iterating Over a Multimap

You can iterate through the elements of a multimap using an iterator or a range-based for loop:

Example 1: Using Iterator

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

Example 2: Using Range-Based For Loop

for (const auto& pair : multimap) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}

---

Custom Sorting in Multimaps

By default, the std::multimap stores elements in ascending order based on the keys. However, you can define a custom sorting order by providing a comparator.

Example: Custom Sorting (Descending Order)

#include <iostream>
#include <map>

bool descendingOrder(int a, int b) {
    return a > b;  // Custom comparator for descending order
}

int main() {
    // Create a multimap with a custom comparator
    std::multimap<int, std::string, bool(*)(int, int)> multimap(descendingOrder);

    multimap.insert({1, "Apple"});
    multimap.insert({2, "Banana"});
    multimap.insert({3, "Cherry"});

    // Display elements in descending order
    for (const auto& pair : multimap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

Output:

3: Cherry
2: Banana
1: Apple

---

Advantages of Using std::multimap

1. Duplicate Keys: Unlike a std::map, a std::multimap allows multiple elements to have the same key, making it suitable for applications where duplicates are needed.
2. Efficient Searching: Like a map, operations such as search, insertion, and deletion are performed in logarithmic time (O(log n)) due to the underlying self-balancing binary search tree.
3. Automatic Ordering: Multimaps automatically sort their elements based on the keys, making it easier to manage ordered collections.
4. Versatile: You can store multiple values for each key and easily iterate over all values associated with a given key.

---

When to Use std::multimap

Use a std::multimap when:

• You need to store multiple values with the same key.
• You need the elements to be automatically sorted based on the key.
• You need efficient insertion, deletion, and search operations while allowing duplicate keys.

---

---