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的对比

特性 deque vector list
随机访问 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的对比

特性 stack queue
数据访问规则 LIFO（后进先出） FIFO（先进先出）
操作端 仅栈顶 队尾入，队头出
支持的接口 push, pop, top push, pop, front, back
底层容器选择 deque, vector, list deque, 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
2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

cover

大模型工具使用技术演进：从Prompt到A2A通信协议全解析

avatar 2048 AI社区
cover

【程序员必学】GPT模型架构解析：预训练与微调技术详解（建议收藏）

avatar 2048 AI社区
cover

2026职场商务汇报PPT神器盘点：10款AI工具助你高效出稿，告别熬夜加班

avatar 2048 AI社区