C++无序容器：特性、操作与应用

### C++ 无序容器：特性、操作与应用 #### 1. 无序容器概述 在 C++ 中，哈希表这种重要的数据结构最初并未包含在 C++ 标准库的第一版中。后来随着 TR1 的出现，具有哈希表特性的容器才被纳入标准。在 TR1 之前，C++ 社区中已有几种哈希表的实现，常见的有 `hash_set`、`hash_multiset`、`hash_map` 和 `hash_multimap`，但它们的实现略有不同。为避免命名冲突，标准中引入了以 `unordered_` 为前缀的容器类。 无序容器（也被称为无序关联容器）与普通关联容器的主要区别在于，无序容器中的元素没有定义的顺序，就像一个袋子，你可以放入元素，但访问时元素的顺序是随机的。与（多）集合和（多）映射不同，无序容器没有排序标准；与序列容器不同，你无法将元素放入特定位置。 无序容器主要分为以下几类： - **无序集合（Unordered Set/Multiset）**：存储特定类型的单个值。无序集合不允许重复元素，而无序多重集合允许。 - **无序映射（Unordered Map/Multimap）**：存储键值对，键用于存储和查找特定元素及其关联值。无序映射不允许重复键，而无序多重映射允许。 要使用无序集合或多重集合，需包含头文件 `<unordered_set>`；要使用无序映射或多重映射，需包含头文件 `<unordered_map>`。以下是这些类型在 `std` 命名空间中的定义： ```cpp namespace std { template <typename T, typename Hash = hash<T>, typename EqPred = equal_to<T>, typename Allocator = allocator<T> > class unordered_set; template <typename T, typename Hash = hash<T>, typename EqPred = equal_to<T>, typename Allocator = allocator<T> > class unordered_multiset; template <typename Key, typename T, typename Hash = hash<T>, typename EqPred = equal_to<T>, typename Allocator = allocator<pair<const Key, T> > > class unordered_map; template <typename Key, typename T, typename Hash = hash<T>, typename EqPred = equal_to<T>, typename Allocator = allocator<pair<const Key, T> > > class unordered_multimap; } ``` 无序集合或多重集合的元素可以是任何可比较的类型 `T`。对于无序映射和多重映射，第一个模板参数是元素键的类型，第二个模板参数是元素关联值的类型。元素的键和值必须满足以下两个要求： 1. 键和值都必须是可复制或可移动的。 2. 键必须能根据等价标准进行比较。 可选的第二个/第三个模板参数定义哈希函数，若未传递特殊哈希函数，则使用默认的 `hash<>` 函数。可选的第三个/第四个模板参数定义等价标准，默认使用 `equal_to<>` 比较元素。可选的第四个/第五个模板参数定义内存模型，默认使用 C++ 标准库提供的 `allocator`。 #### 2. 无序容器的能力 所有标准化的无序容器类都以哈希表的形式实现，但仍有多种实现选项。无序容器的一些特性基于以下假设： - **哈希表采用“链地址法”**：每个哈希码关联一个链表。 - **迭代器类型**：标准仅保证迭代器至少是前向迭代器，链表是单链还是双链由实现者决定。 - **重新哈希策略**： - **传统方法**：单个插入或删除操作可能会导致内部数据的完全重组。 - **增量哈希**：逐步调整桶或槽的数量，适用于实时环境。 无序容器允许使用这两种策略，且不保证与任何一种策略冲突。 使用哈希表的主要优点是其出色的运行时间性能。在哈希策略选择和实现良好的情况下，插入、删除和元素搜索操作的平均时间复杂度为常数。然而，无序容器的性能很大程度上取决于哈希函数的质量。如果哈希函数为不同元素生成相同的值，会导致哈希表操作的运行时间性能变差。 无序容器相对于普通关联容器也有一些缺点： - 不提供 `<`、`>`、`<=` 和 `>=` 运算符来对多个容器实例进行排序，但提供了 `==` 和 `!=` 运算符（自 C++11 起）。 - 不提供 `lower_bound()` 和 `upper_bound()` 函数。 - 由于迭代器仅保证是前向迭代器，不支持反向迭代器，也不能使用需要双向迭代器的算法。 由于元素的（键）值决定了其在哈希表中的位置，因此不能直接修改元素的（键）值。若要修改元素的值，必须先移除旧元素，再插入新元素。 作为程序员，你可以指定一些影响哈希表行为的参数： - 指定最小桶数。 - 提供自定义哈希函数。 - 提供自定义等价标准。 - 指定最大负载因子，超过该值时会自动重新哈希。 - 强制重新哈希。 但你无法影响以下行为： - 自动重新哈希时用于增长或缩小桶列表的增长因子。 - 当容器中元素数量减少时用于强制重新哈希的最小负载因子。 需要注意的是，重新哈希仅在调用 `insert()`、`rehash()`、`reserve()` 或 `clear()` 后才可能发生。这是为了保证 `erase()` 操作不会使迭代器、引用和指向元素的指针失效。 以下是无序容器操作的流程图： ```mermaid graph TD; A[创建无序容器] --> B[插入元素]; B --> C{是否需要重新哈希}; C -- 是 --> D[重新哈希]; C -- 否 --> E[继续操作]; E --> F[查找元素]; E --> G[删除元素]; F --> H[输出结果]; G --> H; D --> B; ``` #### 3. 创建和控制无序容器 哈希表是相当复杂的数据结构，因此有很多方法可以定义或查询其行为。 ##### 3.1 创建、复制和销毁 无序关联容器的构造函数和析构函数如下表所示： | 操作 | 效果 | | ---- | ---- | | `Unord c` | 默认构造函数，创建一个空的无序容器 | | `Unord c(bnum)` | 创建一个内部至少使用 `bnum` 个桶的空无序容器 | | `Unord c(bnum,hf)` | 创建一个内部至少使用 `bnum` 个桶，并使用 `hf` 作为哈希函数的空无序容器 | | `Unord c(bnum,hf,cmp)` | 创建一个内部至少使用 `bnum` 个桶，使用 `hf` 作为哈希函数，使用 `cmp` 作为等价标准的空无序容器 | | `Unord c(c2)` | 复制构造函数，创建另一个相同类型无序容器的副本 | | `Unord c = c2` | 复制构造函数，创建另一个相同类型无序容器的副本 | | `Unord c(rv)` | 移动构造函数，创建一个无序容器，获取右值 `rv` 的内容（自 C++11 起） | | `Unord c = rv` | 移动构造函数，创建一个无序容器，获取右值 `rv` 的内容（自 C++11 起） | | `Unord c(beg,end)` | 创建一个由范围 `[beg,end)` 中的元素初始化的无序容器 | | `Unord c(beg,end,bnum)` | 创建一个由范围 `[beg,end)` 中的元素初始化，内部至少使用 `bnum` 个桶的无序容器 | | `Unord c(beg,end,bnum,hf)` | 创建一个由范围 `[beg,end)` 中的元素初始化，内部至少使用 `bnum` 个桶，并使用 `hf` 作为哈希函数的无序容器 | | `Unord c(beg,end,bnum,hf,cmp)` | 创建一个由范围 `[beg,end)` 中的元素初始化，内部至少使用 `bnum` 个桶，使用 `hf` 作为哈希函数，使用 `cmp` 作为等价标准的无序容器 | | `Unord c(initlist)` | 创建一个由初始化列表 `initlist` 中的元素初始化的无序容器 | | `Unord c = initlist` | 创建一个由初始化列表 `initlist` 中的元素初始化的无序容器 | | `c.~Unord()` | 销毁所有元素并释放内存 | 可能的无序容器类型如下表所示： | 类型 | 效果 | | ---- | ---- | | `unordered_set<Elem>` | 一个默认使用 `hash<>` 进行哈希，使用 `equal_to<>`（`operator ==`）进行比较的无序集合 | | `unordered_set<Elem,Hash>` | 一个默认使用 `Hash` 进行哈希，使用 `equal_to<>`（`operator ==`）进行比较的无序集合 | | `unordered_set<Elem,Hash,Cmp>` | 一个默认使用 `Hash` 进行哈希，使用 `Cmp` 进行比较的无序集合 | | `unordered_multiset<Elem>` | 一个默认使用 `hash<>` 进行哈希，使用 `equal_to<>`（`operator ==`）进行比较的无序多重集合 | | `unordered_multiset<Elem,Hash>` | 一个默认使用 `Hash` 进行哈希，使用 `equal_to<>`（`operator ==`）进行比较的无序多重集合 | | `unordered_multiset<Elem,Hash,Cmp>` | 一个默认使用 `Hash` 进行哈希，使用 `Cmp` 进行比较的无序多重集合 | | `unordered_map<Key,T>` | 一个默认使用 `hash<>` 进行哈希，使用 `equal_to<>`（`operator ==`）进行比较的无序映射 | | `unordered_map<Key,T,Hash>` | 一个默认使用 `Hash` 进行哈希，使用 `equal_to<>`（`operator ==`）进行比较的无序映射 | | `unordered_map<Key,T,Hash,Cmp>` | 一个默认使用 `Hash` 进行哈希，使用 `Cmp` 进行比较的无序映射 | | `unordered_multimap<Key,T>` | 一个默认使用 `hash<>` 进行哈希，使用 `equal_to<>`（`operator ==`）进行比较的无序多重映射 | | `unordered_multimap<Key,T,Hash>` | 一个默认使用 `Hash` 进行哈希，使用 `equal_to<>`（`operator ==`）进行比较的无序多重映射 | | `unordered_multimap<Key,T,Hash,Cmp>` | 一个默认使用 `Hash` 进行哈希，使用 `Cmp` 进行比较的无序多重映射 | 在构造无序容器时，你可以传递初始元素值，如现有容器、元素范围或初始化列表；也可以传递影响容器行为的参数，如哈希函数、等价标准和初始桶数。需要注意的是，不能在类型定义或构造函数参数中指定最大负载因子，必须在构造后调用成员函数 `max_load_factor()` 来设置。一般来说，将最大负载因子设置为 0.7 到 0.8 之间的值可以在速度和内存消耗之间取得较好的平衡。 ##### 3.2 布局操作 无序容器提供了一些操作来查询和影响其内部布局，如下表所示： | 操作 | 效果 | | ---- | ---- | | `c.hash_function()` | 返回哈希函数 | | `c.key_eq()` | 返回等价谓词 | | `c.bucket_count()` | 返回当前桶的数量 | | `c.max_bucket_count()` | 返回可能的最大桶数 | | `c.load_factor()` | 返回当前