Tutorial : STL Map 2 ( Element Search ) timer 2s memory 1024MB

If you have understood the concept of Map, let's now look at how to search for elements in a Map.

Since a Map is always sorted based on the key (the first element of the ordered pair), searching is also based on the key.

First, let's look at the code below. What would be the execution result?

map <int, int> m;

m[1] = 5; // Insert the ordered pair { 1, 5 } into m

if(m[2] == 5){ // Does an ordered pair with { key = 2 , value = 5 } exist in m?
    printf("YES");
}
else{
    printf("NO");
}

The execution result will, of course, be NO.

if(m[2] == 5) is asking if the ordered pair {2, 5} exists in m.

However, since m only contains the ordered pair {1, 5}, NO is printed.

The important point here is that even if you just execute m[2] == 5, the computer automatically inserts the ordered pair {2, 0} into m!

As learned previously, you didn't do m[2] = 0 or m.insert({2, 0}),

and yet the ordered pair {2, 0} is inserted just by checking if m[2] == 5.

Then why specifically { 2 , 0 }? Why is the second element, the value, 0?

When checking if m[2] == 5, there was no ordered pair with key value 2 in the first place.

Therefore, an ordered pair with key = 2 is automatically inserted, and since the value was not specified, it is entered as 0, the default value for int.

Then, what is the execution result of the code below?

map <int, int> m;

m[1] = 5; // Insert the ordered pair { 1, 5 } into m

if(m[2] == 0){ // Does an ordered pair with { key = 2 , value = 0 } exist in m?
    printf("YES");
}
else{
    printf("NO");
}

The answer is YES.

The moment m[2] == 0 is asked, the ordered pair { 2, 0 } is inserted into m,

and afterwards, the computer determines whether m[2] == 0 is true or false.

We have seen that just checking if a specific key value exists in a map causes an ordered pair to be automatically inserted.

Is there a way to prevent this?

This is where the find() function is used.

When searching for a key value with the find() function, an ordered pair is not automatically inserted even if the value is not present.

Let's ask the same question as the first code using find().

map <int, int> m;

m[1] = 5; // Insert the ordered pair { 1, 5 } into m

if(m.find(2) != m.end()){
    printf("YES");
}
else{
    printf("NO");
}

// Output result: NO

Using m.find(2) becomes the question, "Does an ordered pair with key value 2 exist in m?"

If it exists, the m.find() function returns an iterator to that ordered pair.

If it does not exist, the m.find() function returns m.end(), which is the end of this map.

In other words, if m.find(2) == m.end(), the ordered pair with key = 2 does not exist,

conversely, if m.find(2) != m.end(), the ordered pair with key = 2 exists.

The final summary of the two search methods above is as follows.

Since the state of the map does not change after searching when using the find() function,

it is slightly more recommended to use the find() function when searching for elements in a map.

<Application Problem>

A total of Q commands are given.

Suppose there is a "dictionary" that contains integers within the int range. Initially, this dictionary is empty.

The input commands are in one of the following three forms.

f x : If the integer x is in the dictionary, print "YES (count of x)"; otherwise, print "NO".

( It only checks if x exists; it does not add x. )

a x : Add one integer x to the dictionary.

c : Print how many different types of integers are currently in the dictionary.