Multimap in C++ STL

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

Reading time: 45 minutes

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 &lt operator to compare the keys.
Multimap is a container that contains a sorted list of key-value pairs, while permitting multiple entries with the same key. Sorting is done according to the comparison function Compare, applied to the keys. Search, insertion, and removal operations have logarithmic complexity.

The order of the key-value pairs whose keys compare equivalent is the order of insertion and does not change.

Example - 1

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.

Example - 2

A multimap of Employees where employee age is the key and name is the value can be represented as:

Keys	Values
23	Ayan
28	Shreya
25	Deepak
25	Amit

Multimap employee has duplicate keys age.

Syntax

template < class Key,                    // multimap::key_type  
           class T,                     // multimap::mapped_type  
           class Compare = less<Key>,  // multimap::key_compare  
           class Alloc = allocator<pair<const Key,T> > // multimap::allocator_type  
           > class multimap;

Parameter :

key: The key data type to be stored in the multimap.
type: The data type of value to be stored in the multimap.
compare: A comparison class that takes two arguments of the same type bool and returns a value. This argument is optional and the binary predicate less<"key"> is the default value.
alloc: Type of the allocator object. This argument is optional and the default value is allocator .

Implementing Multimap

Multimaps can easily be created using the following statement:

typedef pair<const Key, T> value_type;

The above form will use to create a multimap with key of type Key_type and value of type value_type. One important thing is that key of a multimap and corresponding values are always inserted as a pair, you cannot insert only key or just a value in a multimap.

Example

#include <iostream>  
#include <map>  
#include <string>  
using namespace std;  
  
int main()  
{  
    multimap<string, string> m = {  
            {"India","New Delhi"},  
            {"India", "Hyderabad"},  
            {"United Kingdom", "London"},  
            {"United States", "Washington D.C"}  
    };  
      
    cout << "Size of map m: " << m.size() <<endl;      
    cout << "Elements in m: " << endl;  
      
    for (multimap<string, string>::iterator it = m.begin(); it != m.end(); ++it)  
    {  
       cout << "  [" << (*it).first << ", " << (*it).second << "]" << endl;  
    }  
  
    return 0;  
}

Output:

Size of map m: 4
Elements in m: 
  [India, New Delhi]
  [India, Hyderabad]
  [United Kingdom, London]
  [United States, Washington D.C]

Basic Functions associated with multimap

1. `begin()` & `end()` :

a. begin :
It is a built-in function in C++ STL which returns an iterator referring to the first element in the multimap container. Since multimap container contains the element in an ordered way, begin() will point to that element that will come first according to the container’s sorting criterion.

Syntax

multimap_name.begin()

Parameters : The function does not accept any parameter.
Return Value : The function returns an iterator referring to the first element in the multimap container

Exceptions :

This function never throws exception.

Example

#include <iostream>  
#include <map>  
using namespace std;  
int main ()  
{  
  multimap<char,string> mymultimap;  
  mymultimap = {   
               {'a',"Java"},  
               {'b', "C++"},  
               {'b', "Python"},  
               {'a', "Android"}  
               };  
   
  // show content:  
  for (multimap<char,string>::iterator it=mymultimap.begin(); it!=mymultimap.end(); ++it)  
    cout << it->first << " => " << it->second << '\n';  
  
  return 0;  
}

Output:

a => Java
a => Android
b => C++
b => Python

b. end() :
It is a built-in function in C++ STL which returns an iterator to the theoretical element that follows last element in the multimap. Since multimap container contains the element in an ordered way, end() will point to that theoretical position which follows the last element according to the container’s sorting criterion.

Syntax:

multimap_name.end()

Parameters : The function does not accept any parameter.
Return Value : The function returns an iterator referring to the first element in the multimap container

Exception

This member function never throws exception.

Example

In the following example, end() function is used to return an iterator pointing next to the last element in the mymultimap multimap.

#include <iostream>  
#include <map>  
using namespace std;  
int main ()  
{  
  multimap<char,string> mymultimap;  
  mymultimap = {   
               {'a',"Java"},  
               {'b', "C++"},  
               {'b', "Python"},  
               {'a', "Android"}  
               };  
  // show content:  
  for (multimap<char,string>::iterator it=mymultimap.begin(); it!=mymultimap.end(); ++it)  
    cout << it->first << " => " << it->second << '\n';  
  return 0;  
}

Output:

a => Java
a => Android
b => C++
b => Python

2. `cbegin()` & `cend()` :

a. cbegin() :
It is a built-in function in C++ STL which returns a constant iterator referring to the first element in the multimap container. Since multimap container contains the element in an ordered way, cbegin() will point to that element that will come first according to the container’s sorting criterion.

Syntax:

multimap_name.cbegin()

Parameters : The function does not accept any parameter.
Return Value : The function returns a constant iterator referring to the first element in the multimap container.

Exception

This member function never throws exception.

Example

#include <bits/stdc++.h> 
using namespace std; 
  
int main() 
{ 
  
    // initialize container 
    multimap<int, int> mp; 
  
    // insert elements in random order 
    mp.insert({ 2, 30 }); 
    mp.insert({ 1, 40 }); 
    mp.insert({ 3, 60 }); 
    mp.insert({ 4, 20 }); 
    mp.insert({ 5, 50 }); 
  
    auto ite = mp.cbegin(); 
  
    cout << "The first element is: "; 
    cout << "{" << ite->first << ", "
         << ite->second << "}\n"; 
  
    // prints the elements 
    cout << "\nThe multimap is : \n"; 
    cout << "KEY\tELEMENT\n"; 
    for (auto itr = mp.cbegin(); itr != mp.cend(); ++itr) { 
        cout << itr->first 
             << '\t' << itr->second << '\n'; 
    } 
    return 0; 
}

Output:

The first element is: {1, 40}

The multimap is : 
KEY    ELEMENT
1    40
2    30
3    60
4    20
5    50

b. cend() :
It is a builtin function in C++ STL which returns a constant iterator pointing to the theoretical element that follows last element in the multimap. Since multimap container contains the element in an ordered way, cend() will point to that follows the last element according to the container’s sorting criterion.

Syntax:

multimap_name.cend()

Parameters : The function does not accept any parameter.
Return Value : The function returns a constant iterator pointing to the theoretical element that follows the last element in the multimap.

Exception

This member function never throws exception.

Example

In the following example, cend() function is used to return a const_ iterator pointing next to the last element in the mymultimap multimap.

#include <iostream>  
#include <map>  
using namespace std;  
int main ()  
{  
  multimap<char,string> mymultimap;  
  mymultimap = {   
               {'a',"Java"},  
               {'b', "C++"},  
               {'b', "Python"},  
               {'a', "Android"}  
               };  
  // print content:  
  cout << "mymultimap contains:";  
  for (auto it = mymultimap.cbegin(); it != mymultimap.cend(); ++it)  
    cout << " [" << (*it).first << ':' << (*it).second << ']';  
  cout << '\n';  
  return 0;  
}

Output:

mymultimap contains: [a:Java] [a:Android] [b:C++] [b:Python]

3. `rbegin()` :

It is a built-in-function in C++ STL which returns an iterator pointing to the last element of the container.
That means, rbegin() function is used to return a reverse iterator referring to the last element of the multimap container.
A reverse iterator of multimap moves in reverse direction and incrementing it until it reaches to the beginning (First element) of the multimap container.

Syntax:

multimap_name.rbegin()

Parameters : The function does not take any parameter.
Return Value : The function returns a reverse iterator pointing to the last element of the container.

Exception

This member function never throws exception.

Note : Reverse iterators iterate backwards i.e when they are increased they move towards the beginning of the container

Example

In the following example, rbegin() function is used to return a reverse iterator pointing to the last element in the mymultimap multimap.
Because multimap stores the elements in sorted order of keys therefore, iterating over a multimap will result in above order i.e. sorted order of keys.

#include <iostream>  
#include <map>  
using namespace std;  
int main ()  
{  
  multimap<char,int> mymultimap;  
  mymultimap = {  
               {'a', 100},  
               {'b', 200},  
               {'a', 300},  
               {'c', 300}  
               };  
  // show content:  
  multimap<char,int>::reverse_iterator rit;  
  for (rit=mymultimap.rbegin(); rit!=mymultimap.rend(); ++rit)  
    cout << rit->first << " = " << rit->second << '\n';  
  return 0;  
}

Output:

c = 300
b = 200
a = 300
a = 100

4. `rend()` :

The C++ multimap rend() function is used to return an iterator to the end of the multimap (not the last element but the past last element) in reverse order. This is similar to the element preceding the first element of the non-reversed container.

Note : This is a placeholder. No element exists in this location and attempting to access is undefined behavior.

Syntax

multimap_name.rend()

Parameters : The function does not take any parameter.
Return Value : The function returns a reverse iterator pointing to the reverse end of the multimap container i.e a reverse iterator pointing to the position right before the first element of the multimap.The iterator returned by multimap::rend() cannot be dereferenced.

Example

In the following example, rend() function is used to return a reverse iterator to the element following the last element of the reversed container.
Because multimap stores the elements in sorted order of keys therefore, iterating over a multimap will result in sorted order of keys.

#include <iostream>  
#include <map>  
using namespace std;  
int main ()  
{  
  multimap<char,int> mymultimap;  
  mymultimap =  {  
                {'a', 100},  
                {'b', 200},  
                {'c', 100},  
                {'b', 400}  
                };  
  // show content:  
  multimap<char,int>::reverse_iterator rit;  
  for (rit=mymultimap.rbegin(); rit!=mymultimap.rend(); ++rit)  
    cout << rit->first << " = " << rit->second << '\n';  
  return 0;  
}

Output:

c = 100
b = 400
b = 200
a = 100

5. `crbegin()` :

It is a built-in function in C++ STL which returns a constant reverse iterator referring to the last element in the multimap container. Since multimap container contains the element in an ordered way, crbegin() will point to that element that will come last according to the container’s sorting criterion.
A constant reverse iterator of multimap moves in reverse direction and incrementing it until it reaches to the beginning (First element) of the multimap container and points to the constant element.

Syntax:

multimap_name.crbegin()

Parameters : The function does not accept any parameter.
Return Value : The function returns a constant reverse iterator referring to the last element in the multimap container.

Example

In the following example, crbegin() function is used to return a constant reverse iterator pointing to the last element in the mymultimap multimap.
Because multimap stores the elements in sorted order of keys therefore, iterating over a multimap will result in sorted order of keys.

#include <iostream>  
#include <map>  
using namespace std;  
int main ()  
{  
  multimap<char,string> mymultimap;  
  mymultimap = {   
               {'a',"Java"},  
               {'b', "C++"},  
               {'b', "Python"},  
               {'a', "Android"}  
               };  
  cout << "mymultimap in reverse order:";  
  for (auto rit = mymultimap.crbegin(); rit != mymultimap.crend(); ++rit)  
    cout << " [" << rit->first << ':' << rit->second << ']';  
    cout << '\n';  
  return 0;  
}

Output:

mymultimap in reverse order: [b:Python] [b:C++] [a:Android] [a:Java]

6. `crend()` :

It is a built-in function in C++ STL which returns a constant reverse iterator pointing to the theoretical element before the first element in the multimap. Since multimap container contains the element in an ordered way, crend() will point to the element theoretically before the first element according to the container’s sorting criterion.

Syntax:

multimap_name.crend()

Parameters : The function does not accept any parameter.
Return Value : The function returns a constant reverse iterator pointing to the theoretical element before the first element in the multimap.

Example

In the following example, crend() function is used to return a constant reverse iterator to the element following the last element of the reversed container.
Because multimap stores the elements in sorted order of keys therefore, iterating over a multimap will result in sorted order of keys.

#include <iostream>  
#include <map>  
using namespace std;  
int main ()  
{  
  multimap<char,int> mymultimap;  
  mymultimap= {  
            {'a', 100},  
            {'a', 200},  
            {'c', 300},  
            {'b', 400}  
           };  
  // show content:  
  multimap<char,int>::const_reverse_iterator rit;  
  for (rit=mymultimap.crbegin(); rit!=mymultimap.crend(); ++rit)  
    cout << rit->first << " = " << rit->second << '\n';  
  return 0;  
}

Output:

c = 300
b = 400
a = 200
a = 100

7. `insert()` :

It is a built-in function in C++ STL which is used to insert elements in the multimap container.
There are three ways :-

a. Syntax :

iterator multimap_name.insert({key, element})

Parameters : The function accepts a pair that consists of a key and element which is to be inserted into the multimap container.
Return Value : The function returns an iterator pointing to the new element in the container.

Example :

#include <bits/stdc++.h> 
using namespace std; 
  
int main() 
{ 
  
    // initialize container 
    multimap<int, int> mp; 
  
    // insert elements in random order 
    mp.insert({ 2, 30 }); 
    mp.insert({ 1, 40 }); 
    mp.insert({ 3, 60 }); 
    mp.insert({ 2, 20 }); 
    mp.insert({ 5, 50 }); 
  
    // prints the elements 
    cout << "KEY\tELEMENT\n"; 
    for (auto itr = mp.begin(); itr != mp.end(); ++itr) { 
        cout << itr->first 
             << '\t' << itr->second << '\n'; 
    } 
    return 0; 
}

Output:

KEY    ELEMENT
1    40
2    30
2    20
3    60
5    50

b. Syntax:

iterator multimap_name.insert(iterator position, {key, element})

Parameters : The function accepts two parameters which is described below:
i. {key, element} : this specifies a pair that consists of a key and element which is to be inserted into the multimap container.
ii. position : this does not specify the position where the insertion is to be done, it only points a position from where the searching operation for insertion is to be started. The insertion is done according to the order which is followed by the multimap container.
Return Value : The function returns an iterator pointing to the new element in the container

Example

#include <bits/stdc++.h> 
using namespace std; 
  
int main() 
{ 
  
    // initialize container 
    multimap<int, int> mp; 
  
    // insert elements in random order 
    mp.insert({ 2, 30 }); 
    mp.insert({ 1, 40 }); 
  
    auto it = mp.find(2); 
  
    // inserts {3, 6} starting the search from 
    // position where 2 is present 
    mp.insert(it, { 3, 60 }); 
  
    // prints the elements 
    cout << "KEY\tELEMENT\n"; 
    for (auto itr = mp.begin(); itr != mp.end(); ++itr) { 
        cout << itr->first 
             << '\t' << itr->second << '\n'; 
    } 
    return 0; 
}

Output:

KEY    ELEMENT
1    40
2    30
3    60

c. Syntax:

iterator multimap_name.insert(iterator position1, iterator position2)

Parameters : The function accepts two parameters position1 and position2 which specifies the range of elements. All the elements in the range [position1, last) are inserted in the multimap container.
Return Value : The function returns an iterator pointing to the new element in the container

Example

#include <bits/stdc++.h> 
using namespace std; 
  
int main() 
{ 
  
    // initialize container 
    multimap<int, int> mp, mp1; 
  
    // insert elements in random order 
    mp.insert({ 2, 30 }); 
    mp.insert({ 1, 40 }); 
  
    // inserts all elements in range [begin, end) 
    // in mp1 
    mp1.insert(mp.begin(), mp.end()); 
  
    // prints the elements 
    cout << "Elements in mp1 are\n"; 
    cout << "KEY\tELEMENT\n"; 
    for (auto itr = mp1.begin(); itr != mp1.end(); ++itr) { 
        cout << itr->first 
             << '\t' << itr->second << '\n'; 
    } 
    return 0; 
}

Output:

Elements in mp1 are
KEY    ELEMENT
1    40
2    30

8. `emplace()` :

This function is used to extend the multimap container by inserting new elements into the container. Elements are built directly (neither copied nor moved).
The constructor of the element is called by giving the arguments args passed to this function.It effectively increases the container size by one as multimap is the container that stores multiple keys with same values.

Syntax:

multimap_name.emplace(key, element)

Parameters : The function accepts two mandatory parameters which are described below:
i. key – specifies the key to be inserted in the multimap container.
ii. element – specifies the element to the key which is to be inserted in the multimap container.
Return Value : The function does not return anything.

Example

In the following example, elements are inserted in the multimap and when we try to add the same key George then it will allow us to insert duplicates.

#include <map>    
#include <string>    
#include <iostream>    
using namespace std;    
    
template <typename M> void print(const M& m) {    
    cout << m.size() << " elements: " << endl;    
    
    for (const auto& p : m) {    
        cout << "(" << p.first <<  "," << p.second << ") ";    
    }    
    
    cout << endl;    
}    
    
int main()    
{    
    multimap<string, string> m1;    
    
    m1.emplace("George", "Accounting");    
    m1.emplace("Amit", "Accounting");    
    m1.emplace("Dhruv", "Engineering");    
    
    cout << "multimap modified, now contains ";    
    print(m1);    
    cout << endl;    
    m1.emplace("George", "Engineering");    
    cout << "multimap modified, now contains ";    
    print(m1);    
    cout << endl;    
}

Output:

multimap modified, now contains 3 elements: 
(Amit,Accounting) (Dhruv,Engineering) (George,Accounting) 

multimap modified, now contains 4 elements: 
(Amit,Accounting) (Dhruv,Engineering) (George,Accounting) (George,Engineering)

9. `emplace_hint()` :

It is a built-in function in C++ STL which inserts the key and its element in the multimap container with a given hint. It effectively increases the container size by one as multimap is the container that stores multiple keys with same values. The hint provided does not affect the position to be entered, it only increases the speed of insertion as it points to the position from where the search for the ordering is to be started. It inserts in the same order which is followed by the container. It works similarly to multimap::emplace() function but is at times faster then it if the user provides position accurately.

Syntax:

multimap_name.emplace_hint(position, key, element)

Parameters :* The function accepts three mandatory parameters key which are described as below:
i. key – specifies the key to be inserted in the multimap container.
ii. element – specifies the element to the key which is to be inserted in the multimap container.
iii. position – specifies the position from where the search operation for the ordering is to be started, hence making the insertion faster.
Return Value : The function does not return anything.

Example

#include <bits/stdc++.h> 
using namespace std; 
  
int main() 
{ 
  
    // initialize container 
    multimap<int, int> mp; 
  
    // insert elements in random order 
    mp.emplace_hint(mp.begin(), 2, 30); // faster 
    mp.emplace_hint(mp.begin(), 1, 40); // faster 
    mp.emplace_hint(mp.begin(), 2, 60); // slower 
    mp.emplace_hint(mp.begin(), 2, 20); // slower 
    mp.emplace_hint(mp.begin(), 1, 50); // faster 
    mp.emplace_hint(mp.begin(), 1, 50); // faster 
  
    // prints the elements 
    cout << "\nThe multimap is : \n"; 
    cout << "KEY\tELEMENT\n"; 
    for (auto itr = mp.begin(); itr != mp.end(); itr++) 
        cout << itr->first << "\t" << itr->second << endl; 
  
    return 0; 
}

Output:

The multimap is : 
KEY    ELEMENT
1    50
1    50
1    40
2    20
2    60
2    30

Important tips to remember about Map and Multimap

The multimap stores pairs of (key,value) where both key and value can appear several times
The map > will only store each value once for a specific key. To do that, it will have to be able to compare the values, not just the keys
std::map is an associative container, that allows you to have a unique key associated with your type value
A std::multimap is equal to a std::map, but your keys are not unique anymore. Therefore you can find a range of items instead of just find one unique item.
A std::multimap is equal to a std::map, but your keys are not unique anymore. Therefore you can find a range of items instead of just find one unique item.

Example - 1

Example - 2

Syntax

Implementing Multimap

Example

Output:

Basic Functions associated with multimap

1. begin() & end() :

Syntax

Exceptions :

Example

Output:

Syntax:

Exception

Example

Output:

2. cbegin() & cend() :

Syntax:

Exception

Example

Output:

Syntax:

Exception

Example

Output:

3. rbegin() :

Syntax:

Exception

Example

Output:

4. rend() :

Syntax

Example

Output:

5. crbegin() :

Syntax:

Example

Output:

6. crend() :

Syntax:

Example

Output:

7. insert() :

a. Syntax :

Example :

Output:

b. Syntax:

Example

Output:

c. Syntax:

Example

Output:

8. emplace() :

Syntax:

Example

Output:

9. emplace_hint() :

Syntax:

Example

Output:

Important tips to remember about Map and Multimap

1. `begin()` & `end()` :

2. `cbegin()` & `cend()` :

3. `rbegin()` :

4. `rend()` :

5. `crbegin()` :

6. `crend()` :

7. `insert()` :

8. `emplace()` :

9. `emplace_hint()` :