Hi everyone

In this tutorial we will talk about Map

So, What is Map actually?

Map is an associative container of C++ STL that stores data in key–value pairs. Each key inside a map is unique, and the elements are always kept sorted by key automatically.

Unlike vector or list, where we access elements by index, in map we access values using their keys — just like a real-life dictionary where we look up a word to find its meaning.

Map’s underlying data structure is a Self-Balancing Binary Search Tree (usually a Red-Black Tree). That is why all its major operations — insertion, deletion, search — take O(log n) time, and that is also why the elements stay sorted by key automatically.

Header File Inclusion for map

#include <map>

Declaration & Initialization

Declaring an empty map —

map <int, string> studentMap;

Here, key type is int and value type is string. The map is empty right now.

Declaring a map with values —

From C++11 onwards, we can initialize a map with values using curly braces —

map <int, string> studentMap = {
    { 101, "Imran" },
    { 102, "Linkon" },
    { 103, "Sakib" }
};

After Initialization studentMap will look like this —

 

key	value
101	Imran
102	Linkon
103	Sakib

 

Declaring a map with different data types —

Key and value can be of any type, even different from each other —

map <string, int> ageMap;
map <char, vector<int> > charListMap;
map <string, pair<int, int> > rangeMap;

Declaring a map in descending order of keys —

By default, map stores keys in ascending order. If we want keys in descending order, we can pass greater<> as the third template parameter —

map <int, string, greater<int> > reverseMap;

Insertion

Insertion using [ ] subscript operator

The easiest way to insert a key–value pair is by using the [ ] operator —

map <int, string> studentMap;

studentMap[101] = "Imran";
studentMap[102] = "Linkon";
studentMap[103] = "Sakib";

After Insertion studentMap will look like this —

 

key	value
101	Imran
102	Linkon
103	Sakib

 

Insertion using insert() method with pair

We can also insert values using the insert() method with a pair —

studentMap.insert(pair<int, string>(104, "Rafi"));

Insertion using insert() method with make_pair

Same thing can be done with make_pair() for cleaner code —

studentMap.insert(make_pair(105, "Tanvir"));

Insertion using insert() method with curly braces

From C++11 onwards, we can insert using curly braces directly —

studentMap.insert({ 106, "Shuvo" });

After all these insertions, studentMap will look like this —

 

key	value
101	Imran
102	Linkon
103	Sakib
104	Rafi
105	Tanvir
106	Shuvo

 

Insertion using emplace() method

emplace() constructs the pair in place, so it avoids an extra copy —

studentMap.emplace(107, "Hasan");

💡 Quick tip on duplicate keys — Since map keys are unique, if we try to insert a key that already exists using insert() or emplace(), the insertion will be ignored (old value stays). But if we use the [ ] operator, the old value will be overwritten. Choose carefully based on what we want.

Insertion using insert_or_assign() method (C++17)

If we want the behavior of “insert if new, update if exists” explicitly, we can use insert_or_assign() —

studentMap.insert_or_assign(101, "Imran Hossain");

Now the value of key 101 will be updated to “Imran Hossain”.

Accessing the element

[ ] subscript operator

We can access the value of a given key using the [ ] operator —

cout << studentMap[102] << endl;

Output will be – Linkon

💡 Quick tip on [ ] operator — If the key does not exist, the [ ] operator will create a new entry with that key and a default value (empty string, 0, etc.). This can silently add unwanted entries to our map. If we just want to read, prefer at() or find() instead.

at() method

at() method also returns the value of a given key. But unlike [ ], it does not create a new entry if the key is missing — it throws an out_of_range exception instead —

cout << studentMap.at(103) << endl;

Output will be – Sakib

find() method

find() returns an iterator to the element if the key exists, otherwise it returns end() —

auto it = studentMap.find(104);

if (it != studentMap.end())
{
    cout << it->first << " " << it->second << endl;
}
else
{
    cout << "Key not found" << endl;
}

Output will be – 104 Rafi

Checking if a key exists

count() method

Since keys are unique, count() returns either 0 (not present) or 1 (present) —

if (studentMap.count(105))
{
    cout << "Key exists" << endl;
}
else 
{
    // Do as the action required
}

contains() method (C++20)

From C++20 onwards, we have a cleaner way —

if (studentMap.contains(105))
{
    cout << "Key exists" << endl;
}

Iterating through a map

Range-based for loop

The cleanest way to iterate through a map is using a range-based for loop —

for (auto &element : studentMap)
{
    cout << element.first << " - " << element.second << endl;
}

Output will be —

101 - Imran
102 - Linkon
103 - Sakib
104 - Rafi
105 - Tanvir
106 - Shuvo
107 - Hasan

Using iterator

We can also iterate using iterators directly —

map <int, string>::iterator it;

for (it = studentMap.begin(); it != studentMap.end(); it++)
{
    cout << it->first << " - " << it->second << endl;
}

💡 Note on iteration order — No matter the order in which we inserted the keys, map always iterates them in sorted order of keys (ascending by default). That is one of the most powerful features of map.

Deletion

Deletion using erase() with key

We can delete a specific key–value pair by passing the key directly to erase() —

studentMap.erase(102);

After deletion studentMap will look like this —

 

key	value
101	Imran
103	Sakib
104	Rafi
105	Tanvir
106	Shuvo
107	Hasan

 

Deletion using erase() with iterator

We can also delete using an iterator —

auto it = studentMap.find(104);

if (it != studentMap.end())
{
    studentMap.erase(it);
}

After deletion studentMap will look like this —

 

key	value
101	Imran
103	Sakib
105	Tanvir
106	Shuvo
107	Hasan

 

Deletion using erase() with range

We can delete a range of elements by passing the start and end iterators —

studentMap.erase(studentMap.find(105), studentMap.end());

After deletion studentMap will look like this —

 

key	value
101	Imran
103	Sakib

 

clear() method

If we want to remove all elements of the map, we can use clear() —

studentMap.clear();

After clear(), studentMap will be empty.

Size and Empty

cout << studentMap.size() << endl;

if (studentMap.empty())
{
    cout << "Map is empty" << endl;
}

size() returns the number of elements, and empty() returns true if the map has no elements.

Swapping

swap() method

STL map has a method named swap(), which swaps all the key–value pairs between two maps —

map <int, string> mapOne = {
    { 1, "One" },
    { 2, "Two" }
};

map <int, string> mapTwo = {
    { 10, "Ten" },
    { 20, "Twenty" },
    { 30, "Thirty" }
};

mapOne will look like this —

 

key	value
1	One
2	Two

 

mapTwo will look like this —

 

key	value
10	Ten
20	Twenty
30	Thirty

 

Now, let’s swap the values of two maps —

// swapping values between two maps
mapOne.swap(mapTwo);

After Swapping mapOne will look like this —

 

key	value
10	Ten
20	Twenty
30	Thirty

 

After Swapping mapTwo will look like this —

 

key	value
1	One
2	Two

 

Map with pair as key

Sometimes a single value is not enough to identify an entry — we need two values together as a key. For example, to store the weight of an edge between two nodes, we can use a pair as the key —

map < pair<int, int>, int > edgeWeight;

edgeWeight[{1, 2}] = 50;
edgeWeight[{1, 3}] = 20;
edgeWeight[{2, 3}] = 70;

After Insertion edgeWeight will look like this —

 

key.first	key.second	value
1	2	50
1	3	20
2	3	70

 

Accessing values —

cout << edgeWeight[{1, 3}] << endl;

Output will be – 20

This pattern is very handy in graph problems.

lower_bound() and upper_bound()

Since map keys are stored in sorted order, we can use lower_bound() and upper_bound() just like we do for sorted vectors.

lower_bound(key) — returns an iterator to the first element whose key is not less than the given key.

upper_bound(key) — returns an iterator to the first element whose key is strictly greater than the given key.

map <int, string> studentMap = {
    { 101, "Imran" },
    { 103, "Sakib" },
    { 105, "Tanvir" },
    { 107, "Hasan" }
};

auto lb = studentMap.lower_bound(103);
auto ub = studentMap.upper_bound(103);

cout << lb->first << " " << lb->second << endl;
cout << ub->first << " " << ub->second << endl;

Output will be —

103 Sakib
105 Tanvir

Map vs unordered_map

This is a common confusion, so it is worth a quick note —

 

Property	map	unordered_map
Underlying data structure	Red-Black Tree	Hash Table
Order of keys	Sorted	No specific order
Insertion / Deletion / Search	O(log n)	O(1) average, O(n) worst
Use when	We need sorted keys or ordered traversal	We just need fast lookup, order does not matter

 

Time Complexity

 

Operation	Description	Time Complexity
operator[ ]	Access or insert a value by key	O(log n)
at()	Access value by key (throws if missing)	O(log n)
insert()	Insert a key–value pair	O(log n)
emplace()	Construct and insert a key–value pair in place	O(log n)
insert_or_assign()	Insert new or update existing value	O(log n)
erase()	Remove an element by key or iterator	O(log n)
find()	Find an element by key	O(log n)
count()	Check if a key exists (returns 0 or 1)	O(log n)
contains()	Check if a key exists (C++20)	O(log n)
lower_bound()	Iterator to first key not less than given key	O(log n)
upper_bound()	Iterator to first key greater than given key	O(log n)
size()	Returns the number of elements	O(1)
empty()	Returns true if map is empty	O(1)
clear()	Removes all elements	O(n)
swap()	Swaps contents of two maps	O(1)
begin() / end()	Iterators to the beginning and end	O(1)

 

Applications

• • • • Frequency counting of words, characters, or numbers
      • Dictionary and phone book implementations
      • Storing weighted edges in a graph (using pair as key)
      • Inverted index in search engines
      • Counting distinct elements while keeping them sorted
      • Associating IDs with objects (student ID → student info, product ID → product info)
      • Range queries with lower_bound() and upper_bound()

In the next tutorial we will talk about another useful STL container.

Until then
Happy Coding