本文整理自一次系统的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. 时间复杂度

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; }

五、快速选型参考

总结

理解容器的底层实现，有助于写出更健壮、高效的代码，也能在调试时快速定位迭代器相关崩溃。希望这份总结能为你提供实用的参考。