Hi everyone

In this tutorial we will talk about Unordered Multimap

So, What is Unordered Multimap actually?

Unordered Multimap is an associative container of C++ STL that stores data in key–value pairs. It is basically a combination of two containers we already know —

- - - From unordered_map, it takes the hash table backing and the fast O(1) average lookup (no sorting, no specific order)
    - From multimap, it takes the ability to allow duplicate keys

Just like unordered_map, it does not keep the keys in any sorted order. And just like multimap, it does not have the [ ] subscript operator or the at() method — with duplicate keys, it is not clear which value those should return.

Unordered Multimap’s underlying data structure is a Hash Table. Because of hashing, all its major operations — insertion, deletion, search — take O(1) time on average. In the worst case (when many keys hash to the same bucket) the operations can go up to O(n), but in practice this is very rare.

Header File Inclusion for unordered_multimap

#include <unordered_map>

Unordered multimap comes from the same header as unordered_map, so we include <unordered_map> for it.

Declaration & Initialization

Declaring an empty unordered multimap —


unordered_multimap <int, string> studentMap;

Here, key type is int and value type is string. The unordered multimap is empty right now.

Declaring an unordered multimap with values —

From C++11 onwards, we can initialize an unordered multimap with values using curly braces —


unordered_multimap <int, string> studentMap = {
    { 101, "Imran" },
    { 102, "Linkon" },
    { 102, "Sakib" },
    { 103, "Rafi" }
};

After Initialization studentMap may look like this —

key	value
103	Rafi
101	Imran
102	Linkon
102	Sakib

Notice two things here — the keys are not in sorted order (103 comes before 101 and 102), but the two entries for key 102 appear next to each other. This is because unordered multimap groups all entries with the same key into the same bucket.

Declaring an unordered multimap with different data types —

Key and value can be of any hashable type —


unordered_multimap <string, int> ageMap;
unordered_multimap <char, vector<int> > charListMap;
unordered_multimap <int, pair<int, int> > rangeMap;

💡 Quick tip on key types — Since unordered multimap relies on hashing, the key type must have a valid hash function. All built-in types (int, string, char, double, etc.) work out of the box. But for custom types or pair, we need to provide our own hash function. We will see this in a bit.

Insertion

Insertion using insert() method with pair

Since unordered multimap does not support the [ ] operator, all insertions go through the insert() method. We can insert using a pair —


unordered_multimap <int, string> studentMap;

studentMap.insert(pair<int, string>(101, "Imran"));
studentMap.insert(pair<int, string>(102, "Linkon"));
studentMap.insert(pair<int, string>(102, "Sakib"));

Insertion using insert() method with make_pair

Same thing can be done with make_pair() for cleaner code —


studentMap.insert(make_pair(103, "Rafi"));

Insertion using insert() method with curly braces

From C++11 onwards, we can insert using curly braces directly —


studentMap.insert({ 104, "Tanvir" });
studentMap.insert({ 102, "Hasan" });

Insertion using emplace() method

emplace() constructs the pair in place, so it avoids an extra copy (since we are not using pair syntax explicitly) —


studentMap.emplace(105, "Shuvo");

💡 Quick tip on insertion order of duplicate keys — From C++11 onwards, when multiple values share the same key, they are stored in the same order they were inserted. So if we iterate over the values of key 102, we will see “Linkon”, “Sakib”, “Hasan” in that exact order.

Accessing the element

find() method

find() returns an iterator to the first occurrence of the given key, or end() if the key does not exist —


auto it = studentMap.find(102);

if (it != studentMap.end())
{
    cout << it->first << " " << it->second << endl;
}

Output will be – 102 Linkon

💡 Note on find() with duplicate keys — If the key appears multiple times, find() only returns the iterator to the first one. To get all the values for a given key, we need equal_range() (shown below).

equal_range() method

equal_range() returns a pair of iterators — the first one points to the start of the range of elements with the given key, and the second one points just past the end of that range.


auto range = studentMap.equal_range(102);

for (auto it = range.first; it != range.second; it++)
{
    cout << it->first << " - " << it->second << endl;
}

Output will be —

102 - Linkon
102 - Sakib
102 - Hasan

This is the most common and reliable way to read all values of a given key in an unordered multimap.

Counting occurrences of a key

count() method

Since unordered multimap allows duplicates, count() is actually useful — it returns the total number of elements that share the given key —


cout << studentMap.count(102) << endl;
cout << studentMap.count(101) << endl;
cout << studentMap.count(999) << endl;

Output will be —

3
1
0

contains() method (C++20)

From C++20 onwards, if we just want to check whether a key exists (without caring how many times), we can use contains() —


if (studentMap.contains(102))
{
    cout << "Key exists" << endl;
}

Iterating through an unordered multimap

Range-based for loop

The cleanest way to iterate through an unordered multimap is using a range-based for loop —


for (auto &element : studentMap)
{
    cout << element.first << " - " << element.second << endl;
}

Output may be something like —

105 - Shuvo
103 - Rafi
101 - Imran
102 - Linkon
102 - Sakib
102 - Hasan
104 - Tanvir

Using iterator

We can also iterate using iterators directly —


unordered_multimap <int, string>::iterator it;

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

💡 Note on iteration order — The overall key order is unpredictable (depends on the hash function), but entries sharing the same key always appear together in the iteration and follow the order they were inserted. If we need the keys sorted, we should use multimap instead.

Deletion

Deletion using erase() with key

If we pass a key directly to erase(), it removes all entries with that key, and returns how many were removed —


int removed = studentMap.erase(102);
cout << removed << " entries removed" << endl;

Output will be – 3 entries removed

Deletion using erase() with iterator

If we only want to remove a single entry with a given key (not all of them), we need to pass an iterator —


// re-inserting some values for the next example
studentMap.insert({ 102, "Linkon" });
studentMap.insert({ 102, "Sakib" });
studentMap.insert({ 102, "Hasan" });

// now removing only the first "102" entry that find() returns
auto it = studentMap.find(102);

if (it != studentMap.end())
{
    studentMap.erase(it);
}

This removes only one entry for key 102, leaving the other two intact.

💡 Quick tip — erase all vs erase one — erase(key) removes every entry with that key. erase(iterator) removes only the one entry the iterator points to. Use the iterator version when you want surgical removal.

Deletion using erase() with range

We can also delete a range of elements. A very common pattern is to combine this with equal_range() to remove all entries with a given key —


auto range = studentMap.equal_range(102);
studentMap.erase(range.first, range.second);

This does the same thing as erase(102), just expressed with iterators.

clear() method

If we want to remove all elements of the unordered multimap, we can use clear() —


studentMap.clear();

After clear(), studentMap will be empty.

Size and Empty


cout << studentMap.size() << endl;

if (studentMap.empty())
{
    cout << "Unordered multimap is empty" << endl;
}

size() returns the total number of elements (counting duplicates), and empty() returns true if the unordered multimap has no elements.

Swapping

swap() method

STL unordered multimap has a method named swap(), which swaps all the key–value pairs between two unordered multimaps —


unordered_multimap <int, string> mapOne = {
    { 1, "One" },
    { 1, "Uno" }
};

unordered_multimap <int, string> mapTwo = {
    { 10, "Ten" },
    { 20, "Twenty" },
    { 20, "Bish" }
};

// swapping values between two unordered multimaps
mapOne.swap(mapTwo);

After swapping, mapOne will have the elements of mapTwo, and mapTwo will have the elements of mapOne.

Unordered Multimap with pair as key

Sometimes we want to use a pair as the key — for example, to store events happening at a specific (day, hour) slot. But if we try this directly —


// this will give a compile error
unordered_multimap < pair<int, int>, string > eventMap;

We will get a compile error. The reason is that STL does not provide a default hash function for pair. We need to provide our own.

Writing a custom hash function —


struct pairHash
{
    size_t operator()(const pair<int, int> &p) const
    {
        // combine hashes of the two elements
        return hash<int>()(p.first) ^ (hash<int>()(p.second) << 1);
    }
};

unordered_multimap < pair<int, int>, string, pairHash > eventMap;

eventMap.insert({ {1, 9}, "Math Class" });
eventMap.insert({ {1, 9}, "Library Visit" });
eventMap.insert({ {2, 10}, "Lab Session" });

Accessing all values for a given key —


auto range = eventMap.equal_range({1, 9});

for (auto it = range.first; it != range.second; it++)
{
    cout << it->second << endl;
}

Output will be —

Math Class
Library Visit

💡 Note on custom hash — The hash function must be deterministic (same input always gives same output) and should spread the keys as evenly as possible across buckets. A poor hash function can push the performance from O(1) down to O(n).

Bucket Interface

Unordered multimap stores its elements in buckets. Each bucket holds keys that hash to the same index. All entries sharing the same key naturally land in the same bucket — that is why equal_range() is so fast. STL gives us a few methods to peek into this bucket structure.

bucket_count() method

Returns the total number of buckets currently in the unordered multimap —


cout << studentMap.bucket_count() << endl;

bucket() method

Returns the bucket number where a given key is stored —


cout << studentMap.bucket(101) << endl;

bucket_size() method

Returns the number of elements in a given bucket. This is especially useful in unordered multimap since multiple values with the same key pile up in the same bucket —


size_t b = studentMap.bucket(102);
cout << studentMap.bucket_size(b) << endl;

load_factor() method

Returns the average number of elements per bucket, calculated as size() / bucket_count(). A higher load factor means more collisions —


cout << studentMap.load_factor() << endl;

max_load_factor() method

Returns (or sets) the maximum load factor that unordered multimap allows. When the actual load factor crosses this value, the unordered multimap automatically rehashes —


cout << studentMap.max_load_factor() << endl;

// setting a new max load factor
studentMap.max_load_factor(0.75);

rehash() method

Forces the unordered multimap to rebuild its internal bucket structure with at least the given number of buckets —


studentMap.rehash(100);

reserve() method

Reserves enough buckets to hold at least the given number of elements without rehashing. This is very useful when we know how many elements we are about to insert —


// if we know we will insert around 10000 elements
studentMap.reserve(10000);

💡 Quick tip on reserve() — Calling reserve() before a big batch of insertions prevents multiple rehashes during insertion and can give a noticeable speed boost.

Unordered Multimap vs Multimap

This is a common confusion, so it is worth a quick note —

Property	unordered_multimap	multimap
Underlying data structure	Hash Table	Red-Black Tree
Duplicate keys	Allowed	Allowed
Order of keys	No specific order	Sorted
Insertion / Deletion / Search	O(1) average, O(n) worst	O(log n)
lower_bound() / upper_bound()	Not available	Available
Memory usage	Higher (due to buckets)	Lower
Use when	We need fast lookup with duplicate keys, order does not matter	We need sorted keys with duplicate keys allowed

Time Complexity

Operation	Description	Time Complexity
insert()	Insert a key–value pair	O(1) average, O(n) worst
emplace()	Construct and insert a key–value pair in place	O(1) average, O(n) worst
erase(key)	Remove all elements matching the key	O(k) average, O(n) worst (k = number of matches)
erase(iterator)	Remove a single element at the iterator	O(1) average
find()	Find the first element with the given key	O(1) average, O(n) worst
count()	Returns the number of elements matching the key	O(k) average, O(n) worst
contains()	Check if a key exists (C++20)	O(1) average, O(n) worst
equal_range()	Returns a pair of iterators covering all elements with the key	O(1) average, O(n) worst
size()	Returns the number of elements	O(1)
empty()	Returns true if unordered multimap is empty	O(1)
clear()	Removes all elements	O(n)
swap()	Swaps contents of two unordered multimaps	O(1)
bucket_count()	Returns the number of buckets	O(1)
bucket_size()	Returns the number of elements in a given bucket	O(1)
load_factor()	Returns average elements per bucket	O(1)
rehash()	Rebuilds the bucket structure	O(n) average, O(n²) worst
reserve()	Reserves buckets for expected element count	O(n) average, O(n²) worst
begin() / end()	Iterators to the beginning and end	O(1)

Applications

- - - Phone book where one person can have multiple phone numbers and fast lookup matters more than order
    - Tag systems where one item can have many tags (and one tag maps to many items)
    - Grouping log entries by event ID when we don’t care about time order
    - Storing URL → visitor mappings for web analytics
    - Inverted index in search engines where one word maps to many document IDs
    - Grouping transactions by account ID for fast lookup
    - Storing graph edges from the same source node when ordering is not needed
    - Any situation where multimap’s functionality is needed but sorted order is not

In the next tutorial we will talk about another useful STL container.

Until then
Happy Coding

Hi everyone

Header File Inclusion for unordered_multimap

Declaration & Initialization

Insertion

Accessing the element

Counting occurrences of a key

Iterating through an unordered multimap

Deletion

Size and Empty

Swapping

Unordered Multimap with pair as key

Bucket Interface

Unordered Multimap vs Multimap

Time Complexity

Applications

Leave a Comment Cancel Reply