RobbEr's Blog

Welcome

STL-unordered_set

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

简介

unordered_set 直译为无序集合，为C++11引入的无序（哈希）容器，与 set 类似，都为键值对（Key-Value）容器，去除重复元素，但 unordered_set 无自动排序功能

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

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

类模板

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

成员函数

迭代器

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

容量相关

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

修改器相关

  1. clear() - 清空所有元素，size()置 0
  2. insert() - 插入一个或多个元素到指定位置
  3. erase() - 删除指定位置元素
  4. swap() - 交换元素
  5. emplace() - 插入一个元素到指定位置，调用构造函数
  6. emplace_hint() - 插入新元素到容器中尽可能接近于恰在 hint 前的位置，调用构造函数
  7. extract() - 从另一容器释出结点 (C++17)
  8. merge() - 从另一容器接合结点 (C++17)

元素查找相关

  1. count() - 返回匹配特定键的元素数量 O(1)
  2. find() - 寻找带有特定键的元素
  3. equal_range() - 返回匹配特定键的元素范围
  4. 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. load_factor() - 返回每个桶元素的平均数，即 size() 除以 bucket_count()
  9. max_load_factor(n) - 管理最大加载因子（每个桶的平均元素数）。若加载因子超出n，则容器自动增加桶数
  10. rehash(n) - 设置桶数为 n 并重哈希容器，若新的桶数使加载因子大于最大加载因子，则新桶数至少为 size() / max_load_factor()
  11. reserve(n) - 设置桶数为适应至少 count 个元素，而不超出最大加载因子所需的数，并重哈希容器，等价于 rehash(std::ceil(count / max_load_factor()))

unordered_set迭代器详解

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

const迭代器

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

1
2
3
4
unordered_set<int> v{ 1,2,3,4,5,6 };
auto i = v.begin(); //*i为1
i++;                //*i为2
*i = 100;           //error！

unordered_set特性

rehash后迭代器失效

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