C++ unordered_map及其基本结构和特性

  • 内容
  • 评论
  • 相关

unordered_map 包含的是有唯一键的键/值对元素。容器中的元素不是有序的。元素的位置由键的哈希值确定,因而必须有一个适用于键类型的哈希函数。如果用类对象作为键,需要为它定义一个实现了哈希函数的函数对象。如果键是 STL 提供的类型,通过特例化 hash<T>,容器可以生成这种键对应的哈希函数。

因为键可以不通过搜索就访问无序 map 中的对象,所以可以很快检索出无序 map 中的元素。迭代遍历无序 map 中的元素序列的速度一般没有有序 map 快,因此在某个应用中选择何种容器取决于想如何访问容器中的元素。

unordered_map 容器中元素的组织方式和 map 有很大的不同,元素的内部组织方式取决于 C++ 实现。一般情况下,元素被保存在哈希表中,这个表中的条目被称为格子,每个格子可以包含几个元素。

一个给定的哈希值会选择特定的格子,因为哈希值可能的个数几乎可以肯定会大于格子的个数,两个不同的哈希值可能会映射到同一个格子上。因此,不同键会产生相同的哈希值,会产生碰撞,而且两个不同的哈希值选择相同的格子也会导致碰撞的产生。

下面的一些参数可以影响元素存储的管理:

  • 容器中格子的个数有一个默认值,但也可以定指定初始个数。
  • 载入因子是每个格子平均保存的元素的个数。这个值等于容器中元素个数除以格子的个数。

最大载入因子,默认是 1.0,但也可以修改。这是载入因子的上限。当容器达到最大载入因子时,容器会为格子分配更多的空间,这通常也会对容器中的元素重新进行哈希。

任何时候都不要将单个格子中的最大元素个数和最大载入因子混淆。假设有一个容器,它有 8 个格子,前两个格子中各有 3 个元素,剩下的格子都为空。那么这时候的最大载入因子为 6/8,也就是 0.75,小于默认的最大载入因子 1.0,所以这没有什么问题。

图 1 展示了 unordered_map 的基本结构图。



图 1 unordered_map 中的数据

本文标题:C++ unordered_map及其基本结构和特性

本文地址:http://www.hosteonscn.com/2927.html

评论

0条评论

发表评论

邮箱地址不会被公开。 必填项已用*标注