转自https://blog.csdn.net/liumou111/article/details/49252645
在之前使用STL时，经常混淆的几个数据结构，特别是做Leetcode的题目时，对于使用哪一个map，一直没有太明确的概念，事实上，三个容器，有着比较大的区别.
1. map
内部数据的组织，基于红黑树实现，红黑树具有自动排序的功能，因此map内部所有的数据，在任何时候，都是有序的。
2. hash_map
基于哈希表，数据插入和查找的时间复杂度很低，几乎是常数时间，而代价是消耗比较多的内存。底层实现上，使用一个下标范围比较大的数组来存储元素，形成很多的桶，利用hash函数对key进行映射到不同区域进行保存。
- 插入操作：得到key -> 通过hash函数得到hash值 -> 得到桶号(hash值对桶数求模) -> 存放key和value在桶内
- 取值过程：得到key -> 通过hash函数得到hash值 -> 得到桶号(hash值对桶数求模) -> 比较桶内元素与key是否相等 -> 取出相等纪录的value
- 当每个桶内只有一个元素时，查找时只进行一次比较，当很多桶都没有值时，查询更快。
- 用户可以指定自己的hash函数与比较函数。
3. unordered_map
C++ 11标准中加入了unordered系列的容器。unordered_map记录元素的hash值，根据hash值判断元素是否相同。map相当于java中的TreeMap，unordered_map相当于HashMap。无论从查找、插入上来说，unordered_map的效率都优于hash_map，更优于map；而空间复杂度方面，hash_map最低，unordered_map次之，map最大。
对于STL里的map容器，count方法与find方法，都可以用来判断一个key是否出现，count统计的是key出现的次数，因此只能为0/1，而find基于迭代器实现，以mp.end()判断是否找到要求的key。
下面测试说明了速度之间的比较：
| map类型 | 插入速度 | 插入和查找速度 |
|---|---|---|
| hashmap | 0m0.123s | 0m0.369s |
| map | 0m0.190s | 0m0.681s |
| unordered_map | 0m0.123s | 0m0.315s |
- 为什么要使用unordered_map代替hash_map？
- 因为标准化的推进，unordered_map原来属于boost分支和std::tr1中，而hash_map属于非标准容器。
- 另外，使用之后，感觉速度和hash_map差不多，但是支持string做key，也可以使用复杂的对象作为key。
- gxx需要添加编译选项：--std=gnu++0x或者--std=c++0x