STL 标准容器优劣简述（C++11 及以后，工程选型速查）

先划分大类： 顺序容器：vector、deque、list、forward_list、array 关联容器：set/multiset、map/multimap（红黑树，有序） 无序关联容器：unordered_set、unordered_map（哈希表）

一、顺序容器

1. std::vector（动态连续数组）

✅优点

1. 内存连续，随机访问 O (1)；
2. 缓存友好，遍历速度最快；
3. API 简单，支持尾插尾删摊销 O (1)。 ❌缺点
4. 中间插入 / 删除 O(n)，需要挪动大量元素；
5. 容量满时触发扩容，产生内存重分配、迭代器失效；
6. 不支持头部高效插入删除。 👉适用：绝大多数场景，优先默认选择。

2. std::deque（双端队列，分段连续内存）

✅优点

1. 头部、尾部插入删除均为摊销 O (1)；
2. 支持随机访问 O (1)（比 vector 略慢）；
3. 扩容不需要拷贝全部元素，迭代器失效范围更小。 ❌缺点
4. 内存分段，缓存局部性差，遍历慢于 vector；
5. 中间插入删除依然 O (n)。 👉适用：需要频繁头尾增删，又偶尔随机访问。

3. std::list（双向链表）

✅优点

1. 任意位置插入 / 删除 O (1)（前提已有迭代器）；
2. 不会发生内存重分配，插入不使其他迭代器失效。 ❌缺点
3. 无随机访问，只能顺序遍历；
4. 每个节点额外存储前后指针，内存开销大；
5. 内存碎片化，缓存极差，遍历很慢。 👉适用：频繁中间增删、极少遍历查找；现代工程很少用。

4. std::forward_list（单向链表）

✅优点：比 list 内存开销更小，只有后继指针。 ❌缺点：仅单向遍历，不支持反向迭代，不能获取 size ()。 👉适用：内存极度受限场景。

5. std::array（静态数组，栈 / 静态内存）

✅优点：栈分配、无堆开销、随机访问 O (1)、内存连续。 ❌缺点：容量编译期固定，不能动态扩容。 👉适用：长度已知的小型固定数组。

二、有序关联容器（红黑树实现：set/map/multiset/multimap）

std::set / std::map

✅优点

1. 自动有序；
2. 查找、插入、删除 O(log n)；
3. 迭代遍历按排序顺序输出；
4. set 自动去重；map 存储 key-value，key 唯一。 ❌缺点
5. 节点分散，缓存不友好；
6. O (log n) 复杂度，慢于哈希表；
7. key 不可修改（破坏有序结构）；
8. multiset/multimap 允许重复键。 👉适用：要求有序、需要范围查询（lower_bound/upper_bound）。

三、无序关联容器（哈希表 unordered_xxx）

unordered_set /unordered_map ✅优点

1. 平均查找、插入、删除 O (1)；性能高于红黑树容器； ❌缺点
2. 元素无序，不能范围查找；
3. 存在哈希冲突，最坏退化 O (n)；
4. 哈希表扩容会 rehash，迭代器失效；
5. 需要类型提供哈希函数； 👉适用：只需要快速查找，不要求排序。

关键横向对比总结（选型口诀）

1. 需要随机访问、频繁遍历 → vector
2. 需要头尾快速增删、偶尔随机访问 → deque
3. 大量中间插入删除、很少遍历查找 → list（谨慎）
4. 固定大小数组 → array
5. 需要有序、范围查找、自动排序去重 → map / set
6. 只需要快速查找，不要求顺序 → unordered_map / unordered_set

高频踩坑补充

1. vector 尽量 reserve 减少扩容；
2. list 不要用来做频繁查找，查找必须遍历；
3. unordered 容器不要依赖遍历顺序；
4. map/unordered_map不要修改 key；
5. 不要盲目用 list，绝大多数场景 vector 性能碾压 list。