容器适配器：栈、队列与堆优先级

受限接口是一种设计选择

stack 只暴露后进先出的 top、push、pop，queue 表达先进先出的 front、back、push、pop。默认底层容器都是 deque；stack 也可以用 vector，queue 则要求 pop_front，因此不能直接以 vector 为底层。适配器没有普通容器的公开迭代器接口，这是限制访问纪律，而不是遗漏功能。

这些操作的成本随底层容器而来，不能脱离底层一概判断。读取或弹出之前必须保证非空；pop 返回 void，不返回被删除值。通常先把 top 或 front 复制或移动到局部变量，再调用 pop，避免删除后继续使用指向旧元素的引用。

堆只保证顶端，不保证全局有序

priority_queue 默认使用 vector，并通过堆算法维护最高优先级元素。top 为常数时间；push 和 pop 的堆调整需要对数次比较，但 vector 扩容可能让某次 push 额外花费线性移动成本。批量构建堆具有线性比较复杂度，不必把现有整批数据逐项插入。

堆内部不是完整排序序列，不能从存储位置推断第二、第三高优先级。该适配器也没有直接更新任意元素优先级的接口。若任务优先级会改变，通常重新插入带版本的信息并在弹出时过滤旧版本，或者选择提供句柄更新能力的数据结构，而不是偷偷修改比较器读取的外部状态。

比较器方向与确定性的平局规则

比较器 comp(a,b) 为 true 表示 a 在比较顺序中排在 b 前面；堆顶是该顺序中的最大项。因此默认 less 产生数值最大项在顶端，greater 产生最小项在顶端。比较器仍须满足严格弱序，不能为了优先级相等而返回 true。

示例要求 deadline 越早越先执行，同一 deadline 按 id 越小越先，因此比较器把更晚或同时间更大 id 的任务判为“较前”，让较早者出现在顶端。没有平局字段时，等价任务的弹出顺序不保证稳定；需要可复现执行顺序就把单调序号或其他稳定键纳入比较。

最低标准 C++11 · 完整程序 · 下载 .cpp

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

struct Job { int deadline; int id; };
struct Later {
    bool operator()(const Job& a, const Job& b) const {
        if (a.deadline != b.deadline) return a.deadline > b.deadline;
        return a.id > b.id;
    }
};

int main() {
    std::stack<int> undo;
    undo.push(1);
    undo.push(2);
    assert(undo.top() == 2);
    undo.pop();
    assert(undo.top() == 1);

    std::queue<int> fifo;
    fifo.push(1);
    fifo.push(2);
    assert(fifo.front() == 1);
    fifo.pop();
    assert(fifo.front() == 2);

    std::priority_queue<Job, std::vector<Job>, Later> ready;
    ready.push(Job{5, 1});
    ready.push(Job{2, 3});
    ready.push(Job{2, 2});
    std::vector<int> order;
    while (!ready.empty()) {
        Job current = ready.top();
        ready.pop();
        order.push_back(current.id);
    }
    assert((order == std::vector<int>{2, 3, 1}));
    std::cout << order[0] << ' ' << order[1] << ' ' << order[2] << '\n';
}

在本地编译

g++ -std=c++11 -Wall -Wextra -Wpedantic -pthread stl-adapters.cpp -o example && ./example

预期结果

2 3 1

CHECK YOUR UNDERSTANDING

合上答案，试着解释。

需要从整数集合中反复取最小值，如何声明 priority_queue？如果值相等但必须保持任务到达顺序，还需要什么？

继续查证

• 标准草案 [priority.queue]：底层要求、比较器和堆操作

标准草案链接会随工作草案更新；本文版本标记对应示例最低要求，不表示草案中的所有新规则都适用于旧标准。