What is an unordered_multimap?

At its core, std::unordered_multimap is an unordered associative container that allows the storage of multiple occurrences of keys and their associated values. It shares similarities with std::unordered_map, but unlike a map, it permits multiple elements with equivalent keys. Each element is an unordered multimap is stored based on its hash value, facilitating efficient storage and retrieval.

Understanding Unordered Multimap

The unordered_multimap is part of the C++ STL and is implemented as a hash table. This means that the elements are not stored in any particular order based on their keys, instead, they are organized based on the hash value of the keys. As a result, access, insertion, and deletion operations have an average constant time complexity.

Syntax

In order to use unordered multimap, one need to include the unordered_map header file.

#include <unordered_map>

// Declaration
std::unordered_multimap<KeyType, ValueType> myMultimap;

In this syntax:

• KeyType represents the type of keys you want to use.
• ValueType represents the type of values associated with the keys.
• myMultimap is the name of the unordered_multimap object.

Functions of unordered_multimap

1 insert()

This function is used to insert a new key-value pair onto the unordered_multimap.

std::unordered_multimap<int, std::string> myMultimap;
myMultimap.insert({1, "apple"});
myMultimap.insert({2, "banana"});

Complexity Analysis:

• Average Time Complexity: O(1)
• Worst Time Complexity: O(n)

2 erase()

This function is used to remove elements from the unordered_multimap that match a given key or a specific iterator.

myMultimap.erase(2); // Erase all elements with key 2

Complexity Analysis:

• Average Time Complexity: O(1)
• Worst Time Complexity: O(n)

3 find()

This function is used to search for an element with a specific key and returns an iterator to the first occurrence.

auto it = myMultimap.find(1);
if (it != myMultimap.end()) {
    std::cout << "Value found: " << it->second << std::endl;
}

Complexity Analysis:

• Average Time Complexity: O(1)
• Worst Time Complexity: O(n)

4 count()

This function returns the number of elements with a specific key.

int numOccurrences = myMultimap.count(1);
std::cout << "Number of occurrences of key 1: " << numOccurrences << std::endl;

Complexity Analysis:

• Average Time Complexity: O(1)
• Worst Time Complexity: O(n)

5 empty()

This function checks whether the unordered_multimap is empty.

if (myMultimap.empty()) {
    std::cout << "The unordered_multimap is empty." << std::endl;
}

Complexity Analysis:

• Time Complexity: O(1)

6 size()

This function returns the number of elements in the unordered_multimap

std::cout << "Size of the unordered_multimap: " << myMultimap.size() << std::endl;

Complexity Analysis:

• Time Complexity: O(1)

7 clear()

This function removes all elements from the unordered_multimap.

myMultimap.clear();

Complexity Analysis:

• Time Complexity: O(n)