unordered_map学习笔记

map的实现是红黑树，遍历使用中序遍历，由于是二叉搜索树，所以是有序的；

unordered_map的实现是hash_table；

hash_map在unordered_map实现之前先实现，但是unordered_map作为STL的标准被加入；hash_map和c++ stl的api不兼容，c++ tr1(C++ Technical Report1)作为标准的扩展，实现了hash map,提供了和stl兼容一致的api,称为unorder_map.在头文件 <tr1/unordered_map>中。

使用unordered_map，尽量不使用hash_map。

如果仅仅使用get操作，不涉及排序，使用unordered_map更优，因为get操作的时间复杂度为O(1)，而map的时间复杂度是lg(N);

例如3Sum需要插入排序，所以使用map。

使用自定义类型作为Key

map由于是红黑树，同时也是二叉搜索树，所以需要自定义类型需要重载'<'操作符。

使用unordered_map就比较复杂一点：

类需要重载==，用于如果hash值相同时，判断两个实体是否相同；

所以这个就会导致insert的最坏情况是O(N)，insert的平均时间是O(1);思考：最坏是O(N)，hash冲突采用的是开链法，最坏的时间是O(N);

map的insert的时间复杂度是lg(N);

另外自定义类的hash值怎么计算，所以需要另外一个计算自定义类的hash函数。例子如下：

	
	

		
		
struct Key
{
  std::string first;
  std::string second;
  int third;

  bool operator==(const Key &other) const
  { return (first == other.first
            && second == other.second
            && third == other.third);
  }
};
struct KeyHasher
{
  std::size_t operator()(const Key& k) const
  {
    using std::size_t;
    using std::hash;
    using std::string;

    return ((hash<string>()(k.first)
             ^ (hash<string>()(k.second) << 1)) >> 1)
             ^ (hash<int>()(k.third) << 1);
  }
};

int main()
{
  std::unordered_map<Key,std::string,KeyHasher> m6 = {
    { {"John", "Doe", 12}, "example"},
    { {"Mary", "Sue", 21}, "another"}
  };
}