C++ unordered_map operator[ ] vs unordered_map.find() performance

Question

I was solving a competitive programming problem on interviewbit.com I basically used a unordered_map to keep track of visited numbers. When I used operator[], my code could not perform in time, but it passes all tests when I used find. Both should have same time complexity.

I tried timing both codes using clock() by running them 10 times and averaging out the run times and they both gave more or less same time. I used g++ 7.4.0 while the environment provided by website has g++ 4.8.4. Could this be the reason for this.

int Solution::solve(vector<int> &A) {
    unordered_map<long long, int> hashmap;
    for(auto a : A)
        hashmap[a] = 1;
    int res = 0;
    for(int i = 0; i < A.size(); ++i){
        for(int j = i + 1; j < A.size(); ++j){
          // if(hashmap.find((long long)A[i] + A[j]) != hashmap.end())
            if(hashmap[(long long)A[i] + A[j]] == 1)
                ++res;
        }
    }
    return res;
}

The problem was to find pairs in array whose sum also exist in the array. I got "time limit exceeded" on array size of about 900 when I used the [] operator.

Answer 1

There are two reasons why the []-operator will be slower than find:

1. The []-operator calls a non-const function on the map properly preventing all kinds of optimizations, like loop unrolling.
2. The more import reason: The []-operator creates non-existing elements in the map with their default value. The map will be bloated with all pairs of A[i] + A[j], that were not previously in the map and set their values to 0. This will increase the map size and thus the time.

I think your performance measurements showed no difference between the two alternatives because of one or more of this reasons:

1. The input vector is too small to make a difference
2. Most combinations of A[i] + A[j] are already in the vector, so the unordered_map is not bloated enough to make a difference
3. You did not optimize your code (-O3 or -Os) your code