C++Map的区别

Posted on | In , | Views:

导言

面试别人时我常问一个编程题，也就是leetcode上的two sum，其中使用map和unordered_map的速度区别高达(打败)40%和(打败)88%,也就是快了接近一倍。使用map打败40%, 20ms, 使用unorderred_map打败88%， 12ms。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
  std::unordered_map<int, int> m;
  for(int i=0; i < nums.size(); i++ ){
    int residual = target-nums[i];
    if(m.find(nums[i]) != m.end()){
      return {m[nums[i]], i};
    }else{
    m.insert(pair<int, int>(residual, i));
    }
  }
  return {};
}
};

那么他们有什么区别呢？

原理上的区别

原理上来说，map采用二叉树(如红黑树等)来存储键值，键是有序的，而unordered_map则是采用哈希的方法来存储，是无序的。map的键必须定义operator <，而unordered_map必须定义operator =。C++的unordered_map其实就是Hashmap，但是因为c++有太多第三方库占用了std::hash_map这么一个名字，因此起名叫做unordered_map. (毕竟大家都能给std加料，这也是namespace的设计我感觉到还存在不足的地方)

另有hash_set, hash_multiset等数据结构
https://cloud.tencent.com/developer/article/1338322

使用上的区别

map由于是有序的，因此可以按区间取元素，存在以下方法，而unordered_map则不存在以下方法：

  • lower_bound
    Return iterator to lower bound (public member function )
  • upper_bound
    Return iterator to upper bound (public member function )
  • equal_range
    Get range of equal elements (public member function )
    cpp_diff_map

其他容器也类似，有两个版本，在原理上分使用二叉树的和使用hashmap的，在是否允许键重复分multiXXX和非multi的。

0%