RobbEr's Blog

Welcome

STL-unordered_map

发表于 更新于 分类于 ， 阅读次数： Valine：
本文字数： 2.1k 阅读时长 ≈ 2 分钟

简介

unordered_map 为无序图，为为C++11引入的无序（哈希）容器，与 map 类似，都为键值对（Key-Value）容器

底层实现上，使用一个下标范围比较大的数组来存储元素，形成很多的桶，利用hash函数对key进行映射到不同区域进行保存，且由于其基于哈希表，插入元素和查找的时间复杂度很低，为 O(1)

unordered_map 为关联式容器，底层为哈希表（Hash-Table）

类模板

1
2
3
4
5
6
7
template<
    class Key,                          //key数据类型
    class T,                            //value数据类型
    class Hash = std::hash<Key>,        //哈希算法（哈希函数）
    class KeyEqual = std::equal_to<Key>,//判断元素是否相等所用函数
    class Allocator = std::allocator< std::pair<const Key, T> >//分配器
> class unordered_map;

成员函数

迭代器

  1. begin() - 返回指向 unordered_map 个元素的迭代器
  2. end() - 返回指向 unordered_map 中最后一个元素之后的理论元素的迭代器
  3. cbegin() - 返回指向 unordered_map 中第一个元素的const迭代器
  4. cend() - 返回一个const迭代器，指向 unordered_map 中最后一个元素之后的理论元素

容量相关

  1. size() - 返回 unordered_map 中元素数 O(1)
  2. max_size() - 返回 unordered_map 可以容纳的最大元素数 O(1)
  3. empty() - 当前 unordered_map 是否为空 O(1)

修改器相关

  1. clear() - 清空所有元素，size()置 0
  2. insert() - 插入一个或多个元素到指定位置
  3. erase() - 删除指定位置元素
  4. swap() - 交换元素
  5. emplace() - 插入一个元素到指定位置，调用构造函数
  6. emplace_hint() - 插入新元素到容器中尽可能接近于恰在 hint 前的位置，调用构造函数
  7. try_emplace() - 若键不存在则原位插入，若键存在则不做任何事(包括拷贝构造) (C++17)
  8. insert_or_assign() - 插入元素，若存在则赋值 (C++17)
  9. extract() - 从另一容器释出结点 (C++17)
  10. merge() - 从另一容器接合结点 (C++17)

元素查找相关

  1. at[g] - 返回对 g 处元素的引用
  2. operator[g] - 返回 g 处元素或插入元素到 g 处
  3. count() - 返回匹配特定键的元素数量 O(1)
  4. find() - 寻找带有特定键的元素
  5. equal_range() - 返回匹配特定键的元素范围
  6. contains() - 检查容器是否含有带特定键的元素 (C++20)

桶接口

  1. begin(n) - 返回指向下标为 n 的桶首元素的迭代器
  2. end(n) - 返回指向下标为 n 的桶 中最后一个元素之后的理论元素的迭代器
  3. cbegin(n) - 返回指向下标为 n 的桶首元素的const迭代器
  4. cend(n) - 返回一个const迭代器，指向下标为 n 的桶 中最后一个元素之后的理论元素
  5. bucket_count() - 返回容器中的桶数
  6. max_bucket_count() - 返回容器能容纳桶的最大数量
  7. bucket_size(n) - 返回下标为 n 的桶中的元素数
  8. bucket(n) - 返回关键值为 n 的桶的下标
  9. load_factor() - 返回每个桶元素的平均数，即 size() 除以 bucket_count()
  10. max_load_factor(n) - 管理最大加载因子（每个桶的平均元素数）。若加载因子超出n，则容器自动增加桶数
  11. rehash(n) - 设置桶数为 n 并重哈希容器，若新的桶数使加载因子大于最大加载因子，则新桶数至少为 size() / max_load_factor()
  12. reserve(n) - 设置桶数为适应至少 count 个元素，而不超出最大加载因子所需的数，并重哈希容器，等价于 rehash(std::ceil(count / max_load_factor()))

unordered_map迭代器详解

unordered_map 的所有迭代器都是正向迭代器

const迭代器

unordered_map 所返回的迭代器都是 const 迭代器，只能对其操作，不能更改其指向的值，即：

1
2
3
4
unordered_map<int, int>v{ {1,22},{3,44},{5,66},{7,88},{9,100} };
auto i = v.begin(); //*i为{9,100}
i++;                //*i为{1,22}
*i->first = 100;    //error！

unordered_map特性

rehash后迭代器失效

在操作 unordered_map 容器过程中，如果容器的大小超过了最大容量，会触发 rehash ，导致迭代器失效