This is the 1st Part of Tutorial series on std::map in C++. In this tutorial, we will learn about the STL Container map in C++, and we will discuss its internal data storage mechanisms in C++.

What is a Map in C++?

A map is an associative container provided by the Standard Template Library in C++. It stores elements in key-value pairs. Unlike unordered maps, which use hashing, maps in C++ are ordered by their keys. This ordering is typically implemented using a self-balancing binary search tree, like a Red-Black tree, which ensures efficient access to elements based on their keys.

As map maintains order, it does not require a hash function. The key type of a map must support comparison operations, typically using the less-than (<) operator.

What is a Red-Black Tree?

A Red-Black Tree is a type of self-balancing binary search tree, used internally by the map container in C++. Each node of the tree contains an element of the map, and the tree maintains its balance using a set of properties and color-coding (red and black) of nodes.

This structure allows maps to perform lookup, insertion, and deletion operations in logarithmic time complexity, O(log n), which is efficient for ordered data.

Why do we need map in C++?

The map container is highly efficient for scenarios where the order of elements is important. When we need to access, insert, or delete elements based on a sorted order, map becomes a more suitable choice than an unordered map. It offers logarithmic time complexity (O(log n)) for these operations, making it best for scenarios where ordered data is a critical factor.

Example of map

To use a map, first, we need to include the <map> header file. Then we can create an object of map by specifying the types of the key and value while creating its object. The syntax is as follows:

std::map<KeyType, ValueType> mapName;

Here, KeyType is the type of the keys and ValueType is the type of the values that the map will store. Here’s an example of using a map: We can initialize the map with an Initializer List of predefined key-value pairs. Like this,

#include <iostream>
#include <map>

int main() 
{
    // Creating a map to store words as keys
    // and their frequency as values
    std::map<std::string, int> wordFrequency = {
                                              {"Where", 20}, 
                                              {"How",    21}, 
                                              {"That",   19}
                                          };

    // Accessing elements from map
    std::cout << "Frequency of Word 'How' is: " << wordFrequency["How"] << std::endl;

    return 0;
}

Output:

Frequency of Word 'How' is: 21

We created a map of strings and integers, where keys are of string type and values are of integer type. Then we accessed the value associated with the key “How” from the map using the [] operator.

Summary

Today we have explored the concept of map in C++, its internal data storage mechanism. Maps are ideal for scenarios where ordered access to elements is important.

Ritika Ohri

Hi, I am Ritika Ohri, founder of this blog. I craft comprehensive programming tutorials and also manage a YouTube channel. You can also connect with me on Linkedin.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.