In this article we will discuss the MultiMap in C++.

Multi-map in C++ is an associative container like map. It internally store elements in key value pair. But unlike map which store only unique keys, multimap can have duplicate keys.

Also, it internally keep elements in sorted order of keys. By default it uses < operator to compare the keys.

MultiMap Usage Scenario

Let’s discuss a practical scenario, where we should use multi-map. Suppose, given a string and we want to store the position of each character in that string. For example, String is “this is it” and position of each character in string is,

t occurs at 0 , 9
h occurs at 1
i occurs at 2 , 5 , 8
s occurs at 3 , 6

Here key is ‘char’ and value is ‘int’ i.e. position of character in string. So, there are multiple key value pairs with duplicate keys. Therefore, we will use multi-map to store this elements because in multi-map we can have duplicate keys. MultiMap will store the above data in following  key value pairs i.e.

h :: 1
i :: 2
i :: 5
i :: 8
s :: 3
s :: 6
t :: 1
t :: 9

It will have duplicate keys and elements will be sorted based on keys.

Declaring a Multi-Map in C++

Let’s create a multi-map of char & int i.e.

std::multimap<char, int> mmapOfPos;

We need to include following header file for it,
#include <map>

Initializing a MultiMap with C++11 Initializer list

Let’s initialize this multimap with initializer list i.e.

std::multimap<char, int> mmapOfPos ={
		{'t', 1},
		{'h', 1},
		{'i', 2},
		{'s', 3},
		{'i', 5},
		{'s', 6},
		{'i', 8},
};

Inserting a key value pair in MultiMap

We can also insert a key value pair in multimap using insert() member function i.e.

mmapOfPos.insert(std::pair<char, int>('t', 9));

Iterating over the Multi-Map using Iterator

// Iterate over the multimap using Iterator
for(std::multimap<char, int>::iterator it = mmapOfPos.begin(); it != mmapOfPos.end(); it++)
	std::cout<<it->first<<" :: "<<it->second<<std::endl;

Iterating over the MultiMap using C++11 Range Based for loop

for(std::pair<char, int> elem : mmapOfPos)
	std::cout<<elem.first<<" :: "<<elem.second<<std::endl;

Complete Example

Complete example of Muli Map in C++ is as follows,

#include <iostream>
#include <map>
#include <iterator>
#include <algorithm>

int main()
{
	//Multi Map of char and int
	// Initializing with initializer list
	std::multimap<char, int> mmapOfPos ={
			{'t', 1},
			{'h', 1},
			{'i', 2},
			{'s', 3},
			{'i', 5},
			{'s', 6},
			{'i', 8},
	};

// Inserting an element in map
	mmapOfPos.insert(std::pair<char, int>('t', 9));

// Iterate over the multimap using Iterator
	for (std::multimap<char, int>::iterator it = mmapOfPos.begin();
			it != mmapOfPos.end(); it++)
		std::cout << it->first << " :: " << it->second << std::endl;

	std::cout << "****************************************" << std::endl;

// Iterate over the multimap using range based for loop
	for (std::pair<char, int> elem : mmapOfPos)
		std::cout << elem.first << " :: " << elem.second << std::endl;

	return 0;
}

Output:
h :: 1
i :: 2
i :: 5
i :: 8
s :: 3
s :: 6
t :: 1
t :: 9
****************************************
h :: 1
i :: 2
i :: 5
i :: 8
s :: 3
s :: 6
t :: 1
t :: 9

To compile the above code in lunux use following command,

g++ –std=c++11 example.cpp

In the next article we will discuss how to find all values associated with a key in multimap i.e.

Find All values associated with a Key in MultiMap using equal_range()

Join a list of 2000+ Programmers for latest Tips & Tutorials