Map vs Multimap in C++ STL

Reading time: 20 minutes | Coding time: 5 minutes

In this article we are going to discuss about the difference between a map and a multimap containers in C++ STL. In short, the only difference between map and multimap in C++ is that map can only store unique key-value pairs while in multimap, no key value pair is unique.

Before diving straight into the topic, lets just understand what each of the terms mean specifically. Following it, we will explain the difference in detail with a code example.

Map

A map is a data structure that is primarily used to store key-value pairs.Each key value in a map is mapped to a value.And something to note is that no two values in a map can be mapped to a single index.
Before analysing an code on map, lets just see some functions that helps us implement a map in the best way.

functions to rescue

pair insert(keyvalue, mapvalue) – Adds a new element to the map, it is basically a function that is used to input elements to the map.
syntax:

mapname.insert(pair<int, int>(key, value));

begin() – Returns an iterator to the first element in the map.
syntax:

iter = mapname.begin();

end() – Returns an iterator to the element that follows last element in the map.
syntax:

iter= mapname.end();

there are more functions to use, we shall see them when needed.

example code for map INSERT AND DISPLAY in a multimap:

#include <iostream> 
#include<bits/stdc++.h>
#include <map> 
  
using namespace std; 
  
int main() 
{ 
 
    multimap<int, int> demo;
    demo.insert(pair<int, int>(1, 10)); 
    demo.insert(pair<int, int>(2, 20)); 
    demo.insert(pair<int, int>(3, 30)); 
    //initialising the iterator for the map
    map<int, int>::iterator iter;
    
    for (iter = demo.begin(); iter != demo.end(); ++itr)
    { 
        cout << iter->first<< " " << iter->second << '\n'; 
    } 
   
    return 0;
}

output

1  10
2  20
3  30

example code for map SEARCH operation in a map:

#include <iostream> 
#include<bits/stdc++.h>
#include <map> 
  
using namespace std; 
  
int main() 
{    int index;
 
    map<int, int> demo;
    demo.insert(pair<int, int>(1, 10)); 
    demo.insert(pair<int, int>(2, 20)); 
    demo.insert(pair<int, int>(3, 30)); 
    //initialising the iterator for the map
    map<int, int>::iterator iter;
    cin>>index;   //element to be searched
     iter = demo.find(index); 
      
    if(it == demo.end()) 
        cout << "key isn't present"; 
    else
        cout << "Key-value pair present : " << iter->first << iter->second ; 
   
    return 0;

Complexity analysis:

The time complexity for an insert and a search operation in a map takes log(n) time.

Multimap

Multimap is nothing different than a normal map except the fact that in a multimap mutiple values can have the same key.And other factors are just the same between a Map and a Multimap.

The functions that were discussed under the map section are also workable under this multimap data structure.

example code for map INSERT AND DISPLAY in a multimap:

#include <iostream> 
#include<bits/stdc++.h>
#include <map> 
  
using namespace std; 
  
int main() 
{ 
 
    multimap<int, int> demo;
    demo.insert(pair<int, int>(1, 10)); 
    demo.insert(pair<int, int>(2, 20)); 
    demo.insert(pair<int, int>(2, 30));  //same index mapped twice
    //initialising the iterator for the map
    map<int, int>::iterator iter;
    
    for (iter = demo.begin(); iter != demo.end(); ++itr)
    { 
        cout << iter->first<< " " << iter->second << '\n'; 
    } 
   
    return 0;
}

output

1  10
2  20
2  30

example code for map SEARCH operation in a map:

#include <iostream> 
#include<bits/stdc++.h>
#include <map> 
  
using namespace std; 
  
int main() 
{    int index;
 
    map<int, int> demo;
    demo.insert(pair<int, int>(1, 10)); 
    demo.insert(pair<int, int>(2, 20)); 
    demo.insert(pair<int, int>(2, 30)); 
    //initialising the iterator for the map
    map<int, int>::iterator iter;
    cin>>index;   //element to be searched
     iter = demo.find(index); 
      
    if(it == demo.end()) 
        cout << "key isn't present"; 
    else
        cout << "Key-value pair present : " << iter->first << iter->second ; 
   
    return 0;

Difference between Map and Multimap

• A multimap can store (key-value) pairs , both can appear any number of times.This certainly means that no key-value pair in a map is unique.

example:

#include <iostream> 
#include<bits/stdc++.h>
#include <map> 
  
using namespace std; 
  
int main() 
{ 
 
    multimap<int, int> demo;
    demo.insert(pair<int, int>(1, 10)); 
    demo.insert(pair<int, int>(2, 20)); 
    demo.insert(pair<int, int>(2, 30));  //same index mapped twice
    //initialising the iterator for the map
    map<int, int>::iterator iter;
    
    for (iter = demo.begin(); iter != demo.end(); ++itr)
    { 
        cout << iter->first<< " " << iter->second << '\n'; 
    } 
   
    return 0;
}

output

1  10
2  20
2  30

• On the other hand a map can only store unique key-value pairs. It is able to do this by comparing not just the existing keys but also the value pairs continuosly.

example :

#include <iostream> 
#include<bits/stdc++.h>
#include <map> 
  
using namespace std; 
  
int main() 
{ 
 
    map<int, int> demo;
    demo.insert(pair<int, int>(1, 10)); 
    demo.insert(pair<int, int>(2, 20)); 
    demo.insert(pair<int, int>(3, 30)); 
    //initialising the iterator for the map
    map<int, int>::iterator iter;
    
    for (iter = demo.begin(); iter != demo.end(); ++itr)
    { 
        cout << iter->first<< " " << iter->second << '\n'; 
    } 
   
    return 0;
}

output

1  10
2  20
3  30

• Now as we know that a multimap can have multiple common key-value pairs, we can be certain we would see range of items and not just some unique key-value pairs.

• analogous to a map we have a set, and for a multimap we have a multiset.

• On account of the time complexity, both map and multimap have log(n) time .

• Now if we use the count() function on a map, we can either get 0 or 1. But in the case of a multimap, we can get any non negative value.A count function counts the key values that matches the arguments.

example:

for multimap:

demo.count(2)=2

for map:

demo.count(2)=1

Primarily the major difference is that in a map a key can be mapped with a single value, but in a multimap multiple keys can be mapped to different values.

What to choose and when to choose?

Now if you are looking for a simple look up table, consisting of unique key-value pairs, then map is a all stop destination for you.If at all reccuring key values come into picture, they get rewritten on their previous matching key-values.Maps are generally implemented using a red-black tree.

On the other hand if you are interested in grouping the objects or values together by keys then a Multimap is very suitable in this case. Just think of a case where there are synonyms of a single word, now if we consider that word as a key, we would have different values for that same key.So in this case a map wouldn't do. A multimap on the other hand can serve the purpose very well.
Cases where we are interested in stuffs like:

• Words serving as the key.(synonyms can be handeled because multimap is felxible)

• Tables like pincodes and their residents,where pincodes can act like keys and resident addressses as the values.Same pin coded areas have multiple residents.So this also calls for a multimap.

With this, you may complete knowledge of Map vs Multimap containers in C++ STL.

Hope you liked it. Happy coding.