Chapter 23: Queue
核心问题与阅读主线
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 须同时满足两项条件:
- 类型一致:
Container::value_type必须与队列元素类型T相同。 - 端点完备:须提供常规语义的
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));
}
}
循环中的三个动作严格依赖先后次序:
Job current = std::move(jobs.front());将队首对象移出到局部对象,原队首槽位仍留在队列中并处于 moved-from 状态。jobs.pop();销毁这个 moved-from 队首元素,触发析构并推进底层容器起点。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 接口会阻塞优化,应改用可遍历容器或专用缓冲结构。
排查顺序
- 确认顺序契约:业务是否严格按到达顺序(FIFO)消费,无需优先级插队。
- 确认访问边界:是否无需遍历、查找、合并或删除中间元素。
- 确认并发同步:多线程访问时,是否已由外层配齐
std::mutex与条件变量。 - 确认容量上限:生产快于消费时,是否已设计
max_size限制与背压策略。 - 评估底层容器:在
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++23push_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间权衡底层端点与内存布局成本。