STL map, hash_map , unordered_map区别、对比
首先:
hash_map
, unordered_map
比较
具体可见 stack overflow: Difference between hash_map and unordered_map?
由于在C++标准库中没有定义散列表hash_map
,标准库的不同实现者将提供一个通常名为hash_map的非标准散列表。因为这些实现不是遵循标准编写的,所以它们在功能和性能保证上都有微妙的差别。
从C++11开始,哈希表实现已添加到C++标准库标准。决定对类使用备用名称,以防止与这些非标准实现的冲突,并防止在其代码中有hash_table的开发人员无意中使用新类。
所选择的备用名称是unordered_map,它更具描述性,因为它暗示了类的映射接口和其元素的无序性质。
可见hash_map
, unordered_map
本质是一样的,只不过 unordered_map
被纳入了C++标准库标准。
map vs unordered_map
比较好的对比见:*:How to choose between map and unordered_map?
主要是,查询、插入、删除的时间复杂度三个方面:
unordered_map
(等价于hash_map
)和map
类似,都是存储的key-value
的值,可以通过key
快速索引到value
。不同的是unordered_map
不会根据key
的大小进行排序,
map
内部数据的组织,基于红黑树实现,红黑树具有自动排序的功能,因此map内部所有的数据,在任何时候,都是有序的。unordered_map
(hash_map
)
基于哈希表,数据插入和查找的时间复杂度很低,几乎是常数时间,而代价是消耗比较多的内存。底层实现上,使用一个下标范围比较大的数组来存储元素,形成很多的桶,利用hash函数对key进行映射到不同区域进行保存。
可以见STL源码剖析:
STL源码剖析-hash_set / hash_multiset
STL源码剖析-hash_map / hash_multimap
STL源码剖析-hashtable