【C++进阶】万字长文手写STL：从Vector到优先队列（Heap）的底层黑科技
前情提要：面试官问你：
priority_queue的底层是队列吗？queue为什么默认用deque而不是vector？
如果你答不上来，这篇硬核手写STL系列就是为你准备的。本文将从内存模型、常用接口到手写模拟，带你彻底攻克 Vector、List、Queue 以及最复杂的 Priority_queue（堆）。建议收藏，面试前突击必看！会用STL只是基本功，懂底层原理才是高手的入场券。
目录
- STL 六大组件概览
- 线性之王：Vector（动态数组）
- 底层原理与扩容机制
- 面试重灾区：迭代器失效
- 硬核实战：手写 MyVector
- 链表双雄：List（双向链表）
- 内存结构对比
- 为什么有了 Vector 还要 List？
- 核心逻辑：手写 MyList 节点管理
- 关联容器：Map 与 Unordered_map 的爱恨情仇
- 红黑树 vs 哈希表
- 容器适配器：Queue 与 Stack
- 为什么它们叫“适配器”？
- 几行代码封装 MyQueue
- 进阶难点：Priority_queue（优先队列/堆）
- 堆的物理结构 vs 逻辑结构
- 核心算法：上滤（AdjustUp）与 下滤（AdjustDown）
- 手写 MyPriorityQueue（面试高频！）
- 总结
1. STL 六大组件概览
在深入代码之前，我们先明确 STL 的核心架构。它不仅仅是容器，而是一个精密的生态系统：
- 容器 (Containers)：存放数据（Vector, List, Map…）
- 算法 (Algorithms)：操作数据（Sort, Find…）
- 迭代器 (Iterators)：连接容器与算法的桥梁（像指针一样的存在）
- （以及仿函数、适配器、空间配置器）
今天我们重点攻克容器。
2. 线性之王：Vector（动态数组）
2.1 底层原理与扩容机制
std::vector 本质上是一个连续内存的动态数组。它有三个核心指针：
_start：指向数组开头。_finish：指向有效数据的下一个位置。_end_of_storage：指向整个容量的末尾。
面试必问：Vector 是如何自动扩容的？
当空间不够（size() == capacity()）时，Vector 不会在原数组后面直接拼接（因为后面内存可能被占用了）。它的操作步骤是：
- 开辟新空间：通常是原容量的 1.5倍 (VS编译器) 或 2倍 (GCC编译器)。
- 数据拷贝：将旧数据拷贝到新空间。
- 释放旧空间：删除原来的数组。
- 更新指针：指向新地址。
代价：扩容是一次高成本操作（深拷贝），所以如果知道数据量，建议提前使用
.reserve(n)。
2.2 重灾区：迭代器失效
因为扩容可能导致地址变更，所以扩容后，原来指向旧空间的迭代器全部变成“野指针”，这就叫迭代器失效。
- 插入失效：
insert/push_back可能触发扩容。 - 删除失效：
erase会导致被删元素后面的迭代器错位。
2.3 硬核实战：手写 MyVector
拒绝纸上谈兵，我们用简化代码模拟一个 Vector 的核心逻辑，也就是手写STL容器，这是最好理解和使用STL的方法。
#include 3. 链表双雄：List（双向链表）
3.1 内存结构对比
- Vector：空间连续，支持随机访问
O(1)，但中间插入删除慢O(N)。 - List：空间不连续（一个个节点），不支持随机访问（不能用
[]），但任意位置插入删除极快O(1)。
3.2 核心逻辑：手写 MyList 节点
std::list 是一个带头双向循环链表。手写它的关键在于节点的定义。
// 定义节点结构
template<class T>
struct ListNode{
ListNode<T>* _next;
ListNode<T>* _prev;
T _data;
ListNode(const T& x=T()) : _next(nullptr),_prev(nullptr),_data(x) {}
};
// 简易 List 类
template<class T>
class MyList {
typedef ListNode<T> Node;
public:
MyList(){
// 初始化哨兵位头节点
_head=new Node;
_head->_next=_head;
_head->_prev=_head;
}
void push_back(const T& x){//添加函数
// 找尾节点
Node* tail=_head->_prev;
Node* new_node=new Node(x);
// 链接关系：tail--new_node--head
tail->_next=new_node;
new_node->_prev=tail;
new_node->_next=_head;
_head->_prev=new_node;
}
private:
Node* _head;
};
4. 关联容器：Map 与 Unordered_map 的爱恨情仇
这部分考察的是数据结构的底蕴。
| 特性 | std::map / set | std::unordered_map / set |
|---|---|---|
| 底层实现 | 红黑树 (Red-Black Tree) | 哈希表 (Hash Table) |
| 是否有序 | 有序 (按 Key 排序) | 无序 |
| 查找时间 | O(logN)O(log N)O(logN) (非常稳定) | O(1)O(1)O(1) (最坏情况 O(N)O(N)O(N)) |
| 迭代器 | 双向迭代器 | 前向迭代器 |
| 适用场景 | 需要范围查找、有序输出 | 单纯的高速查找、去重 |
💡 小技巧：
只要题目没有要求“按顺序输出”，首选unordered_map，因为它的平均速度比红黑树快得多！
5. 容器适配器：Queue（队列）
5.1 原理分析：它不是“容器”？
在STL中，stack 和 queue 被称为 容器适配器 (Container Adaptors)。
它们不直接管理内存，而是“寄生”在其他容器（如 deque 或 list）之上，封装出特殊的行为。
- Queue 特性：FIFO（先进先出）。
- 默认底层：
std::deque（双端队列）。- 问：为什么不用
vector？* - 答：
vector在头部删除（出队）是 O(N)O(N)O(N) 的，效率太低；而deque支持 O(1)O(1)O(1) 的头尾操作。
- 问：为什么不用
5.2 手写 MyQueue
我们可以利用模板参数，让用户自己选择底层容器（比如用 list 或 deque）。
#include 6. 进阶难点：Priority_queue（优先队列）
这是本文的重头戏！ 名字叫“队列”，但它的物理底层其实是 vector，逻辑结构是 堆 (Heap)（说这话看着都挺搞笑的）。
6.1 堆的原理（二叉树的数组化）
优先队列保证每次 top() 出来的都是最大值（大顶堆）或最小值（小顶堆）。它使用数组来模拟完全二叉树：
- 父节点下标：
parent = (child - 1) / 2 - 左孩子下标：
left_child = parent * 2 + 1
6.2 核心算法图解
想要手写优先队列，必须掌握两个调整算法：
- push (入堆) -> 向上调整 (AdjustUp)
- 先把数据插到数组末尾。
- 和父节点比，如果比父节点大（大顶堆），就交换，继续向上比。
- pop (出堆) -> 向下调整 (AdjustDown)
- 千万不能直接删头部！ 那样会破坏堆结构。
- 做法：交换
堆顶和数组末尾元素->pop_back()删除末尾 -> 从堆顶开始向下调整。
6.3 手写 MyPriorityQueue (硬核源码)
#include 💡 进阶思考：
如何实现小顶堆？
实际上 STL 使用了仿函数 (Functor)。你可以增加一个模板参数class Compare，把代码里的>换成comp(child, parent)，以此来控制比较逻辑。
7. 总结
| 容器 | 底层结构 | 迭代器 | 核心考点 |
|---|---|---|---|
| Vector | 动态数组 | 随机访问 | 扩容机制、深拷贝 |
| List | 双向链表 | 双向 | 任意位置插入不失效 |
| Queue | Deque (默认) | 无 | 为什么不用 Vector 做底层？ |
| Priority_queue | Vector + 堆算法 | 无 | TopK 问题、堆排序实现 |
手写容器不仅能帮你理解指针和内存管理，更是面试中展现你“技术深度”的杀手锏。建议大家把上面的 MyVector 代码自己敲一遍，尝试添加 insert 和 erase 功能！还有能够手写 Priority_queue 的话说明你数据结构功底扎实。建议大家把本文的代码 Copy 到编译器里跑一遍，甚至尝试去实现 make_heap 的逻辑！
