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 适配器是一种设计模式，通过封装已有的容器 / 迭代器 / 函数对象，对其接口进行转换，使其符合特定使用场景。

三大类：

1. 容器适配器（Container Adapters）

   • std::stack

   • std::queue

   • std::priority_queue

2. 迭代器适配器（Iterator Adapters）

   • std::reverse_iterator

   • std::back_insert_iterator

   • std::front_insert_iterator

   • std::insert_iterator

3. 函数适配器（Function Adapters）

   • std::bind

   • std::function

   • std::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_back

• pop_back

• back

std::stack<int, std::vector<int>> s;

可选容器：

• vector

• deque（默认）

• list

---

queue

要求容器支持：

• push_back

• pop_front

• front

• back

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 设计哲学中**“抽象与约束”**的典型体现。