Map in C++

Learn via video course
FREE
View all courses
C++ Course: Learn the Essentials
C++ Course: Learn the Essentials
by Prateek Narang
1000
5
Start Learning
C++ Course: Learn the Essentials
C++ Course: Learn the Essentials
by Prateek Narang
1000
5
Start Learning

Overview

Maps in C++ are container structures that store elements in key-value pairs. This means that for every unique key, there is a data value mapped to it, that can be easily accessed if we know the key.

This is why every key has to be unique, and no two keys can be the same(but the values associated to keys can be the same).

Maps in C++ store the key-value pairs in sorted order by default so that the search for any key-value pair can be very quick.

What is Map in C++?

Have you ever wondered how the mechanism of storing books in a library works?

Usually, library management systems make use of something similar to maps to search efficiently where a book must be kept. Each book is assigned a shelf number, which is stored in the computer system, for easy and fast lookup.

This is very similar to how maps work. Maps are container structures that store key-value pairs. This means that each key is unique and points to a specific value. Just like each book is unique and points to a specific shelf in the library.

Libary Map Example

Not only this but maps can also be used in storing the memory addresses of variables in our code, in fact, it stores the elements in order with respect to the keys, Whenever we need to access a variable's value, we just need to look up its address on the map.

Also, the map in C++ is based on red-black trees which in general are self balanced binary trees.

Let us take a look at the syntax of a map in c++

Syntax

To declare a map in C++, we use the following syntax:

Here,

  • The key_dataType is the data type of the key.
  • The value_dataType is the data type of the value.
  • mapName is the name of the map.

Note: To declare the map in C++, you need to add a header file containing the template and the functions of the map.

Header for Map in C++

In the C++ Language, the required header for the map data structure is:

Let us now try creating a map to see how we can use it in our codes.

Creating a Map

A map in C++ can be easily created using the header file and the syntax that we discussed above, let us take a look at an example to see how it can be created.

We can create a map to store the roll numbers corresponding to the names of every student in the class.

Output

Example Question Map

In the above example, we did not have to go through the whole array to find the student with the name "Antarctica" or "Europe", we just required the key which in this case was the name of the student and the value associated to that key was retrieved quickly, to be accurate the time complexity of the worst case if we had to iterate through the whole array would have been O(NL){ O(N*L) } whereas in this case, that is by using the map we have improved it to O(log(N)L){ O(log(N)*L) }, where NN is the number of elements in the array and L{ L } is the average length of the array.

Member Functions

So far we've learned about how the map works, let us now see how we can make use of the in-built functions of the map in C++ to create our key-value pairs.

For this, we have many predefined member functions, that perform different map operations. We shall look into them one by one and try to understand how they work through examples.

Element Access

Function NameDescriptionSyntaxTime ComplexityReason
operator []Operator [] is used to retrieve the element / value associated with the given keymap_name[key_name]O( log(N) )Adding a new element in a self balanced bianry tree takes logarthimic time (O(log(N)))
atat is used to retrieve the element/value associated with the given keymap_name.at(key_name)O( log(N) )Adding a new element in a self balanced binary tree takes logarthimic time (O(log(N)))

Both the functions are operator [] and at are used to access/retrieve the element/value associated with the key.

The major difference between the two is that at-will throw an exception if the key-value pair is not present in the map whereas the operator [] will insert a key-value pair if the key is not present in the map.

Example: To understand this better.

Output

In the above code, we create a map with the keys as integers and values as strings and assign the pairs in the map.

Then we print and change the values associated with the given key using the at and operator []. The last lines of the code are commented out since uncommenting them will result in an error showcasing the fact that it cannot be used on a key that is not present on the map.

Capacity

Function NameDescriptionSyntaxTime ComplexityReturn TypeReason
emptyIt is used to check if the map is empty or not. It returns true if the map is empty and otherwise Falsemap_name.empty()O(1)BooleanNeed to check the value of the variable which stores the size of the map
sizeIt is used to find the number of elements ( key value pairs ) present in the mapmap_name.size()O(1)Unsigned IntegerNeed to check the value of the variable which stores the size of the map
max_sizeIt is used to find the maximum size of the map that can be possiblemap_name.max_size()O(1)Unsigned IntegerNeed to check the value of the variable which stores the max size of the map

These functions are used to find the solution to the queries related to the size of the map in general. The empty() function returns a boolean value, TrueTrue if the map is empty that is it does not contain any key-value pair in it, otherwise it returns FalseFalse.

The size() function is used to return the number of key-value pairs in the map that is the number of entries in the map, whereas, the max_size() returns the upper bound of the entries that can contain based on the memory that the map has been allocated.

Let us take a look at an example to understand these functions.

Output

In the above code, we create a map with the keys as integers and values also as integers and then check if the map is empty or not ( the map is empty initially) and print the size of the map ( using the size() ) as well which is 0. We then assign the key-value pairs in the map, due to which the size of the map changes.

Then we again check if the map is empty (the map is now not empty) and print the size as well as the maximum size (using the max_size()) that the map can hold up to.

Modifiers

Following functions are known as modifiers in c++.

Function NameDescriptionSyntaxTime ComplexityReason
insertIt is used to insert an element in the mapmap_name.insert({ key, value })O(log(n))Adding a new element in a self balanced binary tree takes logarthimic time (O(log(N)))
eraseIt is used to erase an element in the map using the given keymap_name.erase( key )O(log(n))Removing an element in a self balanced binary tree takes logarthimic time (O(log(N)))
clearIt is used to delete all the elments of the mapmap_name.clear()O(n)Removing all the elements from a self balanced binary tree takes linear time (O(N))

Iterators

Iterators are provided by the C++ STL to make traversing the STL containers more efficient. The memory address of the elements contained in the container is returned by these iterators. The iterators may be used to conduct a variety of pre-defined tasks in STL. This also reduces the time complexity of the program.

Following functions are used to return iterators pointing to the first or the last element ( key value pair ) of the map:

Function NameDescriptionSyntaxTime Complexity
beginIt returns an iterator pointing to the first element of the map.map_name.begin()O(1)
endIt returns an iterator pointing to the last element of the map.map_name.end()O(1)
rbeginIt returns a reverse iterator pointing to the last element of the map.map_name.rbegin()O(1)
rendIt returns a reverse iterator pointing to the first element of the map.map_name.rend()O(1)
cbeginIt returns a constant iterator pointing to the first element of the map.map_name.cbegin()O(1)
cendIt returns a constant iterator pointing to the last element of the map.map_name.cend()O(1)
crbeginIt returns a reverse constant iterator pointing to the last element of the map.map_name.crbegin()O(1)
crendIt returns a reverse constant iterator pointing to the first element of the map.map_name.crend()O(1)

Note: All of the above function return iterators, that is, pointers pointing to an element of the cointainer map.

Searching and Counting

Function NameDescriptionSyntaxTime ComplexityReturn TypeReason
findIt searches for a given key-value pair using the key. It returns the iterator pointing to that element if the element is present otherwise returns an iterator equal to the end iterator of the map.map_name.find(key)O( log n )IteratorIt works on the principle of balanced binary search tree that os in worst case it will take time equivalent ot height of the tree that is O( log(n) )
countIt returns the number of key-value pairs matching the given key.map_name.count(key k)O( log n )IntegerIt works on the principle of balanced binary search tree that os in worst case it will take time equivalent ot height of the tree that is O( log(n) )
lower_boundIt returns an iterator pointing to the lower bound of the key that is passed to it.map_name.lower_bound(key)O( log n )IteratorIt works on the principle of balanced binary search tree that os in worst case it will take time equivalent ot height of the tree that is O( log(n) )
upper_boundIt returns an iterator pointing to the upper bound of the key that is passed to it.map_name.upper_bound(key)O( log n )IteratorIt works on the principle of balanced binary search tree that is the worst case it will take time equivalent of the height of the tree that is O( log(n)
equal_rangeIt returns the range of key-value pairs matching with a given key passed to it, in other words, returns a pair of iterators pointing to the lower bound and upper bound of the given key.map_name.equal_range(key)O( log n )Pair of IteratorIt finds the lower bound and upper bound and then combines both the answers that is it takes O( log(n) )

The above functions are used for searching and counting a given key. The find() function is used to find and return the iterator pointing to the address of the key-value pair matching the given key. Similarly, the count function returns the number of occurrences of the key-value pair matching the given key. The lower_bound() is a concept from binary search which return the iterator pointing to the first occurrence of a key-value pair matching the given key, similar to lower_bound(), the upper_bound() returns the iterator pointing to the key-value pair just after the matching value of the given key. The last function that is equal_range() returns a pair of iterators containing the iterators of the lower bound and upper bound of the given key.

Why Use std::map?

There are many reasons to use a map, some of them are:

  • The map in C++ stores only unique keys in sorted order based on the default or chosen sorting criteria.
  • The map in C++ is fast, easy to use, and able to search for elements using a key.
  • Only one element is attached to each key in the map.
  • The map in C++ is implementable using the balanced binary trees.

There are many more reasons to use the Map data structure in C++ but let us also look at some reasons to not use the Map in C++.

When Not to Use a Map in C++?

A map in C++ is a very useful data structure, especially when it comes to fast lookups based on a key, a map can provide the data element associated with a particular key very quickly.

But, if in your code you want to iterate over all elements, or perform some operation that requires traversing over all pairs, a map may not be the best choice.

We cannot access elements in a map like we can access them in a vector or an array using indexes, instead, we have to start with the begin iterator and keep incrementing it until we reach the end of the map. This process can be cumbersome, especially if you have a map of a large size. If in your code you find that you have to iterate through the map to search for a particular element, the map may not be the best data structure for that particular code.

Use a map in C++ when you want fast lookups based on a key value.

Let's take a look at an example to understand this better

Output

In the above code one might think that the time complexity is O(log(N)){ O(log(N)) } where N{ N } is the numeber of elements present in the map but that would be incorrect the actual time complexity of the above code is O(log(N)L){ O(log(N) * L) } where L{ L } is the average length of all the string as keys and N{ N } is the number of elements

Does Order Matter in Maps in C++?

A map in C++ keeps the key-value pairs in sorted order, to be precise, in increasing order of the key values. This means that the order in which you insert the elements in a map does not matter, as the map internally stores all elements in sorted order. This is done to provide a quick lookup operation for any key value.

If you don't want the elements to be ordered in a sorted manner, or if your code doesn't require ordering the elements sorted according to the key values, you can consider using an unordered map in C++.

An unordered map in C++, as suggested by the name, is similar to a map except that it doesn't order the pairs in any particular order, and hence results in a better insertion and access time than a normal map.

Storing a Map in a Map in C++

You can store a map inside a map. Usually, when we have both the key and value as integers we declare a map as

If we want the value to be another map, we can declare it as

This means that now we have a map where the key is an integer while the value elements will be another map that can store integer key-value pairs. You can modify the map according to your program needs and even have a vector or map inside a map.

For example, we can have something like:

or something like

Let us take a look at an example to understand this concept better.

Output

In the above code, we have created a map inside a map, i.e. for each key in the map the corresponding value element is also a map. To access the values we can use the [] operator as usual, but keep in mind that this time we have a map inside a map.

So, to access the map stored with the key i, we can use mp[i], while if we want to access the value of the key j in the map stored in key i, we use mp[i][j].

Conclusion

  • Maps in C++ are container structures that store elements in sorted key-value pairs. Each key is unique.
  • A map in C++ has the following inbuilt functions:
    • Access -
      1. Operator []
      2. at()
    • Capacity -
      1. empty()
      2. size()
      3. max_size()
    • Modifiers
      1. insert()
      2. erase()
      3. clear()
      4. swap()
      5. emplace()
      6. emplace_hint()
    • Iterators
      1. begin()
      2. end()
      3. rbegin()
      4. rend()
      5. cbegin()
      6. cend()
      7. crbegin()
      8. crend()
    • Searching and Counting
      1. find()
      2. count()
      3. lower_bound()
      4. upper_bound()
      5. equal_range()
  • Map in C++ helps makes searching elements faster since it is based on red - black trees and is easy to use.
  • It can be cumbersome to iterate the map and may even require more time if the size of the map is big, do don't use a map in C++ if you have to iterate through the map to search for an element.

Learn More: