Map in C++

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.

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

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(N*L) }$ whereas in this case, that is by using the map we have improved it to ${ O(log(N)*L) }$, where $N$ is the number of elements in the array and ${ 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

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

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, $True$ if the map is empty that is it does not contain any key-value pair in it, otherwise it returns $False$.

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++.

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:

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

Searching and Counting

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)) }$ where ${ 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) }$ where ${ L }$ is the average length of all the string as keys and ${ 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].

Learn More:

• Auto in C++.