C++ 头文件系列(unordered_map、unordered_set)

简介

好肯定,这点儿单头文件分别是map、set头文件对应之unordered版本。
所以它们来一个重点的特性就是:

  • 乱序

怎乱序

这unorder暗示着,这点儿只头文件中类的脚实现—-Hash
也是为如此,你才堪在声明这些unordered模版类的早晚,传入一个自定义的哈希函数,准确的身为哈希函数子(hash
function object)。

图片 1

不无同等相同哈希值的因素被在和一个桶(bucket)中。

干什么乱序

以供映射、集合功能的情状下,侧重于元素的快获得

之所以树结构(红黑树、二叉搜索树等)实现之map、set,在检索、获取、修改元素的时光,通常需从根结点自上而下一不良遍历树结构,因此光阴复杂度为线性
; 而透过哈希表实现,
只要哈希函数以及桶的大小选择得当,日复杂度会是常数(只需要调用一次等函数,并开展小增幅的觅)。

一面迭代器

哈希表的落实复杂了该容器上的双向遍历,似乎没有一样种植适于的不二法门能做到快速便捷。
因此,unorder版本的map和set只供前向迭代器(非unorder版本提供双向迭代器)。

丢掉了啊函数

  • lower_bound
  • upper_bound

常见版本的map和set,它们是稳步容器,对各个一个要素还能够还能够判定她应当当哪个之前、在哪个之后;
而该版的器皿则未雷同,因为她是乱序的,免克确定每个元素的先后顺序
因此,容器没有足够的音讯来计量这简单只境界(然而元素的相等性比较仍是行之有效之)。

大多了什么函数

由实现之概念,该版本的类模版必不可少的大都矣把出格之函数。

桶相关(Bucket)

  • bucket_count : 桶数量。
  • max_bucket_count : 最深桶数量。
  • bucket_size : 桶大小,即容量。
  • bucket : 定位被定元素的桶位置。

哈希策略

  • load_factor : 返回load
    factor
    ,即容器当前元素数量以及桶数量的比
  • max_load_factor : 返回或设置极端可怜load factor。
  • rehash : 设置桶的数码,并重新对素进行哈希映射。
  • reserve : 请求保留桶的多少及给定值。

注意到,没有函数能更改桶的容量,兴许桶也是动态增长之

Observers

  • hash_function :
    返回哈希函数(每当宣称时作参数传入,或默认的在funtional头文件被的hash)。
  • key_eq : 返回key的相等性谓词,情况及hash_function相似。