map、hash"/>
map、hash
unordered_map
转载:.html
同事告诉我用unordered_map代替hash_map,好像是标准推荐的吧。(都是哈希啦)
头文件#include <tr1/unordered_map>
命名空间using namespace std::tr1;
其他用法和hash_map一样~
随便说一点,hash_map和map的区别:
4.1 hash_map和map的区别在哪里?
构造函数。hash_map需要hash函数,等于函数;map只需要比较函数(小于函数).
存储结构。hash_map采用hash表存储,map一般采用红黑树(RB Tree)实现。因此其memory数据结构是不一样的。
4.2 什么时候需要用hash_map,什么时候需要用map?
总 体来说,hash_map 查找速度会比map快,而且查找速度基本和数据量大小无关,属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n) 小,hash还有hash函数的耗时,明白了吧,如果你考虑效率,特别是在元素达到一定数量级时,考虑考虑hash_map。但若你对内存使用特别严格,希望程序尽可能少消耗内存,那么一定要小心,hash_map可能会让你陷入尴尬,特别是当你的hash_map对象特别多时,你就更无法控制了,而且 hash_map的构造速度较慢。
现在知道如何选择了吗?权衡三个因素: 查找速度, 数据量, 内存使用。
本文是Devour Heavens撰写整理的关于C++标准库的知识,所有资料均来自于C++官方文档,欢迎转载。但是为了尊重原作者的劳动,请注明出处!谢谢!
class template
unordered_map
template < class Key, //unordered_map::key_type
class T, //unordered_map::mapped_type
class Hash = hash<Key>, // unordered_map::hasher
class Pred =equal_to<Key>, //unordered_map::key_equal
class Alloc = allocator<pair<const Key,T> > // unordered_map::allocator_type
> class unordered_map;
Unordered Map
哈希map是一种关联容器,通过键值和映射值存储元素。允许根据键值快速检索各个元素。
在unordered_map中,键值一般用来唯一标识元素,而对应的值是一个对象关联到这个键的内容。键映射值的类型可能会有所不同。 在内部unordered_map的元素不以键值或映射的元素作任何特定的顺序排序,其存储位置取决于哈希值允许直接通过其键值为快速访问单个元素(具有恒定平均的平均时间复杂度)。 unordered_map容器比map容器更快地通过键值访问他们的单个元素,虽然unordered_map一般都是比map通过其元素的一个子集范围迭代效率低。 哈希map允许使用操作运算符(运算符[])以其键值作为参数直接访问元素。
容器属性
关联
在关联容器的元素通过键值引用,而不是由他们在容器中的绝对位置。
无序
无序容器通过哈希表组织其元素的使用,允许通过键值快速访问其对应元素。
映射
每个元素关联到一键值对应一映射值:键值用于识别元素,其主要内容是键对应的值。
唯一键
在容器中没有两个元素可以有相同的键。
分配器的唤醒
容器使用一个分配器对象动态地处理其存储需求。
模板参数
Key
关键值的类型。一个unordered_map中的每个元素通过键值被唯一标识。
T
映射值的类型。 一个unordered_map中的每个元素是用来存储一些数据作为其映射值。别名为成员类型unordered_map:: mapped_type。请注意,这是和unordered_map:: value_type不同的(见下文)。
Hash
更多推荐
map、hash
发布评论