Skip to main content

Chapter 23: Queue

核心问题与阅读主线

本章导读5 个核心小节 · 附自检与总结

std::queue 通过收窄底层容器接口,强制数据严格遵循“队尾写入、队首读取与删除”的 FIFO 顺序,防止调用者误触中间元素破坏排队契约。工程上用好它的关键,在于把每次队列调用准确映射到底层容器的端点成本、对象生命周期以及并发与容量边界。

全章共用代码样本(下文各节持续拆解)

贯穿材料核心代码

下面这段任务队列代码贯穿全章,集中展示 FIFO 端点转发、move-only 安全读取与 pop() 销毁时机:

#include <queue>
#include <string>

struct Job {
int id;
std::string payload;
};

void run(Job job);

void drain_jobs(std::queue<Job>& jobs) {
while (!jobs.empty()) {
Job current = std::move(jobs.front());
jobs.pop();
run(std::move(current));
}
}

std::queue::pop() 返回 void,将“读取队首”与“销毁队首”拆成两步:jobs.front() 先将队首对象移出到局部变量 current,jobs.pop() 再销毁原队首元素。

关键事实

std::queue<T, Container> 定义于头文件 <queue>,默认底层容器为 std::deque<T>;标准要求底层容器提供 front()、back()、push_back() 和 pop_front()(参见 C++ working draft queue definition 与 cppreference: std::queue)。

23.1 FIFO 语义与容器适配器目标​

std::queue 是容器适配器(container adaptor),不自行管理内存,而是封装一个底层序列容器 c,把公开接口收窄为 FIFO(first-in, first-out)端点操作:新元素只能从 back 写入,读取与删除只能发生在 front。

下面的简化模型直接体现 std::queue 的端点转发关系:

template<class T, class Container = std::deque<T>>
class queue_like {
protected:
Container c;

public:
bool empty() const { return c.empty(); }
std::size_t size() const { return c.size(); }

T& front() { return c.front(); }
T& back() { return c.back(); }

void push(const T& value) { c.push_back(value); }
void push(T&& value) { c.push_back(std::move(value)); }
void pop() { c.pop_front(); }
};

以贯穿示例 jobs 为例:依次压入 Job{1, "parse"}、Job{2, "index"}、Job{3, "flush"} 后,front() 指向 id == 1,back() 指向 id == 3;首轮读取 front() 并 pop() 后,队首推进到 id == 2。出队顺序完全由入队先后决定,Job::id 与 payload 不参与排序。

只要通过 std::queue 公开接口操作,调用者就无法从中间插入或跳过队首删除,从而以类型边界守住 FIFO 不变量。

核心判断

std::queue 的时间复杂度、内存分配与缓存局部性直接继承自底层容器端点操作(如 std::deque 分段连续存储 vs std::list 独立节点分配)以及元素自身的构造、移动和析构开销。

23.2 默认 deque 与可替换底层容器条件​

std::queue<T> 默认展开为 std::queue<T, std::deque<T>>。std::deque 面向两端增长且原生支持全部必需端点操作,是通用场景的首选。

可替换底层容器 Container 须同时满足两项条件:

  1. 类型一致:Container::value_type 必须与队列元素类型 T 相同。
  2. 端点完备:须提供常规语义的 front()、back()、push_back() 与 pop_front()。
#include <deque>
#include <list>
#include <queue>
#include <vector>

std::queue<int> default_queue; // uses std::deque<int>
std::queue<int, std::deque<int>> deque_queue; // valid underlying container
std::queue<int, std::list<int>> list_queue; // valid underlying container
// std::queue<int, std::vector<int>> vector_queue; // invalid underlying container choice

std::vector<int> 缺少 pop_front(),无法支撑 std::queue::pop() 的直接转发模型;即便用 erase(begin()) 模拟删除队首,也会引发后续元素整体搬移,违背队列端点的复杂度语义。

底层容器端点操作能力内存布局引用稳定性与额外成本适用场景
std::deque<T>完备(push_back + pop_front)分段连续存储两端修改按 deque 规则失效,缓存局部性较好通用任务队列、BFS、事件缓冲
std::list<T>完备(push_back + pop_front)每元素独立节点节点地址稳定,但每次入队出队涉及节点分配与指针开销大对象、需稳定引用/指针、长度剧烈波动
std::vector<T>缺 pop_front()整块连续数组不满足 queue::pop() 转发要求不可用作 std::queue 底层容器

边界与误区

注意
  • 空队列前提:对空队列调用 front()、back() 或 pop() 违反标准库接口前提,程序行为失去可靠语义。
  • 引用立即失效:std::queue 隐藏了 iterator,但一旦 pop() 销毁队首元素,此前从 front() 取得的引用与指针立即悬空,与底层采用 deque 还是 list 无关。
  • 异常安全:push() 转发至 push_back(),若元素构造、移动或内存分配在提交前抛出异常,队列保持原有状态。

23.3 push、pop、front 与 back 的状态路径​

std::queue 不提供“弹出并返回元素”的成员函数,读取与销毁必须由调用者组合完成。对照贯穿示例中的消费循环:

void drain_jobs(std::queue<Job>& jobs) {
while (!jobs.empty()) {
Job current = std::move(jobs.front());
jobs.pop();
run(std::move(current));
}
}

循环中的三个动作严格依赖先后次序:

  1. Job current = std::move(jobs.front()); 将队首对象移出到局部对象,原队首槽位仍留在队列中并处于 moved-from 状态。
  2. jobs.pop(); 销毁这个 moved-from 队首元素,触发析构并推进底层容器起点。
  3. run(std::move(current)); 处理已脱离队列生命周期的局部对象。

若颠倒顺序,或保留 front() 引用后再 pop(),就会访问已析构对象:

void wrong(std::queue<Job>& jobs) {
Job& ref = jobs.front();
jobs.pop();
run(ref); // ref no longer denotes a live queue element
}

边界与误区

注意
  • 把 front()/back() 视为瞬时别名:两者都返回队列内部元素的引用,仅在对应元素尚未被 pop() 前有效。
  • 单元素出队边界:通常 pop() 只影响队首而不改变队尾;但当队列仅剩 1 个元素时,pop() 会清空队列,导致原 front() 与 back() 引用同时失效。

back() 常用于观察最新入队元素;向队尾写入元素共有四种标准入口:

入队入口底层转发构造行为与适用场景
push(const T&)c.push_back(value)从左值拷贝构造入队
push(T&&)c.push_back(std::move(value))从右值移动构造入队
emplace(args...)c.emplace_back(args...)直接转发参数在队尾原地构造,减少临时对象
push_range(rg)批量追加到队尾C++23 新增,将一段范围按序批量入队
std::queue<Job> jobs;

Job parse{1, "parse"};
jobs.push(parse); // copy into the back
jobs.push(Job{2, "index"}); // move into the back
jobs.emplace(Job{3, "flush"}); // constructs through the adaptor interface

Job& first = jobs.front(); // id == 1
Job& last = jobs.back(); // id == 3

C++26 对 constexpr queue 的支持扩展了常量求值可用性,上述端点转发模型保持不变。

23.4 iterator 封装边界与顺序语义​

std::queue 公开接口不提供 begin() 和 end(),从接口层收回了底层容器的遍历、查找、排序与中间删改能力。消费全队列的标准写法是循环读取 front() 并 pop():

std::queue<int> values;
values.push(10);
values.push(20);
values.push(30);

while (!values.empty()) {
int current = values.front();
values.pop();
// process current
}

这层封装明确区分了“纯 FIFO 队列”与“可遍历序列容器”的适用边界:

维度使用 std::queue直接使用 std::deque / std::list
遍历方式只能破坏性 front() + pop()(无损查看须整体拷贝副本)原生迭代器无损遍历全部待处理项
中间修改禁止中间插入、条件删除或重排支持在任意位置插入、删除或重排
STL 算法无迭代器区间 [first, last),无法传给 std::find、std::sort、std::remove_if可直接接入区间型标准算法

核心判断

虽然 std::queue 将底层容器保存为 protected 成员 c,但工程上不应通过派生类暴露 c 的迭代器;一旦需要无损遍历、中间删除或重排,应直接改用 std::deque 或 std::list 并由业务层约束操作规则。

23.5 工程使用场景​

多线程任务队列与同步分工​

单线程任务队列可直接使用 std::queue<Job>;多线程生产消费场景下,std::queue 本身不含互斥锁与阻塞等待语义,必须由外层显式分离职责:

#include <condition_variable>
#include <mutex>
#include <queue>

class JobQueue {
public:
void push(Job job) {
{
std::lock_guard<std::mutex> lock(mutex_);
jobs_.push(std::move(job));
}
ready_.notify_one();
}

Job wait_and_pop() {
std::unique_lock<std::mutex> lock(mutex_);
ready_.wait(lock, [this] { return !jobs_.empty(); });
Job job = std::move(jobs_.front());
jobs_.pop();
return job;
}

private:
std::mutex mutex_;
std::condition_variable ready_;
std::queue<Job> jobs_;
};

std::queue 只负责 FIFO 存储,std::mutex 负责互斥访问,std::condition_variable 负责等待非空;若需要容量上限,还需额外维护 max_size 检查与“非满”等待条件。

广度优先搜索(BFS)​

BFS 需要先访问距离起点更近的节点再推进下一层,将新发现的邻居追加到队尾、从队首取出待访问节点即可自然形成按层遍历:

#include <queue>
#include <vector>

void bfs(int start, const std::vector<std::vector<int>>& graph) {
std::vector<char> visited(graph.size(), false);
std::queue<int> pending;

visited[start] = true;
pending.push(start);

while (!pending.empty()) {
int node = pending.front();
pending.pop();

for (int next : graph[node]) {
if (!visited[next]) {
visited[next] = true;
pending.push(next);
}
}
}
}

替换容器适配器会直接改变算法与调度语义:

适配器类型出队/弹出顺序对应的算法或调度语义
std::queue最早入队先出(FIFO)广度优先搜索(按层推进)
std::stack最新入栈先出(LIFO)深度优先遍历倾向
std::priority_queue按优先级比较器决定优先级调度 / 最佳优先搜索

事件缓冲与背压边界​

输入事件、网络包、日志项或 UI 消息按到达顺序缓冲时适用 std::queue,但须警惕两个边界:

  • 容量与背压:标准 std::queue 无内置容量上限,生产速率长期高于消费速率会导致队列无限增长,必须补充容量上限与背压策略。
  • 前瞻与合并:若处理端需要窥视后续事件或合并中间事件,纯 FIFO 接口会阻塞优化,应改用可遍历容器或专用缓冲结构。

排查顺序

  1. 确认顺序契约:业务是否严格按到达顺序(FIFO)消费,无需优先级插队。
  2. 确认访问边界:是否无需遍历、查找、合并或删除中间元素。
  3. 确认并发同步:多线程访问时,是否已由外层配齐 std::mutex 与条件变量。
  4. 确认容量上限:生产快于消费时,是否已设计 max_size 限制与背压策略。
  5. 评估底层容器:在 std::deque(默认、局部性较好)与 std::list(节点稳定性、大对象)间权衡端点成本。

最小自检任务​

动手自检先独立判断

判断下面三个队列声明(q1–q3)与 consume() 函数的用法是否适合表达 FIFO 队列,并从底层容器能力、端点操作、对象生命周期与工程语义四个角度说明理由。

#include <deque>
#include <list>
#include <queue>
#include <vector>

struct Job {
int id;
};

std::queue<Job> q1;
std::queue<Job, std::list<Job>> q2;
// std::queue<Job, std::vector<Job>> q3;

void consume(std::queue<Job>& jobs) {
Job& ref = jobs.front();
jobs.pop();
Job copy = ref;
}

本章知识点总结​

  • 适配器与 FIFO

    std::queue 定义于 <queue>,通过封装底层容器并隐藏 begin()/end(),将操作收窄为“队尾写入、队首读取与删除”的 FIFO 语义。

  • 底层容器条件

    底层容器的 value_type 须与元素类型一致,且须提供 front()、back()、push_back() 与 pop_front();因此默认 std::deque 与 std::list 可用,缺 pop_front() 的 std::vector 不可用。

  • 写入与构造路径

    push()(拷贝/移动)、emplace()(原地转发构造)与 C++23 push_range() 均向队尾追加元素,只改变构造方式而不改变 FIFO 顺序。

  • 读取、弹出与生命周期

    pop() 返回 void 并销毁队首元素,必须在非空队列上先通过 front() 拷贝或 std::move 移出对象,再调用 pop(),否则已取出的 front()/back() 引用立即悬空。

  • 算法与遍历边界

    没有公开迭代器使 std::queue 无法直接接入 [first, last) STL 算法,也无法无损遍历;需要中间查找、删除或重排时应直接使用 std::deque 或 std::list。

  • 并发与容量边界

    std::queue 不含互斥锁、条件变量或容量上限;多线程生产消费须在外层显式分离互斥与等待条件,高吞吐缓冲须额外设计背压与上限策略。

  • 选型顺序

    依次确认 FIFO 顺序、无遍历/中间修改需求、并发同步与容量上限,最后在 std::deque 与 std::list 间权衡底层端点与内存布局成本。