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.