In this article, we will learn how to work with two-dimensional (2D) maps in C++. We have explained the concept using C++ code examples.

Table of Contents

• Introduction - What is a 2D Map?
• Application
• Getting Started - Declaring a 2D Map
• Adding and Updating Keys/Values
• Accessing Values
• Erasing Key/Value Pairs
• Initializing a 2D Map Using an Initializer List
• Iterating through a 2D Map
• Complexity

Introduction - What is a 2D Map?

Essentially, a two-dimensional map is a map of maps, i.e. a nested map. It is similar to a 2D array, which is an array of arrays.

Application

This table shows how a 2D Map can store data. 2D Maps are very useful when there is nested information. For example, in the table above, each person has an identifier "name" and has several pieces of nested information (height, weight, and age).

Getting Started - Declaring a 2D Map

The syntax for creating a two-dimensional map is very similar to that of creating a one-dimensional map.

Below is the syntax for creating a one-dimensional map with keys of type int and values of type string.

1D Map

#include <iostream>
#include <map>
using namespace std;

int main () {
    map<int, string> map1d;
}

2D Map

Below is the syntax for creating a two-dimensional map. The keys in this map are ints and the values are maps. These inner maps have keys of type string and int values.

#include <iostream>
#include <map>
using namespace std;

int main () {
    map<int, map<string, int>> map2d;
}

Adding and Updating Keys/Values

The syntax for adding keys and updating values is very similar to that of a one-dimensional array, however, we are specifying two keys instead of one.

Here is the code to add a new key (0) to map2D, and setting its inner map's key "key" to 5.

#include <iostream>
#include <map>
using namespace std;

int main () {
    map<int, map<string, int>> map2d;
    map2d[0]["key"] = 5;
}

Here's how that works:
Since map2d is a 2D map, map2d[0] is a map itself, with the key being a string and the value being an int. Initially, map2d[0] had no elements, but now we have added an element with key "key" and value 5 to map2d[0]. Now, map2d has one element, where the key is 0 and the value is a map.

We can add other values to the inner map as well:

#include <iostream>
#include <map>
using namespace std;

int main () {
    map<int, map<string, int>> map2d;
    map2d[0]["key"] = 5;
    map2d[0]["new key"] = 10;
    map2d[1]["key"] = 15;
}

We can also update values:

#include <iostream>
#include <map>
using namespace std;

int main () {
    map<int, map<string, int>> map2d;
    map2d[0]["key"] = 5;
    map2d[0]["key"] = 10; // Updates the value that was previously set
}

Accessing Values

We can access values in 2D maps using the same syntax as we used for adding/updating values.

#include <iostream>
#include <map>
using namespace std;

int main () {
    map<int, map<string, int>> map2d;
    map2d[0]["key"] = 5;
    map2d[0]["key"] = 10;
    cout << map2d[0]["key"];
}

Output:
10

Erasing Key/Value Pairs

Erasing entire inner maps

Erasing an entire inner map is fairly straightforward - all we need to do is call the erase function and pass the key we want to erase as the argument.

Here's an example:

#include <iostream>
#include <map>
using namespace std;

int main () {
    map<int, map<string, int>> map2d;
    map2d[0]["key"] = 5;
    
    map2d.erase(0); // There is no longer any value for the key 0.
}

As a result of executing this, the entire inner map (which is the value for key 0 in map2d) is erased.

Erasing a specific key/value in an inner map

In order to erase a specific key/value in an inner map (eg. "key" in map2d[0]), we will first need to access the inner map, and then call the erase function.

#include <iostream>
#include <map>
using namespace std;

int main () {
    map<int, map<string, int>> map2d;
    map2d[0]["key"] = 5;
    
    map2d[0].erase("key"); // access map2d at key 0, 
    // then delete the key "key" from this inner map
}

Initializing a 2D Map Using an Initializer List

When we are creating a one-dimensional map, we can initialize a map using the following format:

#include <iostream>
#include <map>
using namespace std;

int main () {
    map<int, string> map1d = {
        {0, "hello"},
        {1, "bye"}
    };
}

We can initialize a two-dimensional map in a similar way. However, instead of a string, we have a map as the value. Each of these inner maps is in the same format as the map in the previous code segment.

#include <iostream>
#include <map>
using namespace std;

int main () {
    map<int, map<string, int>> map2d = {
        {0, {{"key", 5}, {"other", 10}}}, 
        {1, {{"key", 15}, {"other", 20}}}
    };

The above code is equivalent to writing:

#include <iostream>
#include <map>
using namespace std;

int main () {
    map<int, map<string, int>> map2d;
    
    map2d[0]["key"] = 5;
    map2d[0]["other"] = 10;
    
    map2d[1]["key"] = 15;
    map2d[1]["other"] = 20;
}

Iterating through a 2D Map

To iterate through a 2D map, we will need to iterate through the outer map and each inner map. Therefore, we will use nested for loops.

#include <iostream>
#include <map>
using namespace std;

int main () {
    map<int, map<string, int>> map2d;
    map2d[0]["key"] = 5;
    map2d[0]["other"] = 10;
    
    map2d[1]["key"] = 15;
    map2d[1]["other"] = 20;

    for (auto outer = map2d.begin(); outer != map2d.end(); outer++) {
        // print the key
        cout << outer->first << "\n";
        //iterate through the value, which is a map
        auto inner_map = outer->second;
        for (auto inner_iterator = inner_map.begin(); inner_iterator != inner_map.end(); inner_iterator++) {
            cout << inner_iterator->first << ": "; //print the inner key
            cout << inner_iterator->second << " "; // print the inner value
        }
        cout << "\n";
    }
}

Output:

0
key: 5 other: 10 
1
key: 15 other: 20 

Here's how that works:

To loop through a map, we use iterators. Every map iterator has members called first and second, which we access using the arrow operator (->). first is used to access the key, and second is used to access the value of each element in a map.

In the outer loop, we are using an iterator called outer. First, we print the key of each element using cout << outer->first. Then, we access the inner map by creating a new variable called inner_map (specified as auto for simplicity) and assigning it the value outer->second.

Then, we create an inner loop to iterate through inner_map, with an iterator called inner_iterator. Inside this loop, we print each key and value using inner_iterator->first and inner_iterator->second.

Complexity

Map Operations

The time complexity of map operations (eg. lookups, updates) is O(log(N)).

Iteration

Since we iterate through each inner map, the overall time complexity of complete iteration is O(NM), where N is the size of the outer map and M is the size of the inner maps.

Conclusion

That's it for this article! Hope you enjoyed reading.