C++11——散列表(哈希表)

 

散列表类型 有无关系值 接受相同键值
std::unordered_set
std::unordered_multiset
std::unordered_map
std::unordered_multimap

std::mapstd::unordered_map区别:

  std::map std::unordered_map
头文件 #include <map> #include <unordered_map>
内部实现 map内部实现了一个红黑树,红黑树具有自动排序的功能,因此map内部的所有元素都是有序的,红黑树的每一个节点都代表着map的一个元素。 unordered_map内部实现了一个哈希表,其元素的排列顺序是无序的,根据关键码值而进行直接访问的数据结构。
优点 有序性,在很多应用中都会简化很多的操作,效率非常的高 查找速度非常的快
缺点 空间占用率高,因为红黑树每一个节点都需要额外保存父节点、孩子节点和红/黑性质,使得每一个节点都占用大量的空间 哈希表的建立比较耗费时间
适用 有顺序要求的问题 查找问题

unordered_map的占用的内存比map高, 但unordered_map执行效率要比map高很多 。

unordered_map的用法和map是一样的,提供了 insertsizecount等操作,并且里面的元素也是以pair类型来存储的。

上一篇:c++数据结构总结


下一篇:map 和 unordered_map