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在性能稳定性 + 接口适配性上最均衡，因此成为默认选择。

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 的时间复杂度

7️⃣ 如何实现小顶堆？

修改第三个模板参数（比较器）：

std::priority_queue< int, std::vector<int>, std::greater<int> > minHeap;

• 默认：std::less<T>→ 大顶堆

• 使用：std::greater<T>→ 小顶堆

四、进阶对比（加分项）

8️⃣ push() vs emplace()

👉推荐：优先使用emplace()

9️⃣ deque vs vector 作为 stack 底层对比

五、迭代器适配器（理解型）

🔟 reverse_iterator 的底层原理

本质：对正向迭代器的封装

• ++rit→ 实际执行--it

• --rit→ 实际执行++it

为什么rbegin() == end()？

STL 区间是左闭右开[begin, end)：

rbegin() = reverse_iterator(end())

解引用逻辑：

*rit 等价于 *(it - 1)

👉这是反向迭代器最容易被问的陷阱点

✅ 面试一句话总结

STL 适配器通过限制接口而不是增强功能，
保证数据结构的语义正确性，
是 STL 设计哲学中**“抽象与约束”**的典型体现。