C++ STL 容器底层实现与迭代器失效规则总结
本文整理自一次系统的STL学习笔记，重点梳理
vector、list、deque、map、unordered_map的底层数据结构、时间复杂度、内存模型以及迭代器失效的典型场景。
前言
使用STL容器时，如果只记API而不了解底层机制，很容易写出潜伏的bug。本文从内存布局和源码实现角度，对比分析几个常用容器的核心特性，适合作为面试前或日常开发的知识速查。
一、vector—— 动态数组
1. 底层结构
vector内部维护三个指针（GCC实现中的_M_start、_M_finish、_M_end_of_storage）：
_M_start：指向连续内存的起始位置。_M_finish：指向最后一个有效元素的下一个位置（size = _M_finish - _M_start）。_M_end_of_storage：指向已分配内存的尾部（capacity = _M_end_of_storage - _M_start）。
2. 扩容机制
当_M_finish == _M_end_of_storage时，触发扩容：
新容量通常为原容量的2倍（GCC）或1.5倍（VS）。
步骤：分配新内存 → 移动/拷贝构造元素 → 析构旧元素 → 释放旧内存 → 更新指针。
3. 迭代器失效
插入：若导致扩容，所有迭代器失效；否则插入点之后的迭代器失效。
删除：删除点之后的所有迭代器失效。
安全删除写法：
cpp
for (auto it = v.begin(); it != v.end(); ) { if (条件) it = v.erase(it); else ++it; }二、list—— 双向链表
1. 底层结构
每个节点包含
prev、next指针及数据。采用哨兵节点（不存储数据）作为头尾标记，简化边界处理。
2. 时间复杂度
随机访问：O(n)（不支持
[]）任意位置插入/删除：O(1)（仅改指针）
3. 迭代器失效
插入：任何迭代器均不失效。
删除：仅被删除元素的迭代器失效，其他迭代器保持有效。
删除写法同样推荐使用it = lst.erase(it);（C++11起erase返回下一个迭代器）。
三、deque—— 双端队列
1. 底层结构
由一段段固定大小的缓冲区组成，缓冲区通过中控器（指针数组）管理。
逻辑上连续，物理上分段。
2. 迭代器结构
deque的迭代器包含4个指针：
cur：指向当前元素first/last：当前缓冲区的头/尾node：指向中控器中当前缓冲区的管理单元
3. 时间复杂度
随机访问：O(1)（但有间接寻址）
头/尾插入删除：O(1)
中间插入删除：O(n)（需移动元素）
4. 迭代器失效
头部/尾部插入：迭代器失效，但引用通常不失效。
中间插入：所有迭代器失效。
头部/尾部删除：仅被删迭代器失效。
中间删除：删除点之后的迭代器失效。
四、map与unordered_map对比
1. 底层数据结构
map：红黑树（近似平衡二叉搜索树），元素按键有序。unordered_map：哈希表（桶数组 + 链地址法），元素无序。
2. 时间复杂度
| 操作 | map | unordered_map |
|---|---|---|
| 插入/删除/查找 | O(log n) | 平均 O(1)，最坏 O(n) |
| 空间开销 | 较大（节点存父/子指针及颜色） | 相对较小（仅存next指针，但预分配桶数组） |
3. 迭代器失效
map/set：插入/删除操作不会使任何已有迭代器失效（被删除元素自身的迭代器除外）。unordered_map/unordered_set：插入触发rehash时，所有迭代器失效；删除仅使被删迭代器失效。
⚠️ 注意：即便map删除不危及其他迭代器，当前被删的迭代器本身已失效，不能再对其操作。
正确遍历删除：
cpp
for (auto it = m.begin(); it != m.end(); ) { if (条件) it = m.erase(it); else ++it; }五、快速选型参考
| 需求场景 | 推荐容器 |
|---|---|
| 随机访问 + 尾部操作 | vector |
| 频繁在中间/头部插入删除 | list |
| 双端操作 + 随机访问 | deque |
| 需要有序键值对 | map |
| 只关心快速查找，不需顺序 | unordered_map |
总结
理解容器的底层实现，有助于写出更健壮、高效的代码，也能在调试时快速定位迭代器相关崩溃。希望这份总结能为你提供实用的参考。