STL 容器
STL 容器总结笔记
STL 容器分为两大类：序列式容器 和 关联式容器。
一、序列式容器
按照元素插入的顺序存储，不会自动排序。
| 容器 | 底层结构 | 特点 |
|---|---|---|
vector |
动态数组 | 支持下标随机访问；适合尾部插入 |
array |
静态数组 | 原生数组的标准化封装；大小固定，不能扩容 |
deque |
基于 vector |
双端队列，分段连续空间，支持两端频繁插入和删除 |
list |
双向链表 | 支持在中间任意位置 O(1) 插入和删除 |
forward_list |
单向链表 | 比 list 节省一半指针内存；只能单向遍历 |
stack |
基于 vector |
栈；先进后出（LIFO） |
queue |
基于 deque |
队列；先进先出（FIFO） |
priority_queue |
基于堆（vector） |
优先队列；基于堆排序，元素按优先级出队 |
二、关联式容器
元素按照某种规则组织，支持高效查找。分为有序和无序两类。
1. 有序关联容器（基于红黑树）
查找时间复杂度：O(log n)
| 容器 | 存储内容 | 是否允许重复键 |
|---|---|---|
set |
仅键（key） | ❌ 不允许 |
multiset |
仅键（key） | ✅ 允许 |
map |
键值对（key-value），按 key 排序 | ❌ 不允许 |
multimap |
键值对（key-value），按 key 排序 | ✅ 允许 |
2. 无序关联容器（基于哈希表）
查找时间复杂度：O(1) （平均）
| 容器 | 存储内容 | 是否允许重复键 |
|---|---|---|
unordered_set |
仅键（key） | ❌ 不允许 |
unordered_multiset |
仅键（key） | ✅ 允许 |
unordered_map |
键值对（key-value） | ❌ 不允许 |
unordered_multimap |
键值对（key-value） | ✅ 允许 |
其他
std::string 有短字符串优化，在短字符串时使用对象内部的一个小数组，达到十几二十个字节长度的阈值时把字符串拷贝到堆内存上，原本的数组用来存储指针和 size + capacity。std::inplace_vector 在 C++26 中加入的动态固定数组，capacity 固定，size 动态，初始化时在对象内部分配内存（对象在哪内存就在哪，栈、堆或全局区，主要是栈上），其他和 vector 保持一致。也就是无法像 vector 一样扩容，也不用像 arrary 一样在初始化时构造全部元素。
总结
STL容器分为两大类：
第一大类是序列式容器：首先第一个 Vector 动态数组，可以根据下标进行随机的访问，适用于在尾部插入的情况；然后第二种 Array 是对原生数组的标准化封装，是静态数组，无法像 Vector 一样扩容；然后第三种 deque 双端队列，主要是用来支持在两端频繁插入删除操作；然后第四种 List 双向链表，可以支持在中间频繁的插入和删除，时间复杂度是 O(1)；然后第五种是 ForwardList 单向链表，它比 List 双向链表节省了一部分内存；然后第六种是基于 Vector 实现的栈 Stack，用于先进后出；然后第七种是基于 deque 的 Queue 队列，是先进先出；然后第八种是优先队列 PriorityQueue，是利用堆排序实现的一个有顺序的队列。
然后第二大类就是关联式容器，它也分为两类：第一类是有序的，基于红黑树进行排序，分别是 Set 和 MultiSet 还有 Map 和 MultiMap。Set 存储的是键，根据键值进行排序；Map 是根据键值对的键来排序；Multi 代表可以允许重复的键。因为基于红黑树，它们的查找效率是 O(log n)。然后是无序的，基于哈希表的关联式容器，分别是 unordered_set 和 unordered_multiset 还有 unordered_map 和 unordered_multimap，是基于哈希表的容器，它们的查找时间就是 O(1)。
