Hi everyone

In this tutorial we will talk about Multimap

So, What is Multimap actually?

Multimap is an associative container of C++ STL that stores data in key–value pairs, just like map. The elements are kept sorted by key automatically.

The one big difference from map is that multimap allows duplicate keys. The same key can appear multiple times, each mapped to a different value.

Unlike map, multimap does not have the [ ] subscript operator or the at() method. That is because, with duplicate keys, it is not clear which value the operator should return.

Multimap’s underlying data structure is a Self-Balancing Binary Search Tree (usually a Red-Black Tree). That is why all its major operations — insertion, deletion, search — take O(log n) time, and that is also why the elements stay sorted by key automatically.

Header File Inclusion for multimap

#include <map>

Multimap comes from the same header as map, so we include <map> for it.

Declaration & Initialization

Declaring an empty multimap —

multimap <int, string> studentMap;

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

Declaring a multimap with values —

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

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

After Initialization studentMap will look like this —

 

key	value
101	Imran
102	Linkon
102	Sakib
103	Rafi

 

Notice how the key 102 appears twice — once with “Linkon” and once with “Sakib”. This is perfectly valid in multimap.

Declaring a multimap with different data types —

Key and value can be of any type, even different from each other —

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

Declaring a multimap in descending order of keys —

By default, multimap stores keys in ascending order. If we want keys in descending order, we can pass greater<> as the third template parameter —

multimap <int, string, greater<int> > reverseMap;

Insertion

Insertion using insert() method with pair

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

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");

After all these insertions, studentMap will look like this —

 

key	value
101	Imran
102	Linkon
102	Sakib
102	Hasan
103	Rafi
104	Tanvir
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. That is why “Linkon”, “Sakib”, and “Hasan” appear in that exact order under key 102.

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 a multimap.

Counting occurrences of a key

count() method

Since 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 a multimap

Range-based for loop

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

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

Output will be —

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

Using iterator

We can also iterate using iterators directly —

multimap <int, string>::iterator it;

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

💡 Note on iteration order — Multimap iterates in sorted order of keys (ascending by default). For elements with the same key, they come out in the order they were inserted.

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

After deletion studentMap will look like this —

 

key	value
101	Imran
103	Rafi
104	Tanvir
105	Shuvo

 

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
auto it = studentMap.find(102);

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

This removes only one entry (the first 102 — “Linkon”), leaving the other two values for key 102 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 multimap, we can use clear() —

studentMap.clear();

After clear(), studentMap will be empty.

Size and Empty

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

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

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

Swapping

swap() method

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

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

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

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

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

lower_bound() and upper_bound()

Since multimap keys are stored in sorted order, we can use lower_bound() and upper_bound() just like we do for map. These two together actually give us what equal_range() gives — they are used internally by equal_range() anyway.

lower_bound(key) — returns an iterator to the first element whose key is not less than the given key.

upper_bound(key) — returns an iterator to the first element whose key is strictly greater than the given key.

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

auto lb = studentMap.lower_bound(102);
auto ub = studentMap.upper_bound(102);

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

Output will be —

102 - Linkon
102 - Sakib
102 - Hasan

Multimap vs Map

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

 

Property	multimap	map
Underlying data structure	Red-Black Tree	Red-Black Tree
Duplicate keys	Allowed	Not allowed
Order of keys	Sorted	Sorted
operator[ ] and at()	Not available	Available
count() returns	0, 1, 2, 3, … (total matches)	0 or 1 only
Use when	We need sorted keys and duplicates are allowed	We need sorted keys and each key is unique

 

Time Complexity

 

Operation	Description	Time Complexity
insert()	Insert a key–value pair	O(log n)
emplace()	Construct and insert a key–value pair in place	O(log n)
erase(key)	Remove all elements matching the key	O(log n + k) where k is the number of matches
erase(iterator)	Remove a single element at the iterator	O(1) amortized
find()	Find the first element with the given key	O(log n)
count()	Returns the number of elements matching the key	O(log n + k)
contains()	Check if a key exists (C++20)	O(log n)
equal_range()	Returns a pair of iterators covering all elements with the key	O(log n)
lower_bound()	Iterator to first key not less than given key	O(log n)
upper_bound()	Iterator to first key greater than given key	O(log n)
size()	Returns the number of elements	O(1)
empty()	Returns true if multimap is empty	O(1)
clear()	Removes all elements	O(n)
swap()	Swaps contents of two multimaps	O(1)
begin() / end()	Iterators to the beginning and end	O(1)

 

Applications

• • • • Phone book where one person can have multiple phone numbers
      • Dictionary where a word can have multiple meanings
      • Indexing books or articles by author (one author, many books)
      • Storing scores of students by roll number (a student can have multiple scores)
      • Event scheduling where multiple events can happen at the same time
      • Grouping items by category while keeping the categories sorted
      • Storing graph edges from the same source node (source → destination)
      • Range queries with lower_bound() and upper_bound()

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

Until then
Happy Coding