容器适配器

定义与作用

容器适配器是对底层容器的接口封装，限制操作集合以适配特定的数据结构模型。三种标准适配器：

#include <stack>
#include <queue>

std::stack<int> stk;                    // 默认底层 deque<int>
std::queue<int> q;                      // 默认底层 deque<int>
std::priority_queue<int> pq;            // 默认底层 vector<int>
适配器概念模型默认底层核心操作
stackLIFO（后进先出）dequepush/pop/top
queueFIFO（先进先出）dequepush/pop/front/back
priority_queue最大堆vectorpush/pop/top

核心原理

适配器模式

底层容器要求

适配器底层容器必须支持
stackpush_back, pop_back, back
queuepush_back, pop_front, back, front
priority_queuepush_back, pop_back, back, 随机访问迭代器

完整示例

示例一：飞翔科技工单处理系统

场景说明：李眉用三种容器适配器实现飞翔科技的工单处理系统——紧急工单栈、普通工单队列、优先级工单堆。

#include <iostream>
#include <stack>
#include <queue>
#include <string>
#include <vector>

struct Ticket {
    int id;
    std::string reporter;
    std::string issue;
    int severity;  // 1-10

    Ticket(int i, std::string r, std::string iss, int sev)
        : id(i), reporter(std::move(r)), issue(std::move(iss)), severity(sev) {}
};

int main() {
    // ------------------- stack：紧急工单（LIFO）-------------------
    // 新到紧急工单直接压栈，最近的最先处理
    std::stack<Ticket> urgentStack;

    urgentStack.emplace(101, "孔蓝", "支付系统崩溃", 10);
    urgentStack.emplace(102, "赵鸣", "内容发布接口超时", 9);
    urgentStack.emplace(103, "孙鹤", "数据库连接池耗尽", 10);

    std::cout << "=== 紧急工单栈（后进先出）===\n";
    while (!urgentStack.empty()) {
        auto& t = urgentStack.top();
        std::cout << "  处理 #" << t.id << ": " << t.issue
                  << " (严重度: " << t.severity << ")\n";
        urgentStack.pop();
    }

    // ------------------- queue：普通工单队列（FIFO）-------------------
    std::queue<Ticket> normalQueue;

    normalQueue.emplace(201, "黄俪", "前端样式错位", 3);
    normalQueue.emplace(202, "林鸥", "图标资源缺失", 2);
    normalQueue.emplace(203, "朱璐", "社群消息延迟", 4);

    std::cout << "\n=== 普通工单队列（先进先出）===\n";
    while (!normalQueue.empty()) {
        auto& t = normalQueue.front();
        std::cout << "  处理 #" << t.id << ": " << t.issue
                  << " (严重度: " << t.severity << ")\n";
        normalQueue.pop();
    }

    // ------------------- priority_queue：按严重度优先级处理 -------------------
    auto cmp = [](const Ticket& a, const Ticket& b) {
        return a.severity < b.severity;  // 严重度高的优先
    };
    std::priority_queue<Ticket, std::vector<Ticket>, decltype(cmp)> pq(cmp);

    pq.emplace(301, "大翔", "安全漏洞：SQL 注入", 10);
    pq.emplace(302, "白歌", "架构设计评审", 7);
    pq.emplace(303, "小崔", "缓存击穿修复", 8);
    pq.emplace(304, "杨英", "活动页面文案修改", 2);
    pq.emplace(305, "高英", "用户反馈统计", 3);

    std::cout << "\n=== 优先级工单（严重度高优先）===\n";
    while (!pq.empty()) {
        auto& t = pq.top();
        std::cout << "  处理 #" << t.id << ": " << t.issue
                  << " (严重度: " << t.severity << ")\n";
        pq.pop();
    }
}

预期输出：

=== 紧急工单栈（后进先出）===
  处理 #103: 数据库连接池耗尽 (严重度: 10)
  处理 #102: 内容发布接口超时 (严重度: 9)
  处理 #101: 支付系统崩溃 (严重度: 10)

=== 普通工单队列（先进先出）===
  处理 #201: 前端样式错位 (严重度: 3)
  处理 #202: 图标资源缺失 (严重度: 2)
  处理 #203: 社群消息延迟 (严重度: 4)

=== 优先级工单（严重度高优先）===
  处理 #301: 安全漏洞：SQL 注入 (严重度: 10)
  处理 #303: 缓存击穿修复 (严重度: 8)
  处理 #302: 架构设计评审 (严重度: 7)
  处理 #305: 用户反馈统计 (严重度: 3)
  处理 #304: 活动页面文案修改 (严重度: 2)

逐段分析：

  • stack：最新到达的紧急工单最先被处理（后进先出）
  • queue：普通工单按到达顺序处理（先进先出）
  • priority_queue：按严重度排序，最高的优先（最大堆默认行为，但自定义了比较器）
  • 自定义比较器 decltype(cmp) 需作为模板参数传入

示例二：替换底层容器

场景说明：白歌演示更换容器适配器的底层容器。

#include <iostream>
#include <stack>
#include <queue>
#include <list>
#include <vector>

int main() {
    // stack 使用 vector 作为底层（不常见，但合法）
    std::stack<int, std::vector<int>> vecStack;
    vecStack.push(10);
    vecStack.push(20);
    // 注意：vector 的 pop_back 和 back 满足 stack 需求

    // queue 使用 list 作为底层（vector 不支持 pop_front）
    std::queue<int, std::list<int>> listQueue;
    listQueue.push(100);
    listQueue.push(200);

    // priority_queue 使用 deque 作为底层
    std::priority_queue<int, std::deque<int>> dequePQ;
    dequePQ.push(5);
    dequePQ.push(3);
    dequePQ.push(8);

    std::cout << "vector-stack top: " << vecStack.top() << "\n";
    vecStack.pop();

    std::cout << "list-queue front: " << listQueue.front()
              << ", back: " << listQueue.back() << "\n";

    std::cout << "deque-priority_queue top: " << dequePQ.top() << "\n";
}

预期输出：

vector-stack top: 20
list-queue front: 100, back: 200
deque-priority_queue top: 8

逐段分析：

  • stack<vector> 合法但非默认，vector 的 pop_back 不释放容量
  • queue<list> 常用，list 的前端删除是 O(1)
  • priority_queue<deque> 替代默认 vector，deque 在大量 push/pop 时扩容效率更好

易错场景与面试考点

易错场景

1. 容器适配器没有迭代器

std::stack<int> stk;
// stk.begin();    // ❌ 编译错误！适配器不暴露迭代器

2. priority_queue 默认是最大堆

std::priority_queue<int> pq;
pq.push(1); pq.push(5); pq.push(3);
std::cout << pq.top();  // 5，不是 1！
// 要最小堆：std::priority_queue<int, vector<int>, greater<int>>

3. queue 不支持 vector 底层

// std::queue<int, std::vector<int>> q;  // ❌ vector 没有 pop_front

面试考点

考点要点
适配器概念封装底层容器，限制为特定接口
默认底层stack=deque, queue=deque, priority_queue=vector
priority_queue 比较器第三个模板参数，默认 less（最大堆）
无迭代器适配器刻意不暴露迭代器，保持数据结构语义
时间复杂度push/pop 与底层容器一致
何时用适配器语义清晰：LIFO 用 stack，FIFO 用 queue，最优先用 priority_queue