本文整理自一次系统的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. 迭代器失效插入若导致扩容所有迭代器失效否则插入点之后的迭代器失效。删除删除点之后的所有迭代器失效。安全删除写法cppfor (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);C11起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. 时间复杂度操作mapunordered_map插入/删除/查找O(log n)平均 O(1)最坏 O(n)空间开销较大节点存父/子指针及颜色相对较小仅存next指针但预分配桶数组3. 迭代器失效map/set插入/删除操作不会使任何已有迭代器失效被删除元素自身的迭代器除外。unordered_map/unordered_set插入触发rehash时所有迭代器失效删除仅使被删迭代器失效。⚠️ 注意即便map删除不危及其他迭代器当前被删的迭代器本身已失效不能再对其操作。正确遍历删除cppfor (auto it m.begin(); it ! m.end(); ) { if (条件) it m.erase(it); else it; }五、快速选型参考需求场景推荐容器随机访问 尾部操作vector频繁在中间/头部插入删除list双端操作 随机访问deque需要有序键值对map只关心快速查找不需顺序unordered_map总结理解容器的底层实现有助于写出更健壮、高效的代码也能在调试时快速定位迭代器相关崩溃。希望这份总结能为你提供实用的参考。
