9、【C++】STL容器：deque、容器适配器：stack、queue、priority_queue的使用及介绍

目录

一、deque（双端队列）

1.1 deque的概念与特性

deque（Double-Ended Queue，双端队列）是C++标准库提供的双端动态数组容器，定义在<deque>头文件中。它结合了vector和list的优点，支持：

  • 高效的头尾插入/删除：时间复杂度O(1)（接近list）。
  • 随机访问：时间复杂度O(1)（接近vector）。
  • 动态扩容：无需整体搬迁数据（优于vector）。

核心特性：

  • 分段连续存储：数据存储在多个固定大小的缓冲区中，通过中控器管理缓冲区地址。
  • 复杂迭代器：迭代器需处理缓冲区边界跳转，实现逻辑比vector和list复杂。
  • 无预留容量：扩容时不会预留额外空间，内存利用率高于vector。

1.2 deque的内存结构：分段连续存储

deque的内存结构不同于vector的连续数组或list的离散节点，而是由中控器（Map） 和缓冲区（Buffer） 组成：

1.2.1 中控器（Map）

中控器是一个指向缓冲区的指针数组（T**），每个元素指向一个缓冲区。当缓冲区数量不足时，中控器会动态扩容（通常翻倍）。

1.2.2 缓冲区（Buffer）

缓冲区是固定大小的连续数组（默认512字节，可通过deque::resize()调整），用于存储实际数据。新元素优先填入当前缓冲区，填满后分配新缓冲区。

1.2.3 deque迭代器的实现原理

deque迭代器包含四个指针，用于处理缓冲区边界：

  • cur：指向当前元素。
  • first：指向当前缓冲区的起始地址。
  • last：指向当前缓冲区的结束地址（含空闲空间）。
  • node：指向中控器中当前缓冲区对应的指针。

迭代器移动逻辑：

  • ++it：若cur+1 < last，则cur++；否则跳转到下一个缓冲区的起始位置。
  • --it：若cur > first，则cur--；否则跳转到上一个缓冲区的末尾。

示意图：

中控器（Map）: [buf1*, buf2*, buf3*, ...]
               ↓       ↓       ↓
缓冲区（Buffer）: [0..511] [512..1023] [1024..1535] ...
                   ↑           ↑           ↑
迭代器: (cur=0, first=0, last=512, node=buf1*)

1.3 deque的迭代器操作与失效问题

  • 迭代器操作：支持++、--、+=n、-=n（随机访问），但跨缓冲区操作效率低于vector。
  • 迭代器失效：
    • 插入元素：
      • 头尾插入：若未触发中控器扩容，迭代器有效；否则所有迭代器失效。
      • 中间插入：所有迭代器失效（需重新分配中控器并调整缓冲区指针）。
    • 删除元素：
      • 头尾删除：迭代器有效（仅被删元素迭代器失效）。
      • 中间删除：所有迭代器失效。

1.4 deque的常用接口

1.4.1 构造与析构
#include <deque>

// 默认构造
std::deque<int> d1;

// 初始化n个val
std::deque<int> d2(5, 10); // {10,10,10,10,10}

// 范围构造
std::vector<int> v = {1,2,3};
std::deque<int> d3(v.begin(), v.end()); // {1,2,3}

// 列表初始化（C++11）
std::deque<int> d4{1,2,3,4}; // {1,2,3,4}

// 拷贝构造
std::deque<int> d5(d4);
1.4.2 元素访问
  • operator[]：随机访问，无越界检查（高效）。
  • at(size_t pos)：随机访问，越界抛出out_of_range（安全）。
  • front()：访问第一个元素。
  • back()：访问最后一个元素。
std::deque<int> d = {1,2,3,4};
d[0] = 5; // {5,2,3,4}
d.at(2) = 6; // {5,2,6,4}
std::cout << d.front() << d.back(); // 5 4
1.4.3 容量管理
  • size()：返回元素个数。
  • empty()：判断是否为空。
  • resize(size_t n, T val=T())：调整元素个数，新增元素用val填充。
  • shrink_to_fit()：释放未使用的缓冲区（C++11，非所有实现都支持）。
std::deque<int> d = {1,2,3};
d.resize(5, 0); // {1,2,3,0,0}
d.resize(2);    // {1,2}
d.shrink_to_fit(); // 释放多余缓冲区
1.4.4 修改操作
  • push_back(const T& val)：尾插元素。
  • pop_back()：尾删元素。
  • push_front(const T& val)：头插元素。
  • pop_front()：头删元素。
  • insert(iterator pos, const T& val)：在pos位置插入val。
  • erase(iterator pos)：删除pos位置元素。
  • swap(deque& other)：交换两个deque的内容。
  • clear()：清空所有元素（保留中控器和缓冲区）。
std::deque<int> d = {2,3};
d.push_front(1); // {1,2,3}
d.push_back(4);  // {1,2,3,4}
auto it = d.begin() + 2;
d.insert(it, 5); // {1,2,5,3,4}
d.erase(it);     // {1,2,5,4}（it指向3，删除后失效）

1.5 deque与vector、list的对比

特性dequevectorlist
随机访问O(1)（复杂迭代器）O(1)（简单指针）O(n)（需遍历）
头尾插入/删除O(1)O(1)（尾插）/O(n)（头插）O(1)
中间插入/删除O(n)（需移动元素+可能扩容）O(n)（需移动元素）O(1)（已知位置）
内存布局分段连续连续离散节点
迭代器复杂度高（多指针管理）低（原生指针）中（节点指针）
扩容效率高（新增缓冲区）低（整体搬迁）高（新增节点）
内存利用率中（无预留空间）低（可能预留大量空间）低（每个节点额外2指针）

1.6 deque的适用场景

  • 实现栈/队列：作为stack和queue的默认底层容器（兼顾头尾操作效率）。
  • 频繁头尾操作：如双端队列、滑动窗口问题。
  • 大数据量动态存储：避免vector扩容的性能开销。

反例场景：

  • 需要频繁中间插入/删除（优先list）。
  • 需要极致随机访问性能（优先vector）。

二、容器适配器概述

2.1 适配器模式与容器适配器

适配器模式是一种结构型设计模式，用于将一个类的接口转换为客户端期望的另一个接口。容器适配器（Container Adapter）通过封装底层容器，提供特定的数据结构接口，如栈、队列等。

STL中的容器适配器：

  • stack：封装底层容器为栈结构（LIFO）。
  • queue：封装为队列结构（FIFO）。
  • priority_queue：封装为优先级队列（有序输出）。

2.2 容器适配器的共性与差异

共性：

  • 封装底层容器：不直接管理数据，而是委托给底层容器（如deque、vector、list）。
  • 简化接口：仅暴露适配后的数据结构接口（如stack仅提供push/pop/top）。
  • 依赖底层容器迭代器：要求底层容器支持特定操作（如stack需要push_back/pop_back）。

差异：

  • 数据访问规则：stack（LIFO）、queue（FIFO）、priority_queue（优先级）。
  • 底层容器要求：
    • stack/queue：需支持push_back/pop_back/pop_front（deque/list）。
    • priority_queue：需支持随机访问和push_back/pop_back（vector/deque）。

2.3 底层容器的选择

适配器默认使用以下底层容器，也可通过模板参数指定：

  • stack：默认deque<T>，可选vector<T>、list<T>。
  • queue：默认deque<T>，可选list<T>（不支持vector，因无pop_front）。
  • priority_queue：默认vector<T>，可选deque<T>（不支持list，因无随机访问）。

指定底层容器示例：

#include <stack>
#include <vector>

// 基于vector实现的stack
std::stack<int, std::vector<int>> st;

三、stack（栈）

3.1 stack的概念与特性（LIFO）

stack是后进先出（LIFO, Last-In-First-Out） 的容器适配器，仅允许在尾部（栈顶） 进行插入和删除操作。

核心特性：

  • 单向操作：元素只能从栈顶进出。
  • 适配底层容器：默认使用deque，也可指定vector或list。
  • 无迭代器：不支持遍历，仅能访问栈顶元素。

3.2 stack的底层实现与接口封装

stack通过封装底层容器的以下接口实现栈功能：

  • push_back → push（入栈）。
  • pop_back → pop（出栈）。
  • back → top（访问栈顶）。

示意图：

stack（基于deque）:
push(1) → [1]
push(2) → [1,2]
pop()   → [1]（返回2）
top()   → 1

3.3 stack的常用接口

#include <stack>

std::stack<int> st;

// 入栈
st.push(1);
st.push(2);

// 访问栈顶
std::cout << st.top() << std::endl; // 2

// 出栈
st.pop(); // 栈变为[1]

// 容量操作
std::cout << st.size() << std::endl; // 1
std::cout << st.empty() << std::endl; // false

// 交换
std::stack<int> st2;
st.swap(st2); // st为空，st2为[1]

3.4 stack的应用场景

3.4.1 括号匹配

问题：判断字符串中的括号是否匹配（如"()[]{}“合法，”([)]"非法）。
思路：遇左括号入栈，遇右括号则弹出栈顶并检查匹配。

bool is_valid(const std::string& s) {
    std::stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top();
            st.pop();
            if ((c == ')' && top != '(') || 
                (c == ']' && top != '[') || 
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return st.empty();
}
3.4.2 逆波兰表达式求值

问题：计算逆波兰表达式（如"3 4 + 5 *" = (3+4)*5=35）。
思路：遇数字入栈，遇运算符弹出两个数计算后入栈。

int eval_rpn(const std::vector<std::string>& tokens) {
    std::stack<int> st;
    for (const std::string& token : tokens) {
        if (token == "+" || token == "-" || token == "*" || token == "/") {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            if (token == "+") st.push(a + b);
            else if (token == "-") st.push(a - b);
            else if (token == "*") st.push(a * b);
            else st.push(a / b);
        } else {
            st.push(std::stoi(token));
        }
    }
    return st.top();
}

3.5 stack的性能分析

  • 时间复杂度：push/pop/top均为O(1)。
  • 空间复杂度：O(n)（存储n个元素）。
  • 底层容器选择：
    • deque（默认）：无扩容开销，适合频繁入栈出栈。
    • vector：随机访问快，但扩容时可能有性能波动。
    • list：内存分配频繁，缓存效率低。

四、queue（队列）

4.1 queue的概念与特性（FIFO）

queue是先进先出（FIFO, First-In-First-Out） 的容器适配器，允许在尾部（队尾）插入、在头部（队头）删除。

核心特性：

  • 双向操作：元素从队尾入，从队头出。
  • 适配底层容器：默认使用deque，也可指定list。
  • 无迭代器：不支持遍历，仅能访问队头和队尾元素。

4.2 queue的底层实现与接口封装

queue通过封装底层容器的以下接口实现队列功能：

  • push_back → push（入队）。
  • pop_front → pop（出队）。
  • front → front（访问队头）。
  • back → back（访问队尾）。

示意图：

queue（基于deque）:
push(1) → [1]
push(2) → [1,2]
pop()   → [2]（返回1）
front() → 2, back() → 2

4.3 queue的常用接口

#include <queue>

std::queue<int> q;

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

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

// 出队
q.pop(); // 队列变为[2]

// 容量操作
std::cout << q.size() << std::endl; // 1
std::cout << q.empty() << std::endl; // false

// 交换
std::queue<int> q2;
q.swap(q2); // q为空，q2为[2]

4.4 queue的应用场景

4.4.1 广度优先搜索（BFS）

BFS是图/树的遍历算法，依赖queue实现逐层访问：

#include <queue>
#include <vector>

// 二叉树节点定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

// BFS遍历二叉树
std::vector<int> bfs(TreeNode* root) {
    std::vector<int> res;
    if (!root) return res;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        res.push_back(node->val);
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
    return res;
}
4.4.2 任务调度系统

queue常用于实现FIFO任务调度，如打印队列、消息队列等。

4.5 queue与stack的对比

特性stackqueue
数据访问规则LIFO（后进先出）FIFO（先进先出）
操作端仅栈顶队尾入，队头出
支持的接口push, pop, toppush, pop, front, back
底层容器选择deque, vector, listdeque, list（不支持vector）
典型应用表达式求值、回溯算法BFS、任务调度

五、priority_queue（优先级队列）

5.1 priority_queue的概念与特性

priority_queue是优先级驱动的容器适配器，每次出队的是优先级最高的元素（默认大顶堆，即最大值优先）。

核心特性：

  • 有序输出：元素按优先级排序，而非插入顺序。
  • 底层依赖堆算法：基于vector或deque实现，通过堆排序维护优先级。
  • 随机访问迭代器：要求底层容器支持随机访问（如vector）。

5.2 底层实现：堆算法与vector

priority_queue的底层容器默认是vector，通过以下堆算法维护优先级：

  • 插入（push）：元素添加到尾部，再通过push_heap上浮调整堆。
  • 删除（pop）：交换首尾元素，删除尾部，再通过pop_heap下沉调整堆。
  • 访问（top）：返回堆顶元素（vector[0]）。

堆结构示意图（大顶堆）：

      5
    /   \
   3     4
  / \   /
 1   2 0

5.3 priority_queue的常用接口

#include <queue>

std::priority_queue<int> pq; // 默认大顶堆

// 入队
pq.push(3);
pq.push(1);
pq.push(5); // 堆结构：5,3,1

// 访问队头（优先级最高元素）
std::cout << pq.top() << std::endl; // 5

// 出队（删除队头）
pq.pop(); // 堆结构变为3,1

// 容量操作
std::cout << pq.size() << std::endl; // 2
std::cout << pq.empty() << std::endl; // false

5.4 自定义比较器

默认情况下，priority_queue使用std::less<T>（大顶堆）。可通过以下方式自定义优先级：

5.4.1 使用函数对象
#include <functional>

// 小顶堆（最小值优先）
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
min_pq.push(3);
min_pq.push(1);
min_pq.push(5);
std::cout << min_pq.top() << std::endl; // 1
5.4.2 使用lambda表达式（C++11+）

需通过decltype推导lambda类型：

auto cmp = [](int a, int b) { return a > b; }; // 小顶堆逻辑
std::priority_queue<int, std::vector<int>, decltype(cmp)> pq(cmp);
pq.push(3);
pq.push(1);
pq.push(5);
std::cout << pq.top() << std::endl; // 1

5.5 priority_queue的应用场景

5.5.1 最大/最小元素快速访问

如从数据流中实时获取中位数，可使用两个优先级队列（大顶堆+小顶堆）。

5.5.2 事件驱动模拟

如操作系统的进程调度，优先级高的任务先执行。

5.6 priority_queue的性能分析

  • 时间复杂度：
    • push/pop：O(log n)（堆调整）。
    • top：O(1)。
  • 空间复杂度：O(n)。
  • 底层容器选择：
    • vector（默认）：随机访问效率高，堆调整更快。
    • deque：头尾操作高效，但堆调整时随机访问略慢于vector。

六、容器适配器的模拟实现

6.1 stack的模拟实现

template <typename T, typename Container = std::deque<T>>
class stack {
public:
    // 入栈
    void push(const T& val) { _con.push_back(val); }
    
    // 出栈
    void pop() { _con.pop_back(); }
    
    // 访问栈顶
    T& top() { return _con.back(); }
    const T& top() const { return _con.back(); }
    
    // 容量操作
    size_t size() const { return _con.size(); }
    bool empty() const { return _con.empty(); }

private:
    Container _con; // 底层容器
};

6.2 queue的模拟实现

template <typename T, typename Container = std::deque<T>>
class queue {
public:
    // 入队
    void push(const T& val) { _con.push_back(val); }
    
    // 出队
    void pop() { _con.pop_front(); }
    
    // 访问队头/队尾
    T& front() { return _con.front(); }
    const T& front() const { return _con.front(); }
    T& back() { return _con.back(); }
    const T& back() const { return _con.back(); }
    
    // 容量操作
    size_t size() const { return _con.size(); }
    bool empty() const { return _con.empty(); }

private:
    Container _con; // 底层容器
};

6.3 priority_queue的模拟实现

#include <algorithm>

template <typename T, typename Container = std::vector<T>, 
          typename Compare = std::less<T>>
class priority_queue {
public:
    // 入队（堆插入）
    void push(const T& val) {
        _con.push_back(val);
        std::push_heap(_con.begin(), _con.end(), _cmp);
    }
    
    // 出队（堆删除）
    void pop() {
        std::pop_heap(_con.begin(), _con.end(), _cmp);
        _con.pop_back();
    }
    
    // 访问队头（堆顶）
    T& top() { return _con.front(); }
    const T& top() const { return _con.front(); }
    
    // 容量操作
    size_t size() const { return _con.size(); }
    bool empty() const { return _con.empty(); }

private:
    Container _con; // 底层容器
    Compare _cmp;   // 比较器
};

七、总结与最佳实践

7.1 如何选择合适的容器/适配器

  • 需要LIFO操作 → stack。
  • 需要FIFO操作 → queue。
  • 需要优先级排序 → priority_queue。
  • 需要双端操作+随机访问 → deque。
  • 需要高效随机访问 → vector。
  • 需要频繁中间修改 → list。

7.2 避免常见错误

  • stack/queue使用vector作为底层容器：queue不支持vector（无pop_front）。
  • priority_queue自定义比较器：需指定容器和比较器两个模板参数。
  • 依赖迭代器遍历适配器：stack/queue/priority_queue无迭代器，不可遍历。
  • deque中间插入后使用旧迭代器：中间插入可能导致所有迭代器失效。

7.3 性能优化建议

  • stack/queue优先使用默认deque：平衡性能和灵活性。
  • priority_queue使用vector作为底层容器：堆调整效率更高。
  • 批量操作优先使用底层容器接口：如通过c()获取底层容器引用进行批量操作。
std::stack<int> st;
// 批量入栈（通过底层deque的assign）
st._Get_container().assign({1,2,3}); // 非标准接口，部分实现支持

通过合理选择容器和适配器，并理解其底层实现，可显著提升程序性能和可读性。

# c++
Logo
亚马逊云科技技术品牌专区

更多推荐

open-code-review Codex 插件教程：对话式调用评审技能指南

本文是一份面向新手的 **open-code-review Codex 插件教程**，教你在 Codex 中通过对话式方式调用 open-code-review 的 AI 代码评审技能。open-code-review 是阿里巴巴开源的 AI 代码评审工具，采用"确定性流水线 + LLM Agent"混合架构，内置多语言评审规则（NPE、线程安全、XSS、SQL 注入等），可在 Codex 里用一

avatar 亚马逊云科技技术品牌专区

OBS Studio 完整指南：免费开源录屏与直播软件从零上手

想做一场像模像样的直播，或者把屏幕内容录成教程视频，但一想到商用软件的订阅费就有些犹豫？其实你不需要花一分钱。OBS Studio 是一款免费开源的直播与录屏软件，支持 Windows、macOS 和 Linux，采集、混音、编码、推流、录制，一条流水线全包了。## 先搞清楚 OBS Studio 是什么OBS Studio 是一个"场景化"的采集合成工具：你把摄像头、窗口、浏览器、图片、

avatar 亚马逊云科技技术品牌专区

如何用MediaCrawler爬取小红书抖音数据？7大平台爬虫从安装到实战完整指南

MediaCrawler 是一个支持小红书、抖音、快手、B站、微博、百度贴吧、知乎的开源自媒体数据采集工具。它能按关键词、按帖子、按创作者主页三种方式抓取笔记/视频内容、评论甚至二级评论，并把结果存成 JSON、CSV、Excel 或数据库。适合做市场调研、竞品监控、内容选题的运营人员，以及想要现成爬虫框架而不想从零写 JS 逆向的开发者。## 从一次"手动抄数据"说起想象这个场景：你负责

avatar 亚马逊云科技技术品牌专区