Search for Courses, Topics

Map in C++

Learn about Map in C++

20 Aug 2021-11 mins read
quiz
Challenge Inside! : Find out where you stand! Try quiz, solve problems & win rewards!

Overview

Maps in C++ are associative containers present in C++ standard template library(STL) that are used to store data in a form of key-value pair. Each element of a map has a key value and a mapped value. Also, maps store the key values in ascending order by default in C++.

Scope

  • This article covers the concept of maps and how they are implemented internally in C++
  • It also covers the concept of unordered map and multimap in C++

Introduction

Standard Template Library (STL) was introduced in C++ 11, which made many things simpler by providing many inbuilt class templates,( that is why it is known as template library!!), also known as associative containers.

With the help of these templates, users can just use simple syntaxes to declare and use data structures like heap and algorithms like binary search which requires long codes if implemented manually.

Now there is no need to write long code for the implementation of these templates. STL did that for us!!

Map in C++ is also one of these associative containers. It is based on a hashing technique in which the elements are stored as a key-value pair. The key is always unique, that is we cannot insert the same key more than once.

Let us understand this with the help of an example. Suppose there are 10000 students in your college whose roll number ranges from 1 to 10000 and you only want to store the marks of top 10 students. Then how will you do this?? One obvious answer could be using arrays. Then you will have to make an array of size 10000 as you do not roll numbers of toppers. But you will use only 10 blocks of array rest will be wasted. Now is it an optimal way to solve the problem?? Obviously not!!. So what can you do??

Well in these situations we can easily use maps. Here we can store a pair of roll numbers and marks in the map in C++. The roll number will act as a key and marks will be the value corresponding to that key.

The key in a map is always unique, you can not have multiple instances of the same key.

Below is the representation of a map in C++ which stores roll number as a key and name of student as a value.

key value pair in a cpp map

The key-value pair in a map is always stored in sorted order, by default, it is in ascending order but you can define your own order using the comparator function.

How are maps in C++ implemented internally?

Map in C++ is implemented with the help of self-balancing binary search tree mostly using Red Black trees. Red Black Tree is a self-balancing binary search tree, in which the value at the root node is always greater than or equal to the left child and always less than or equal to the value of the right child. It also ensures that the difference between heights of the left subtree and right subtree is at most one. (To know about the Red Black Tree please refer to the Red Black Tree article on Scaler).

Therefore the time complexity of various operations on the map in C++ is the same as that of Red Black trees. Inserting a key-value pair takes O(log(n)) time, traversing a whole map in C++ takes O(nlog(n)) time.

Therefore the time complexity of various operations on the map in C++ is the same as that of Red Black trees. Inserting a key-value pair takes O(log(n)) time, traversing a whole map in C++ takes O(nlog(n)) time.

The representation of above mentioned map using Red Black Tree will look somewhat like this:

maps in cpp implemented internally

Syntax

The general syntax of maps in C++ are:

map<data type of key, data type of value> map_name;

Let us understand this with code:

#include <bits/stdc++.h>
using namespace std;

int main() {

  // empty map in container
  map<int, int> m1; // with key value both as integer
  map<int, string> m2; // with key as integer and value as string
  map<int, vector<int>> m3; // with key as integer and value as vector
  map<string, string> m4; // with key and value as string

  return 0;
}

Parameters in a Map

Parameters refer to the set of values required to initialize any particular template. As the templates or a method associated with it are types of functions and for any function, we need to give the required number of parameters that are used in the function definition. Similarly, in the case of maps in C++, two parameters that are required are key and a value.

Thus, parameters required for a map in C++ are a key and a value.

Creating a Map

Now let’s see how the maps in C++ are created, how values are inserted in a map in C++, and how we traverse a map in C++, with the help of code.

But before that, we need to look at some functions defined for the map in C++ which help us in doing various operations on a map in C++ such as insert, delete, etc.

Basic Functions in a Map

In order to use the function on a map in C++ or even on any data structure you need to know about an iterator. An iterator is used to point at the memory locations of an STL container. There are many predefined iterators present in STL containers like begin, end, rbegin, rend, cbegin, cend, etc. But the two iterators which are mostly used are: begin and end. Apart from that, you can also create your own iterators pointing to any valid location in your container.

basic functions in a map cpp

1. begin() – Returns an iterator to the first key-value pair in the map in C++. Now since begin is predefined in STL, it is a constant operation that is it’s time complexity is O(1).

2. end()–Returns an iterator to the hypothetical address after the last key-value pair in the map in C++. Its time complexity is O(1).

3. size() – Returns the number of elements in the map. Internally this is calculated by simply maintaining the iterator to the current position in map and then subtracting that from the iterator to the begin. It is of O(1) time complexity.

4. max_size() – Returns the maximum possible size of the maps in C++. It depends upon the compiler and machine. It is of O(1) time complexity.

5. empty() – Returns whether the map in C++ is empty or not. True if the map in C++ is empty and false if it is not. It is of O(1) time complexity.

6. insert(pair) – Adds a new key-value pair to the map in C++. Since the map in C++ is internally represented using Red Black Trees, the time complexity is also the same as that of insertion in Red Black Trees, that is O(log(n)).

7. erase( iterator ) – Removes the key-value pair which is present at the position pointed by the iterator. It is of O(1) time complexity.

Now there few more variations of erase function depending upon the parameters provided by the user:

  • erase(key) – Removes the key-value pair corresponding to the given key. It has logarithmic time complexity that is O(log(n)).
  • erase ( first_it, last_it ) – It is used to remove a key-value pair from the range starting with first_it till last_it. The time complexity depends linearly upon the value of range covered, that is O(last_it – first_it). It will be O(n), in case you want to erase the whole map in C++.

8. clear() – Removes all the key-value pairs from the maps in C++. Its time complexity is O(n) because of the reason mentioned above.

Now we know all the functions required to define, initialize and use a map in C++.

Let us code it!!

#include <bits/stdc++.h>
using namespace std;

int main() {
  map<int, int> marks;
  map<int, string> student;
  // insert elements in random order
  marks.insert({
    1,
    20
  });
  marks.insert({
    2,
    67
  });
  student.insert({
    1,
    "Elon Musk"
  });
  student.insert({
    2,
    "Bill Gates"
  });
    
  // printing marks
  map<int, int>::iterator itr;
  cout << "\nThe map marks is : \n";
  cout << "\tKEY\tVALUE\n";
  for (itr = marks.begin(); itr != marks.end(); ++itr) {
    cout << '\t' << itr -> first <<
      '\t' << itr -> second << '\n';
  }
  cout << endl;
  map<int, string>::iterator itr1;
  cout << "\nThe map student is : \n";
  cout << "\tKEY\tVALUE\n";
  for (itr1 = student.begin(); itr1 != student.end(); ++itr1) {
    cout << '\t' << itr1 -> first <<
      '\t' << itr1 -> second << '\n';
  }
  marks.clear(); // deletes all the elements from a maps in C++
  student.clear(); // deletes all the elements from a maps in C++
  return 0;
}

Output:

The map marks is :

KEY        VALUE
1           20
2           67

The map student is :

KEY        VALUE
1         Elon Mask
2         Bill Gates  

Other than normal maps in C++ there are two more variants of a map that are widely used in programming. These are:

  1. Unordered_map in C++
  2. Multimap in C++

Unordered_map in C++

Unordered_map in C++ is exactly the same as that of a map in C++, with the only difference that in unordered_map in C++ there is no order in which key-value pairs are stored whereas, in normal maps in C++, it is always stored in sorted order. Let's understand with the help of a code:

#include <bits/stdc++.h>
using namespace std;

int main() {
  map<int, int> marks;
  // insert elements in random order
  marks.insert(pair<int, int>(2, 80));
  marks.insert(pair<int, int>(4, 67));
  marks.insert(pair<int, int>(3, 35));
  marks.insert(pair<int, int>(1, 20));
  // printing marks
  map<int, int>::iterator itr;
  cout << "\nThe map marks is : \n";
  cout << "\tKEY\tVALUE\n";
  for (itr = marks.begin(); itr != marks.end(); ++itr) {
    cout << '\t' << itr -> first <<
      '\t' << itr -> second << '\n';
  }
  cout << endl;
  unordered_map<int, int> marks1;
  // insert elements in random order
  marks1.insert(pair<int, int>(2, 80));
  marks1.insert(pair<int, int>(4, 67));
  marks1.insert(pair<int, int>(3, 35));
  marks1.insert(pair<int, int>(1, 20));

  unordered_map<int, int>::iterator itr1;
  cout << "\nThe map unordered_marks is : \n";
  cout << "\tKEY\tVALUE\n";
  for (itr1 = marks1.begin(); itr1 != marks1.end(); ++itr1) {
    cout << '\t' << itr1 -> first <<
      '\t' << itr1 -> second << '\n';
  }

  return 0;
}

Output:

The map marks is :

KEY      VALUE
1          20
2          80
3          35
4          67

The map unordered_marks is :

KEY      VALUE
1         20
2         35
3         67
4         80

When do we use unordered_maps in C++? In the situations where we only need to store the key-value pair and there is no need of maintaining any specific order, then we use unordered_maps in C++.

Unordered maps are widely used because of their time complexity. The time complexity of the search, insert and delete operations in unordered_maps in C++ is O(1) in an average case while that of an ordered map or simple map in C++ is O(log(n)) in an average case. Therefore you should use unordered_map in C++ whenever possible.

Multimap in C++

Multimap in C++ is also the same as a map in C++, with the only difference being that, we can store more than one occurrence of the same key, that is, the key is not unique here. We can have multiple values corresponding to the same key. Whereas in a normal map in C++, it is just not possible. Every key is unique there.

Let's understand this with code:

#include <bits/stdc++.h>
using namespace std;

int main()
{
  map<int, int> marks;
  // insert elements in random order
  marks.insert(pair<int, int>(1, 80));
  marks.insert(pair<int, int>(2, 67));
  marks.insert(pair<int, int>(1, 80));
  marks.insert(pair<int, int>(2, 67));
  
  // printing marks
  map<int, int>::iterator itr;
  cout << "\nThe map marks is : \n";
  cout << "\tKEY\tVALUE\n";
  for (itr = marks.begin(); itr != marks.end(); ++itr) {
     cout << '\t' << itr->first
          << '\t' << itr->second << '\n';
  }
  cout << endl;
  multimap<int, int> marks1;
   // insert elements in random order
  marks1.insert(pair<int, int>(1, 80));
  marks1.insert(pair<int, int>(2, 67));
  marks1.insert(pair<int, int>(1, 35));
  marks1.insert(pair<int, int>(2, 20));
  // printing marks
  multimap<int, int>::iterator itr1;
  cout << "The multimap marks is : \n";
  cout << "\tKEY\tVALUE\n";
  for (itr1 = marks1.begin(); itr1 != marks1.end(); ++itr1) {
     cout << '\t' << itr1->first
          << '\t' << itr1->second << '\n';
  }

return 0;
}

Output:

The map marks is : 

KEY      VALUE 
1         80 
2         67 

The multimap marks is : 

KEY     VALUE
1        80 
1        35
2        67
2        20

When to use a multimap in C++? Suppose you have a list of students and you want to store the phone numbers of each of them. Now it may be possible that one student has more than one phone number, in that case a multimap in C++ will be used. Or the DNS server can map several URLs to the same IP address, in that case also multimaps in C++ will be used.

Conclusion

So far we have seen that maps in C++ are used to store a key-value pair. We can use any type of data type for keys and values. The elements can be stored in ordered form or in unordered form using unordered_map in C++. We can also have multiple occurrences of the same key using multimap in C++. Thus the map in C++ provides a wide range of operations and applications in programming, such as hashing, storing key and value pairs while maintaining the order, etc.

That’s all for now folks!

Thanks for reading.

Challenge Time!

quiz Time to test your skills and win rewards! Note: Rewards will be credited after the next product update.