Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Map in C++
3.
Creating a Map in C++
4.
Member Functions of Map
5.
Iterator in Maps
6.
FAQs
7.
Key Takeaways
Last Updated: Mar 27, 2024

Map in C++

Author Tanay Kumar
2 upvotes
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

The C++ STL (Standard Template Library) supports several Data Structures that play a crucial role in solving any problem. One such data container is the "Map in C++". A map in C++ is an associative container that stores elements in a mapped fashion. Every element has one key value and one mapped value. Any two elements can not have the same key.

To learn more about C++ STL, visit the C++ guided path.

This article will help you understand the map in c++ and the basic functions associated with it.

Map in C++

A map in C++ is an associative container that stores elements in a mapped fashion. Maps contain sorted key-value pairs, in which every key is unique and cannot be modified. We can insert and delete a key but cannot alter it. The value associated with keys can be modified or updated. We can insert, remove, and search a map within O(n) time complexity.

Internally, the map elements are always sorted by their key values following a specific ordering criterion indicated by its internal comparison object (of type Compare). Keys are always sorted in ascending order.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Creating a Map in C++

We can easily create a map with the following syntax:

map<key_type , value_type> map_name;

 

The above code will create a map with a key of the "Key_type" data type and the "value_type" datatype value. Remember that the key of a map and corresponding values are always inserted as a pair. We cannot insert only a key or value in the map.

Now, let’s see an example of creating and initializing maps in different ways:

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


int main ()
{
    // Create a map with keys 1, 2, 3 and corresponding values 4,5,6 
    map<int,int> map1{ {1,4} , {2,5} , {3,6} };
    
    // Creates a map with keys of string  type and values of integer type
    map<string,int> map2;
    
    map2["abc"]=101;    // inserts key = "abc" with value = 101
    map2["b"]=201;      // inserts key = "b" with value = 201
    map2["c"]=301;      // inserts key = "c" with value = 301
    map2["def"]=401;    // inserts key = "def" with value = 401
    
    // Create a map which have entries copied from map2.begin() to map2.end()
    map<char,int> map3 (map2.begin(), map2.end());
    
    // create map which is a copy of map1
    map<char,int> map4 (map1);
}

 

In the above example, we have created and initialized different maps using different methods.

Member Functions of Map

For a map, many functions or methods are defined, among which the most used ones are the begin, end, empty and size for capacity, find for searching a key, erase and insert for modification.

We have seen an example of functions associated with the map in C++. Now let's learn about them briefly with the help of the table below:

Function

Description

insert() We use it to insert a new element in the map.
begin() It returns the iterator to the first element in the map container.
end() It returns an iterator to the end of the map.
clear() It removes all the elements from any map and empties it.
erase() It removes either a single element or a range of elements from the start(inclusive) to end(exclusive).
size() It returns the total number of elements in a map container.
empty() It checks if the map is empty or not.
upper_bound() It returns the iterator to the first element equivalent or greater than the mapped value.
lower_bound() It returns the iterator to the first element equivalent or just smaller to the mapped value.

 

Let's consider an example of declaration, insert, find and iteration in a map.

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


int main ()
{
    // Creates a map1 with keys 1,2,3 and corresponding values 4,5,6
    map<int,int> map1{ {1,4} , {2,5} , {3,6} };
        
    // Using at() and [ ] method
    m.at(1) = 40;    // Updates the value associated with key 1 to 40
    m[2] = 50;         // Updates the value associated with key 2 to 50


    // Using insert() method
    m.insert(pair<int,int> (4,7));    // Inserts new entry of key = 4 and value = 7
    m.insert(make_pair(5, 8));      // Inserts new entry of key = 5 and value = 8


    // Iterating over the map
    cout<<"The Map is: \n";
    map<int, int>::iterator i;
    for(i = map1.begin(); i != map1.end(); i++){
        cout << i->first << '\t' << i->second<< '\n';
    }
}

 

The output for the above code is displayed below:

Output

Iterator in Maps

An object (like a pointer) pointing to an element inside the map container is an iterator to a map. We can use these iterators to move through the elements of the container.

Syntex:

// Initializing an iterator
map<key_type , value_type>::iterator itr;

 

Example:

Let’s consider an example for iterating over the complete map in c++.

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
     // Creates a map map1 with keys 1,2,3 and corresponding values 4,5,6
    map<int,int> map1{ {1,4} , {2,5} , {3,6} };


    // Iterating over the map
    map<int, int>::iterator i;
    for(i = map1.begin(); i != map1.end(); i++){
        cout << i->first << '\t' << i->second<< '\n';
    }
}

 

The output of the above code after iterating through the whole set is displayed below:

Output

Also check out this article - Pair in C++

Must Read Swap Two Numbers Without Using Third Variable

FAQs

  1. What are the differences between a map and an unordered_map in C++?
    A map is an ordered sequence of unique key values, whereas in an unordered_map key values can be stored in any order, so it is unordered. The average time complexity for a map operation is O(log(n)), while for an unordered_map, it is O(1).
     
  2. How is a map in C++ internally implemented?
    std::map is implementable using binary search trees (balanced).
     
  3. What are data types supported for the key of a map in C++?
    A map can contain a key of any type – user-defined or pre-defined data structure. Still, when we define a key of a user-defined type, we need to specify our custom comparison function according to compare the keys.
     
  4. What is the worst and average time complexity of a map in c++?
    The average time complexity and the worst-case complexity are O(log n) for a map.

Key Takeaways

In this article, we have extensively discussed the map in c++. We learned how to initialize a map in c++ and the different functions and methods associated with it.

We hope that this blog has helped you enhance your knowledge regarding Map in C++, and if you would like to learn more, check out our articles on STL containers in C++, Data Types in C++, and Implementing Sets Without C++ STL Containers. Do upvote our blog to help other ninjas grow. Happy Coding!

Previous article
Set in C++ Standard Template Library
Next article
Multimap in C++
Live masterclass