引言

C++ STL（标准模板库）为我们提供了丰富的容器类型，如 vector、list、map 等，用于高效地管理和操作数据。但在实际开发中，我们常常需要一些特殊的数据结构行为，比如“先进先出（FIFO）”队列、“后进先出（LIFO）”栈，或优先级队列。此时，STL容器适配器（Container Adapters）便应运而生。

1 什么是适配器？

容器适配器并不是独立的容器类型，而是对现有容器的功能进行封装和限制，使其表现出特定的数据结构行为。C++ STL 提供了三种主要的容器适配器：

stack（栈，LIFO）
queue（队列，FIFO）
priority_queue（优先队列，按优先级排序）

它们都是通过底层容器（如 deque、vector、list 等）实现的，但只暴露有限的接口，屏蔽了底层容器的其他操作。

2 stack

2.1 原理与底层实现

stack 通常以 deque 作为底层容器（也可指定为 vector 或 list），只允许在栈顶插入和移除元素，遵循“后进先出”原则。

2.2 常用接口

#include <stack>
#include <iostream>

int main() {
  // 创建一个空栈，底层容器为deque
  std::stack<int> s;

  // 入栈
  s.push(10);
  s.push(20);

  // 访问栈顶元素
  std::cout << "栈顶元素: " << s.top() << std::endl;  // 输出 20

  // 出栈
  s.pop();

  std::cout << "栈顶元素: " << s.top() << std::endl;  // 输出 10

  // 判断栈是否为空
  if (s.empty()) {
    std::cout << "栈为空" << std::endl;
  }

  // 获取栈的大小
  std::cout << "栈的大小: " << s.size() << std::endl;

  return 0;
}

2.3 适用场景

函数调用栈
括号匹配
深度优先搜索（DFS）

2.4 与其他方法对比

可以用 vector 或 list 手动实现栈，但 stack 适配器封装了接口，更安全、易用。
stack 不允许遍历或随机访问，只允许栈顶操作。

3 queue

3.1 原理与底层实现

queue 默认使用 deque 作为底层容器，遵循“先进先出”原则，只允许在队尾插入，在队头移除。

3.2 常用接口

#include <queue>
#include <iostream>

int main() {
  std::queue<int> q;

  // 入队
  q.push(1);
  q.push(2);

  // 访问队头和队尾
  std::cout << "队头: " << q.front() << std::endl;  // 输出 1
  std::cout << "队尾: " << q.back() << std::endl;   // 输出 2

  // 出队
  q.pop();

  std::cout << "队头: " << q.front() << std::endl;  // 输出 2

  // 判断队列是否为空
  if (q.empty()) {
    std::cout << "队列为空" << std::endl;
  }

  // 获取队列大小
  std::cout << "队列大小: " << q.size() << std::endl;

  return 0;
}

3.3 适用场景

广度优先搜索（BFS）
生产者-消费者模型
消息队列

3.4 与其他方法对比

用 deque 或 list 也可实现队列，但 queue 适配器接口更简洁，屏蔽了不必要的操作。
不能遍历或随机访问队列元素。

4 priority_queue

4.1 原理与底层实现

priority_queue 默认使用 vector 作为底层容器，并通过堆算法（通常是最大堆）实现元素的优先级排序。每次访问都是优先级最高的元素。

4.2 常用接口

#include <queue>
#include <vector>
#include <iostream>

int main() {
  // 默认最大堆
  std::priority_queue<int> pq;

  pq.push(5);
  pq.push(1);
  pq.push(10);

  std::cout << "当前最大值: " << pq.top() << std::endl; // 输出 10

  pq.pop();

  std::cout << "当前最大值: " << pq.top() << std::endl; // 输出 5

  // 最小堆实现（通过自定义比较器）
  std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
  min_pq.push(5);
  min_pq.push(1);
  min_pq.push(10);

  std::cout << "当前最小值: " << min_pq.top() << std::endl; // 输出 1

  return 0;
}

4.3 适用场景

贪心算法
Dijkstra最短路径
任务调度

4.4 与其他方法对比

可以用 set 或 multiset 实现优先级队列，但 priority_queue 插入和访问最高优先级元素更高效（对数时间）。
不能遍历或随机访问队列元素。

5 适配器的底层原理

容器适配器本质上是模板类，通过组合方式持有底层容器对象，并只暴露特定的接口。例如，stack 源码（简化版）如下：

template <typename T, typename Container = std::deque<T>>
class stack {
 public:
  // 入栈
  void push(const T& value) { c.push_back(value); }
  // 出栈
  void pop() { c.pop_back(); }
  // 访问栈顶
  T& top() { return c.back(); }
  // 判断空
  bool empty() const { return c.empty(); }
  // 获取大小
  size_t size() const { return c.size(); }
 private:
  Container c;  // 底层容器
};

6 扩展：自定义底层容器和比较器

容器适配器允许我们自定义底层容器和比较器。例如：

#include <stack>
#include <list>

// 使用list作为底层容器
std::stack<int, std::list<int>> custom_stack;

对于 priority_queue，可以自定义比较器：

#include <queue>
#include <vector>
#include <functional>

// 最小堆
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

7 总结与建议

容器适配器提供了安全、简洁的接口，适合特定数据结构场景。
只暴露必要操作，避免误用底层容器的其他接口。
性能优良，底层实现高效。
如果需要遍历或复杂操作，应选择底层容器直接操作。

目录CONTENT

C++ STL：容器-适配器

引言