STL-适配器（面试复习4）
目录
C++ STL 适配器（Adapters）高频面试题整理版
一、基础概念类（必考）
1️⃣ 什么是 STL 适配器？分为哪几类？
二、容器适配器（🔥 核心重点）
2️⃣ stack / queue 的默认底层容器是什么？为什么？
3️⃣ priority_queue 的底层是什么？
4️⃣ 为什么 stack / queue 不提供迭代器？
5️⃣ 如何指定 stack / queue 的底层容器？
stack
queue
三、算法与复杂度（必背）
6️⃣ priority_queue 的时间复杂度
7️⃣ 如何实现小顶堆？
四、进阶对比（加分项）
8️⃣ push() vs emplace()
9️⃣ deque vs vector 作为 stack 底层对比
五、迭代器适配器（理解型）
🔟 reverse_iterator 的底层原理
为什么 rbegin() == end()？
✅ 面试一句话总结
C++ STL 适配器（Adapters）高频面试题整理版
核心一句话：
STL 适配器不是新容器/算法，而是对已有组件的接口封装与限制，体现的是适配器设计模式（Adapter Pattern）。
一、基础概念类（必考）
1️⃣ 什么是 STL 适配器？分为哪几类？
定义：
STL 适配器是一种设计模式，通过封装已有的容器 / 迭代器 / 函数对象，对其接口进行转换，使其符合特定使用场景。
三大类：
容器适配器（Container Adapters）
std::stackstd::queuestd::priority_queue
迭代器适配器（Iterator Adapters）
std::reverse_iteratorstd::back_insert_iteratorstd::front_insert_iteratorstd::insert_iterator
函数适配器（Function Adapters）
std::bindstd::functionstd::not1/std::not2（C++11 后已废弃，推荐 lambda）
二、容器适配器（🔥 核心重点）
2️⃣ stack / queue 的默认底层容器是什么？为什么？
默认底层容器：
std::deque原因分析：
| 对比点 | deque | vector | list |
|---|---|---|---|
| 头尾插删 | O(1) | 头部 O(n) | O(1) |
| 扩容成本 | 分段扩容，无整体拷贝 | 扩容需整体拷贝 | 无 |
| 内存局部性 | 较好 | 最好 | 最差 |
| 额外指针 | 无 | 无 | 多 |
👉结论：deque在性能稳定性 + 接口适配性上最均衡，因此成为默认选择。
3️⃣ priority_queue 的底层是什么？
数据结构：堆（Heap）
默认：大顶堆（Max Heap）
底层容器：
std::vector
原因：
堆是完全二叉树
使用数组 / vector 可通过下标快速定位：
左孩子：
2*i + 1右孩子：
2*i + 2
4️⃣ 为什么 stack / queue 不提供迭代器？
核心原因：维护抽象语义
stack：LIFO（后进先出）queue：FIFO（先进先出）
如果提供迭代器：
用户可访问中间元素
可破坏数据结构语义
与“只能在端点操作”的设计目标冲突
👉这是“接口约束”，不是能力不足
5️⃣ 如何指定 stack / queue 的底层容器？
容器适配器是模板类，可指定第二个模板参数。
stack
要求容器支持：
push_backpop_backback
std::stack<int, std::vector<int>> s;可选容器：
vectordeque（默认）list
queue
要求容器支持：
push_backpop_frontfrontback
std::queue<int, std::list<int>> q;⚠️vector❌（没有pop_front）
三、算法与复杂度（必背）
6️⃣ priority_queue 的时间复杂度
| 操作 | 复杂度 | 原因 |
|---|---|---|
push() | O(log n) | 向上调整（heapify up） |
pop() | O(log n) | 向下调整（heapify down） |
top() | O(1) | 直接访问堆顶 |
7️⃣ 如何实现小顶堆？
修改第三个模板参数（比较器）：
std::priority_queue< int, std::vector<int>, std::greater<int> > minHeap;默认：
std::less<T>→ 大顶堆使用：
std::greater<T>→ 小顶堆
四、进阶对比（加分项）
8️⃣ push() vs emplace()
| 对比 | push | emplace |
|---|---|---|
| 构造位置 | 容器外 | 容器内 |
| 临时对象 | 可能有 | 没有 |
| 拷贝 / 移动 | 有 | 无 |
| 性能 | 稍差 | 更优 |
👉推荐：优先使用emplace()
9️⃣ deque vs vector 作为 stack 底层对比
| 维度 | deque（默认） | vector |
|---|---|---|
| 扩容 | 分段，无整体拷贝 | 翻倍扩容 |
| 内存连续 | 伪连续 | 严格连续 |
| 空间浪费 | 少量 buffer | 最多 ~50% |
| 适用场景 | 通用、大对象 | 小对象、极致局部性 |
五、迭代器适配器（理解型）
🔟 reverse_iterator 的底层原理
本质：对正向迭代器的封装
++rit→ 实际执行--it--rit→ 实际执行++it
为什么rbegin() == end()？
STL 区间是左闭右开[begin, end)：
rbegin() = reverse_iterator(end())解引用逻辑：
*rit 等价于 *(it - 1)👉这是反向迭代器最容易被问的陷阱点
✅ 面试一句话总结
STL 适配器通过限制接口而不是增强功能，
保证数据结构的语义正确性，
是 STL 设计哲学中**“抽象与约束”**的典型体现。