Unordered Map Performing Much Slower than Map-CodePudding

Say I am attempting to solve the two-sum problem. Below are two samples of the same algorithm, one using an ordered map, and one using an un-ordered map.

Using unordered_map:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> d;
        int indx {0};
        for(auto num: nums){
            int complement {target - num};
            if(d.find(complement) != d.end()) {
                vector<int> answer {d[complement], indx};
                return answer;
            } else {
                d[num] = indx;
                indx  ;
            }
        }
    return vector<int> {-1, -1};
    }
};

Using (ordered) map (the only change):

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> d;
        int indx {0};
        for(auto num: nums){
            int complement {target - num};
            if(d.find(complement) != d.end()) {
                vector<int> answer {d[complement], indx};
                return answer;
            } else {
                d[num] = indx;
                indx  ;
            }
        }
    return vector<int> {-1, -1};
    }
};

With my understanding of the differences between the two objects, I do not understand why unordered_map is performing more slowly than the ordered map by a factor of three.

CodePudding user response：

The unordered_map has to allocate and copy to grow over and over while the map just allocates nodes.