无序映射执行速度比映射慢得多

Question

假设我正在尝试解决两和问题。下面是相同算法的两个示例，一个使用有序映射，另一个使用无序映射。

使用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};
}
};

使用(ordered) map(唯一更改):

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};
}
};

根据我对两个对象之间差异的理解，我不明白为什么unordered_map的执行速度比有序map慢三倍。

Answer 1

unordered_map必须分配和复制以不断增长，而map只是分配节点。