underSpirit's blog

By underSpirit, 8 years ago, In English

std::map is a commonly used C++ container in problem solving. But careless use of map can cause Time Limit Exceeded in some cases.

See Example 1

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
map<int, int>mp;
int main() {
    for ( int i = 1; i <= N; i++ ) mp[i]++;
    clock_t t = clock();
    for ( int i = 1; i <= N; i++ ) {
        if ( mp.find ( i ) != mp.end() ) {
            // found
        }
    }
    t = clock() - t;
    printf ( "Time 1: %lf\n", ( double ) t / CLOCKS_PER_SEC );
    t = clock();
    for ( int i = 1; i <= N; i++ ) {
        if ( mp[i] ) {
            // found
        }
    }
    t = clock() - t;
    printf ( "Time 2: %lf\n", ( double ) t / CLOCKS_PER_SEC );
    return 0;
}

In my computer Time 1: 0.420439 and Time 2: 0.420225. They are almost same!

Now, Example 2

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
map<int, int>mp;
int main() {
//    for ( int i = 1; i <= N; i++ ) mp[i]++;
    clock_t t = clock();
    for ( int i = 1; i <= N; i++ ) {
        if ( mp.find ( i ) != mp.end() ) {
            // found
        }
    }
    t = clock() - t;
    printf ( "Time 1: %lf\n", ( double ) t / CLOCKS_PER_SEC );
    printf ( "Size 1: %d\n", ( int ) mp.size() );
    t = clock();
    for ( int i = 1; i <= N; i++ ) {
        if ( mp[i] ) {
            // found
        }
    }
    t = clock() - t;
    printf ( "Time 2: %lf\n", ( double ) t / CLOCKS_PER_SEC );
    printf ( "Size 2: %d\n", ( int ) mp.size() );
    return 0;
}

Time 1: 0.055969 and Time 2: 0.779736. Here, Time 2 is almost 15 times greater than Time 1.

Now, what's the difference?

In Example 1 we checked N numbers where they were mapped and caused no time difference. But, in Example 2 N numbers weren't mapped and caused a huge time difference. What's the reason behind this effect?

When we use std::map::find it searches the container for an element with a key equivalent to k and returns an iterator to it if found, otherwise it returns an iterator to map::end.

But, on the other hand using std::map::operator : if k matches the key of an element in the container, the function returns a reference to its mapped value. If k does not match the key of any element in the container, the function inserts a new element with that key and returns a reference to its mapped value.

So, in Example 2 every time we are using mp[i], we are not only checking the existence of i but also mapping it with a value (more formally with 0).

In Example 2 we edited couple of extra lines to proof the above statements. This lines will show the size of the map after performing this operations.

We get Size 1: 0 and Size 2: 1000000. Look at Size 2, isn't it exactly N (number of values)?

Finally, we come to real time experience. Solve this problem, 732E - Sockets from Codeforces Round 377 (Div. 2) with using two different techniques of mapping and you will see the results.

Advance Sorry for your Time Limit Exceeded and Congrats for Accepted.

Tags stl
  • Vote: I like it
  • +75
  • Vote: I do not like it

»
8 years ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

I got tle for problem 722D - Generating Sets for same reason. TLE and AC.

»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Thanks bro . :) will keep in mind in the coming contests . :)

»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

It's not that shocking. How on earth would statement like mp[i]++ work if the map didn't add the element in the map(if absent) before incrementing (like you did in the first example).

»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Hi, just my two cents: I think it is much nicer to write

if (mp.count(i)) {
  // mp contains i
  // Do stuff
}

rather than

if (mp.find(i) != mp.end()) {
  // mp contains i
  // Do stuff
}

Of course this works with std::sets as well.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Sorry in advance for your TLE if you are using multiset :'(

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Recently faced the same issue in Div 4 but wasn't able to figure this out. Thanks for pointing out this so clearly