Tutorial : STL Map 1 ( Basic Concepts ) timer 2s memory 1024MB

Now that you’ve studied the STL pair data type, let’s move on to learning the STL map data structure.

Take a look at the code below:

arr[1] = 1;
arr[1000000000] = 1;

This is a simple piece of code that puts the value 1 into index 1 and index 1,000,000,000 of the array arr.

But what problem would arise if we implemented this using a normal one-dimensional array?

To execute a[1000000000] = 1, the size of array a would have to be larger than one billion.

Even if we create an enormous array with one billion elements, only two positions—a[1] and a[1000000000]—are actually used.

How inefficient is that!

One way to solve this problem is by using an STL map.

As in the example above, an STL map is useful when the number of elements being inserted is small, but the range of values is extremely large.

(In the example, only 2 elements are inserted, but the range goes up to one billion.)

A map stores data in the form of pairs. It is provided in the #include <map> header.

The declaration is as follows:

#include <map>
using namespace std;

map<int, int> m;  // a data structure that stores pair<int, int>

You can declare it using the syntax map<type, type> name;.

When declared as map<int, int> m;,
m can store pair<int, int>, that is, ordered pairs of (integer, integer).

Now let’s learn how to insert ordered pairs into a map.

There are two representative methods.

If you want to insert the ordered pair {100, 200}, you can write:

map<int, int> m;

m[100] = 200;          // Method 1
m.insert({100, 200});  // Method 2

Both Method 1 and Method 2 are correct. In both cases, the ordered pair {100, 200} is inserted into m.

Method 1 is generally used a bit more often.

One important thing to note is that m[100] = 200 does not mean putting 200 into the 100th index of m.

m[100] = 200 means adding the ordered pair {100, 200} to the map.

Do not confuse a map with a one-dimensional array.

In a one-dimensional array, executing m[100] = 200 would require allocating memory for m[0] through m[99], wasting 100 memory slots.

In a map, however, m[100] = 200 creates memory for only one ordered pair {100, 200}.

This saves a tremendous amount of memory.

In a pair stored in a map, the first element is called the key, and the second element is called the value.

That is, in the ordered pair {100, 200} inserted into m,
key = 100 and value = 200.

Now consider the following code:

map<int, int> m;

m[5] = 8;  // {5, 8} is added
m[5] = 2;  // {5, 8} is replaced with {5, 2}
m[7] = 9;  // {7, 9} is added

At first, the ordered pair {5, 8} is added to m.

Later, {5, 2} is not added as a new pair; instead, the existing {5, 8} pair is replaced with {5, 2}.

In other words, for each key, only one value can exist.

Then the ordered pair {7, 9} is newly inserted.

The diagram below shows this at a glance.

Finally, let’s look at an important property of map: real-time sorting.

The elements of a map are automatically sorted in real time based on their keys (the first value of each pair).

Consider the following code, where five ordered pairs are inserted:

#include <map>
using namespace std;

int main(){
    map<int, int> m;

    m[2] = 3;
    m[-2] = 1;
    m[5] = 3;
    m[1] = 4;
    m[2] = 8;
}

Each time a line is executed, the ordered pairs are automatically sorted by their keys.

If you look at the diagram below, the principle becomes immediately clear.

Every time an ordered pair is inserted, the map sorts them in real time based on the key values.

If you look at the keys (the first numbers of each pair), you can see that they are always sorted.

Therefore, all insertion and lookup operations in a map take O(log N) time.

How can we print all elements of a map in order?

Since a map is a data structure that stores pairs, you can use a range-based for loop with auto.

Thus, there are two common methods shown below.

(Of course, there are several other ways as well.)

If you don’t understand the two methods below, make sure to review range-based for loops using auto.

map<int, int> m;

// Method 1: single variable element
for (auto element : m) {
    printf("%d %d\n", element.first, element.second);
}

// Method 2: separate variables [key, value]
for (auto [key, value] : m) {
    printf("%d %d\n", key, value);
}

※ Reference: What if you want to remove an ordered pair from a map?

You can use the erase() function.

If you want to remove {2, 8} from the diagram above, simply provide the key value 2.

m.erase(2);

What if you call m.erase(7)?

There was no ordered pair with key 7 to begin with, so nothing happens. (No error occurs.)

< Practice Problem >

People’s names are given as strings consisting only of lowercase English letters.
(Each name is at most 50 characters long.)

After all input has been processed, write a program that outputs, in lexicographical (dictionary) order, the line number on which each name was last entered.