Containers
摘要
C++ 标准模板库（STL）容器是用于存储数据的对象集合，它们提供了不同的存储方式、内存管理机制和访问模式。理解不同容器的底层结构、时间复杂度和内存特性，是高效进行C++编程的关键。
STL 容器主要分为三大类：序列容器、关联容器和无序容器。此外，容器适配器提供受限接口以模拟特定的数据结构（如栈和队列）。C++23 新增的扁平容器则代表了对内存局部性和性能优化的新探索。
容器总览表
| 容器类别 | 容器名称 | 描述 | 存储特性 | 核心操作复杂度 |
|---|---|---|---|---|
| 序列容器 (Sequence) | std::array (C++11) | 固定大小的静态数组。 | 栈上，连续内存 | 随机访问 \(O(1)\) |
| std::vector | 动态数组。 | 堆上，连续内存 | 随机访问 \(O(1)\)，末尾增删平均 \(O(1)\) | |
| std::deque | 双端队列。 | 分段连续内存 | 随机访问 \(O(1)\)，头尾增删 \(O(1)\) | |
| std::list | 双向链表。 | 堆上，非连续内存 | 任意位置增删 \(O(1)\) | |
| std::forward_list (C++11) | 单向链表。 | 堆上，非连续内存 | 头部增删 \(O(1)\) | |
| 关联容器 (Associative) | std::set/multiset | 存储键，基于红黑树。 | 红黑树结构，有序 | 查找/增删 \(O(\log n)\) |
| std::map/multimap | 存储键值对，基于红黑树。 | 红黑树结构，有序 | 查找/增删 \(O(\log n)\) | |
| 无序容器 (Unordered) | std::unordered_set/multiset | 存储键，基于哈希表。 | 哈希表结构，无序 | 查找/增删 平均 \(O(1)\) |
| std::unordered_map/multimap | 存储键值对，基于哈希表。 | 哈希表结构，无序 | 查找/增删 平均 \(O(1)\) | |
| 容器适配器 (Adaptors) | std::stack | LIFO（后进先出）。 | 默认底层 \(\text{std::deque}\) | \(O(1)\) |
| std::queue | FIFO（先进先出）。 | 默认底层 \(\text{std::deque}\) | \(O(1)\) | |
| std::priority_queue | 优先级队列（最大堆）。 | 默认底层 \(\text{std::vector}\) | 插入/删除 \(O(\log n)\) |
1. 序列容器 (Sequence Containers)
序列容器以线性方式排列元素，元素的位置由程序员控制，通常用于构建列表、数组等基础数据结构。
| 特性 | std::array | std::vector | std::deque | std::forward_list | std::list |
|---|---|---|---|---|---|
| 内存结构 | 连续内存 (栈/全局) | 连续内存 (堆) | 分段连续内存 | 非连续 (单向链表) | 非连续 (双向链表) |
| 随机访问 | \(O(1)\) (最快) | \(O(1)\) (快) | \(O(1)\) (快) | 不支持 | 不支持 |
| 头部增删 | 不支持 | \(O(n)\) | \(O(1)\) (快) | \(O(1)\) (最快) | \(O(1)\) (快) |
| 尾部增删 | 不支持 | 平均 \(O(1)\) (最快) | \(O(1)\) (快) | \(O(n)\) | \(O(1)\) (快) |
| 迭代器稳定性 | 稳定 | 插入可能失效，删除指向被删元素的失效。 | 插入/删除头尾稳定，中间失效。 | 增删不会使其他迭代器失效。 | 增删不会使其他迭代器失效。 |
| 优势场景 | 编译期确定大小，极高性能。 | 默认首选，需随机访问，主要在末尾操作。 | 需头尾快速操作和随机访问的场景。 | 极度频繁的插入/删除，内存占用要求低。 | 频繁在任意位置插入/删除，需双向遍历。 |
2. 有序关联容器 (Ordered Associative Containers)
关联容器基于键 (Key) 进行有序存储，通常使用红黑树实现。它们自动保持元素/键的排序，适用于需要排序和快速查找的场景。
| 特性 | std::set | std::multiset | std::map | std::multimap |
|---|---|---|---|---|
| 底层结构 | 红黑树 | 红黑树 | 红黑树 | 红黑树 |
| 操作复杂度 | 查找、插入、删除均为 \(O(\log n)\) | 查找、插入、删除均为 \(O(\log n)\) | 查找、插入、删除均为 \(O(\log n)\) | 查找、插入、删除均为 \(O(\log n)\) |
| 存储内容 | 仅存储唯一键 | 存储可重复键 | 存储唯一键值对 | 存储可重复键值对 |
| 元素顺序 | 始终保持排序 (按键) | 始终保持排序 (按键) | 始终保持排序 (按键) | 始终保持排序 (按键) |
| 迭代器稳定性 | 插入或删除不会使指向其他元素的迭代器失效。 | 插入或删除不会使指向其他元素的迭代器失效。 | 插入或删除不会使指向其他元素的迭代器失效。 | 插入或删除不会使指向其他元素的迭代器失效。 |
3. 无序容器 (Unordered Containers)
无序容器 (C++11) 基于 哈希表 实现。它们不保证元素顺序，但能提供极快的平均性能，适用于不关心元素顺序、追求极致查找速度的场景。
| 特性 | std::unordered_set | std::unordered_multiset | std::unordered_map | std::unordered_multimap |
|---|---|---|---|---|
| 底层结构 | 哈希表 (桶和链表/树) | 哈希表 | 哈希表 | 哈希表 |
| 操作复杂度 | 平均 \(O(1)\)，最坏 \(O(n)\) | 平均 \(O(1)\)，最坏 \(O(n)\) | 平均 \(O(1)\)，最坏 \(O(n)\) | 平均 \(O(1)\)，最坏 \(O(n)\) |
| 存储内容 | 仅存储唯一键 | 存储可重复键 | 存储唯一键值对 | 存储可重复键值对 |
| 元素顺序 | 无序 (取决于哈希值) | 无序 | 无序 | 无序 |
| 迭代器稳定性 | 不稳定。 \(\text{rehash}\) (重新散列) 时所有迭代器和引用都会失效。 | 不稳定。 \(\text{rehash}\) 时所有迭代器和引用都会失效。 | 不稳定。 \(\text{rehash}\) 时所有迭代器和引用都会失效。 | 不稳定。 \(\text{rehash}\) 时所有迭代器和引用都会失效。 |
4. C++23 扁平容器 (Flat Containers)
C++23 引入的扁平容器旨在优化内存局部性。它们使用有序的 \(\text{std::vector}\) 作为底层存储，将键或键值对连续存储，从而利用现代CPU的缓存机制。
| 容器名称 | 对应关联容器 | 底层结构 | 查找性能 | 插入/删除性能 | 优势/劣势 |
|---|---|---|---|---|---|
| std::flat_set / multiset | \(\text{std::set/multiset}\) | 有序 \(\text{std::vector}\) | \(O(\log n)\) (二分查找，比红黑树更快) | \(O(n)\) (需要移动元素) | 优势：极低的内存占用和极佳的遍历性能。劣势：高昂的插入/删除成本。 |
| std::flat_map / multimap | \(\text{std::map/multimap}\) | 一个或两个有序 \(\text{std::vector}\) | \(O(\log n)\) (二分查找，比红黑树更快) | \(O(n)\) (需要移动元素) | 适用于元素数量相对稳定、需要高查找速度和高效遍历的场景。 |
5. 容器适配器 (Container Adaptors)
容器适配器不是独立的容器，而是提供受限接口的类模板。它们使用底层容器来模拟特定的数据结构行为。
| 容器名称 | 接口模型 | 核心操作 | 默认底层容器 | 可选底层容器 |
|---|---|---|---|---|
| std::stack | LIFO (Last-In, First-Out) | \(\text{push()}\), \(\text{pop()}\), \(\text{top()}\) | \(\text{std::deque}\) | \(\text{std::vector}\), \(\text{std::list}\) |
| std::queue | FIFO (First-In, First-Out) | \(\text{push()}\), \(\text{pop()}\), \(\text{front()}\)/\(\text{back()}\) | \(\text{std::deque}\) | \(\text{std::list}\) |
| std::priority_queue | 优先级排序 (最大堆) | \(\text{push()}\), \(\text{pop()}\), \(\text{top()}\) | \(\text{std::vector}\) | \(\text{std::deque}\) |
6. 容器关键概念
迭代器 (Iterators)
迭代器是 STL 的核心，它提供了一种统一访问容器元素的方式，类似于指针。
- 随机访问迭代器：支持 \(O(1)\) 时间内的任意跳转（如 \(\text{std::vector}\), \(\text{std::deque}\), \(\text{std::array}\)）。
- 双向迭代器：支持向前和向后移动（如 \(\text{std::list}\), \(\text{std::set}\), \(\text{std::map}\)）。
- 前向迭代器：仅支持向前移动（如 \(\text{std::forward_list}\)）。
内存分配
- 连续内存：如 \(\text{std::vector}\) 和 \(\text{std::array}\)。优点是内存局部性好，CPU缓存利用率高；缺点是插入/删除中间元素成本高（需要移动后续元素）。
- 非连续内存：如 \(\text{std::list}\) 和红黑树/哈希表容器。优点是插入/删除效率高；缺点是内存碎片化，CPU缓存效率低。
异常安全 (Exception Safety)
- 强保证：如果操作失败（抛出异常），容器保持不变。
- 基本保证：如果操作失败，容器处于可用状态，但可能不是原来的状态。
- \(\text{std::vector}\) 的 \(\text{push_back}\) 在需要重新分配内存时，如果复制构造函数抛出异常，可能导致强保证失效。