开头搞C的迟早要跟std::queue、std::stack、std::priority_queue这些容器适配器打交道。但很多初学者有个误区以为priority_queue就是排队结果一用发现每次弹出的不是先进来的而是最大的那个当场懵掉。还有deque很多人把它和queue搞混以为就是个队列结果一看头文件名字都不带queue前缀——#include deque。这两个东西一个用在需要动态取最大/最小值的场景一个用在需要在头尾两边高频插入删除的场景都是STL里压迫感很强、但用对了非常省心的组件。这篇东西我不打算只讲怎么调API。我要把priority_queue和deque从使用到实现全部拆开先讲怎么用、再讲为什么这么设计、最后讲底层怎么组织数据。看完你至少能回答两个问题第一面试官问priority_queue的底层是什么你为什么能秒答第二让你手写一个deque的迭代器框架你知道它为什么长那个样子。中间还会穿插我实际开发中踩过的坑基本都是文档里不会写的那种。1. 先搞懂一件事priority_queue到底是什么1.1 一句话版本它不是队列是堆std::priority_queue是C标准库里的容器适配器底层默认用vector上面套了一层heap算法对外暴露出的行为就是每次弹出当前最大或最小的元素。说白了它就是给你封装好了的二叉堆。它的声明长这样template class T, class Container std::vectorT, class Compare std::lesstypename Container::value_type class priority_queue;三个模板参数第一个是元素类型第二个是底层容器第三个是仿函数类型的比较器。默认是std::less所以默认是大顶堆——队头是最大元素。这里有个新手常见的认知反转std::less这个名字容易让人以为是从小到大但在priority_queue的语境里less对应的行为是大顶堆。原因后面讲实现的时候会解释。1.2 基本操作谁都会关键是感觉API其实很少priority_queueint pq; pq.push(3); // 插入元素O(log n) pq.push(5); pq.push(1); int top pq.top(); // 看一眼堆顶O(1) pq.pop(); // 弹出堆顶O(log n) bool empty pq.empty(); size_t len pq.size();我在实际项目里对priority_queue最直观的感觉是它像一道自动排序的闸门只对当前最紧急的那一个开放。你往里面丢任务它每次放行优先级最高的放行完然后再自动调整继续放行下一个。这个过程不需要你手动维护任何有序状态。面试或笔试里最常见的应用场景我给你列几个TopK问题维护一个大小为K的小顶堆遍历数据堆顶就是第K大的元素。时间复杂度O(n log K)比全排序的O(n log n)快一个量级。Dijkstra最短路堆优化版本每次拿出当前距离最小的节点去松弛邻边避免每次线性扫一遍找最小值。任务调度服务器按优先级处理请求队列新请求来了进堆处理完一个pop一个。合并K个有序链表每个链表头进堆每次弹出最小节点再把该链表的下一个节点入堆。1.3 自定义优先级三种写法一网打尽实际开发中默认的最大优先基本不够用你总要按自己的规则排序。最常见的有三种写法我一个个说。写法一重载operator如果你的元素是自己定义的结构体那最简单的方式是直接在类里重载小于号。比如我要按价格从低到高排也就是价格小的先出堆struct Order { int id; double price; // 注意想让 price 小的先出就返回 this-price other.price bool operator(const Order other) const { return price other.price; // 反着写 } }; priority_queueOrder pq; // 直接用很多初学者在这卡住为什么想要从小到大却要重载大于逻辑记住一个核心口诀priority_queue的堆顶在less语境下是operator比较结果中最大的那个。如果a b返回false也就是a不小于b那a就被认为是更大更接近堆顶。想让价格小的优先逻辑上必须让价格更小的对象在比较中表现为更大所以反着写。写法二仿函数/函数对象不改结构体定义的时候用仿函数这也是STL里最通用的方式struct CompareByTime { bool operator()(const Task a, const Task b) const { return a.deadline b.deadline; // deadline小的更紧急的先出 } }; priority_queueTask, vectorTask, CompareByTime pq;注意仿函数和operator的判断逻辑方向相反。这里容易栽跟头CompareByTime返回true表示a排在b后面a比b差正好和直觉相反。写法三lambda表达式C11之后lambda不能直接作为模板参数需要用decltype辅助auto cmp [](const Node a, const Node b) { return a.dist b.dist; // 距离小的优先 }; priority_queueNode, vectorNode, decltype(cmp) pq(cmp);priority_queue构造函数接受一个比较器实例所以你需要在构造时把cmp传进去。这块容易出错的点是lambda类型是匿名的必须用decltype推导如果漏了构造参数直接编译报错。1.4 有坑priority_queue没有迭代器不能遍历这是它和普通容器的最大区别。std::priority_queue是一个容器适配器它只暴露top()/push()/pop()这些操作不提供begin()/end()迭代器。你没法直接遍历里面的元素。我见过不少人在这踩坑调试的时候想看看现在堆里有哪些元素结果编译不通过。我的习惯做法是调试时临时复制一份再逐个pop// 调试用打印当前堆内元素 priority_queueint tmp pq; // 拷贝一份 while (!tmp.empty()) { cout tmp.top() ; tmp.pop(); }拷贝的开销一般是O(n)调试无所谓。如果数据量大可以考虑改用std::multiset之类支持遍历的容器或者直接用std::make_heapstd::push_heapstd::pop_heap自己管理一个vector——完全保留堆的特性还支持遍历。后面讲实现的时候我就带大家手搓一版那时你就明白为什么priority_queue不开放遍历了主要是为了封装语义只暴露堆的三大操作防止你破坏堆的合法性。2. 手撕priority_queue底层到底怎么组织的2.1 堆的基本结构一棵隐式二叉完全树一个二叉堆在逻辑上是一棵完全二叉树但物理上存的是连续数组。如果你有一棵完全二叉树节点下标从0开始那么对任意节点i左孩子下标2 * i 1右孩子下标2 * i 2父节点下标(i - 1) / 2这就是为什么priority_queue默认用vector做底层容器——堆的父子关系不需要存指针直接用数组下标算出来内存连续访问快。这种设计和std::list基于节点的存储完全是两个思路。以大顶堆为例核心约束只有一个任何一个父节点的值都不小于它的两个孩子。基于这个约束堆顶天然是全局最大值。插入和删除都是通过上浮和下沉操作来维持这个约束。2.2 push的核心上浮sift up往堆里插入一个新元素priority_queue做的事很简单先把元素push_back到vector尾部然后从这个新位置开始不断和父节点比较——如果比父节点大就交换位置继续往上比直到到达堆顶或者遇到比它大的父节点。这个操作的复杂度是O(log n)因为完全二叉树的高度是log n上浮最多走一条从叶子到根的路径。上浮伪代码void push_heap(vectorint v, int val) { v.push_back(val); int i v.size() - 1; while (i 0) { int parent (i - 1) / 2; if (v[parent] v[i]) { // 大顶堆孩子比父亲大就交换 swap(v[parent], v[i]); i parent; } else break; } }2.3 pop的核心下沉sift down弹出堆顶分三步走这部分面试经常考把堆顶元素v[0]和最后一个元素交换。pop_back()把最后一个元素原来的堆顶删掉。从新的堆顶开始执行下沉比较当前节点和两个孩子的最大值如果当前节点小于较大孩子就和它交换继续往下直到成为叶子或者满足堆约束。这个先交换再删除再调整的设计很巧妙它保证删除后剩下的元素依然是一个合法堆而且整个过程中数组不需要搬移只有O(log n)次交换。下沉伪代码void pop_heap(vectorint v) { swap(v[0], v.back()); v.pop_back(); int i 0, n v.size(); while (true) { int l 2 * i 1, r 2 * i 2; int largest i; if (l n v[l] v[largest]) largest l; if (r n v[r] v[largest]) largest r; if (largest i) break; swap(v[i], v[largest]); i largest; } }2.4 底层算法函数标准库其实早就帮你拆好了底层标准库其实提供了四个堆操作函数全部定义在algorithm头文件里函数作用std::make_heap把一段随机访问序列整理成堆std::push_heap把最后一个元素上浮到正确位置std::pop_heap把堆顶移到末尾并调整剩余部分std::sort_heap反复pop得到有序序列堆排序priority_queue本质上就是对这四个函数的薄封装。面试时如果让你不用priority_queue实现一个优先队列就按我上面的伪代码写如果你想让它支持遍历直接自己管理vector 这四个函数比封装好的容器灵活得多。我给一个完整的自定义优先队列实现支持遍历顶层接口和标准库几乎一样#include vector #include algorithm #include functional templatetypename T, typename Container std::vectorT, typename Compare std::lessT class MyPriorityQueue { public: void push(const T val) { c.push_back(val); std::push_heap(c.begin(), c.end(), comp); } void pop() { std::pop_heap(c.begin(), c.end(), comp); c.pop_back(); } T top() { return c.front(); } const T top() const { return c.front(); } bool empty() const { return c.empty(); } size_t size() const { return c.size(); } // 额外福利支持遍历 typename Container::iterator begin() { return c.begin(); } typename Container::iterator end() { return c.end(); } private: Container c; Compare comp; };如果面试官问priority_queue和普通vectorsort有什么区别你从两个角度回第一堆只维护最大/最小在堆顶这个弱约束而sort维护全序所以堆的插入和删除只要O(log n)第二堆不需要元素全部排好序内存里只保证父子关系遍历的结果不是有序输出。2.5 一个容易搞混的问题make_heap的建堆复杂度建堆有各种方式直接对一组无序数组执行std::make_heap时间复杂度是O(n)不是O(n log n)。很多人以为每个元素上浮一次就是O(n log n)实际上make_heap用的是从最后一个非叶子节点开始向下调整的策略每个节点的调整次数和它所在高度成反比总和算下来是O(n)。这个在面试里是小高频考点记住了。3. deque的使用双端队列到底能干什么3.1 先分清概念deque不是queue很多人头一次看到std::deque以为是queue的另一种拼法。实际上std::queue是一个容器适配器默认底层是deque但只允许从尾部进、头部出FIFO。std::deque是一个独立容器全称double-ended queue双端队列允许在头部和尾部进行O(1)的插入和删除。deque的头文件就一行#include deque。它和queue在使用上完全不是一回事。deque是vector和list的某种中间形态既支持随机访问又支持两端高效插入删除。3.2 核心操作一览#include deque dequeint dq; // 两端插入删出都是 O(1) dq.push_back(10); // 尾部插入 dq.push_front(20); // 头部插入 dq.pop_back(); // 尾部删除 dq.pop_front(); // 头部删除 // 随机访问O(1) int x dq[2]; // 不检查越界 int y dq.at(2); // 抛异常版本 // 迭代器遍历 for (auto it dq.begin(); it ! dq.end(); it) { cout *it ; }3.3 和vector、list的对比什么时候该选谁这是STL选型里最经典的问题。我先给个结论再解释为什么容器头部插入尾部插入中间插入随机访问内存布局vectorO(n)O(1)均摊O(n)O(1)连续单块listO(1)O(1)O(1)需迭代器O(n)节点离散dequeO(1)O(1)O(n)O(1)分段连续从表里看deque在头尾插入删除和随机访问两方面都占优看起来是全能型选手。那为什么实际项目里vector还是用得最多因为deque的随机访问常数因子比vector大。deque的内存不是单块连续的它需要先通过中控器定位到某个缓冲区再在缓冲区内部做偏移多一次间接寻址。CPU缓存友好性也不如vector。所以如果你只是尾部频繁插入 随机访问vector始终是首选如果你明确需要头部也要频繁插入删除 偶尔随机访问选deque。3.4 典型应用场景deque最经典的应用就是滑动窗口。比如一道很常见的算法题给定数组和窗口大小K求每个窗口内的最大值。用deque维护窗口内元素的下标保持窗口内元素单调递减这个状态头部就是当前窗口最大值vectorint maxSlidingWindow(vectorint nums, int k) { dequeint dq; // 存下标从头到尾递减 vectorint result; for (int i 0; i nums.size(); i) { // 移除超出窗口范围的头元素 if (!dq.empty() dq.front() i - k) dq.pop_front(); // 保持单调性从尾往前弹掉所有比 nums[i] 小的 while (!dq.empty() nums[dq.back()] nums[i]) dq.pop_back(); dq.push_back(i); // 窗口满 k 个元素时开始记录 if (i k - 1) result.push_back(nums[dq.front()]); } return result; }这个场景如果用vector实现移除头元素是O(n)用list虽然头部删除O(1)但随机访问和索引都不方便。deque两头都能操作写起来最自然。另外比如实现一个支持撤销/重做的操作序列、CPU任务队列、双端缓存都是deque的主场。STL里的std::stack和std::queue默认也用deque做底层因为它们的内部逻辑只需要单端插入 单端删除deque刚好两头都满足。3.5 注意deque的中间插入和erase不便宜虽然头尾插入便宜但中间插入删除是O(n)的因为要移动元素但可能比vector每个元素一次memmove要慢deque要移动半个缓冲区的元素。需要注意deque的迭代器在中间插入后可能会失效但只在插入位置附近失效不会像vector那样插入导致所有迭代器失效——这是deque一个比较微妙但实用的小细节。4. 深入deque底层分段连续加中控器4.1 为什么vector做不到头尾都快如果要我在面试里用一句话概括deque的设计目标我会说vector解决了尾部高效 随机访问list解决了任意位置高效插入删除deque想要的是兼顾两端高效和随机访问。vector的问题很明显在头部插入所有元素都要往后挪一位O(n)。list当然可以头部插入O(1)但它是离散节点不支持下标定位这种O(1)随机访问。deque的思路是把内存切成若干段连续的缓冲区chunk每段内部像vector一样连续存储再用一张中央控制器map来记录每一段的地址。这样头部要插入时看当前头部缓冲区有没有空位有就直接在头部缓冲区前面填O(1)没有就新开一块缓冲区挂到中控器上O(1)。随机访问时先通过下标算出在第几块缓冲区再算出块内的偏移两步定位O(1)。4.2 中控器map一张存指针的指针表中控器map在标准库实现里是一个指针数组每个元素指向一块缓冲区// 伪代码不同类型参数略有差异 templateclass T class deque { T** map; // 中控器指向缓冲区的指针数组 size_t map_size; // 中控器当前容量 };每块缓冲区一般是固定大小。在libstdc中缓冲区默认至少能存512 / sizeof(T)个元素最少为1个。如果T是int4字节一块缓冲区就是128个int如果T是一个很大的结构体缓冲区可能只装1个元素。为什么要有这么一层间接因为deque需要从两头扩展而vector的地址空间是单一的——头部没有空间就是没有空间。中控器允许你把新缓冲区挂到map的前面或后面等于给了头部和尾部都能生长的能力。4.3 迭代器的四个指针deque迭代器为什么是胖指针deque的迭代器不像vector的迭代器那样只是一个普通指针它是一个包含四个成员的结构体templateclass T, class Ref, class Ptr struct __deque_iterator { T* cur; // 当前指向的元素 T* first; // 当前缓冲区的开头 T* last; // 当前缓冲区的末尾哨兵 T** node; // 中控器里指向当前缓冲区的指针 };这四个字段对应的操作逻辑operator*返回*cur。operator先cur如果cur last到了当前缓冲区末尾就跳到下一块缓冲区的开头——也就是node再更新first/last/cur。operator--如果cur first到了当前缓冲区开头就跳到上一块缓冲区的末尾再cur--。随机访问operator先算总偏移再决定要不要跨缓冲区。为什么要有first和last因为跨缓冲区时你需要知道下一块缓冲区的边界在哪。你只有cur的话知道当前在哪但你不知道当前缓冲区的边界也就不知道什么时候该跨区。所以迭代器必须携带边界信息。这也是deque迭代器比vector迭代器重的根本原因——它要多维护两层边界状态。4.4 空间分配策略从头尾双向扩deque维护两个迭代器start和finish分别指向头部第一个元素和尾部最后一个元素的下一个位置。当头部空间耗尽时分配一块新缓冲区把它挂到中控器的start.node - 1位置尾部同理挂到finish.node 1位置。当中控器本身空间不够时会重新分配一块更大的map把原来的map指针搬运到新map的中间位置保证两头都有足够的空位继续挂新缓冲区。这整套机制比vector的整体搬移复杂不少但也因此换来了头尾插入都不会让已有元素移动地址的特性。我整理了一个deque的简化版中控逻辑方便你理解// 伪代码只展示大概思路 void push_back(const T val) { if (finish.cur ! finish.last - 1) { // 当前末尾缓冲区还有空位 *finish.cur val; finish.cur; } else { // 末尾缓冲区满了分配新缓冲区 T* newbuf new T[BUFSIZE]; *(finish.node 1) newbuf; // 更新 finish 迭代器指向新缓冲区 finish iterator(newbuf, newbuf, newbuf BUFSIZE, finish.node 1); *finish.cur val; finish.cur; } }4.5 和vector、list的存储成本对比任何设计都有取舍。deque的每次访问都要先通过中控器指针找缓冲区再在缓冲区内部做偏移多一次内存寻址遍历时每次跨缓冲区要判断边界。这些开销在数据量小的时候几乎无感但在千万级数据的高频循环里和vector的差距肉眼可见。维度vectordequelist存储局部性极好单块连续较好块内连续差节点跳跃缓存命中率高中低迭代器体积一个指针四个指针通常两个指针前后指针头尾插入头O(n)尾O(1)均摊头尾都O(1)任意位置O(1)随机访问常数小中不支持所以我还是那句话不是deque比vector高级而是它适合不同的场景。你如果确定不用在头部插入那vector始终是你的第一选择如果你需要的是两端都能高效deque才是对的。5. 实战避坑我用这两个容器时踩过的坑5.1 priority_queue自定义类型的比较器方向搞反这是我见过最多的坑包括我自己早年也翻过车。需求是按分数高的先出然后写了个operator里面返回a.score b.score结果跑出来是分低的先出。原因前面解释过了在priority_queue的语义下operator返回谁更小而堆顶是最大的——less表达的是堆顶是最大的那个。我的习惯是写完比较器以后先塞三四个元素进去pop一遍看一眼用实际输出验证方向不靠脑子猜。一份心思打包进注释里以后看代码的人也不会再踩一遍。5.2 deque的迭代器失效范围比vector小但别大意vector的插入会导致所有迭代器失效因为整体搬迁。deque的插入只有插入位置附近的迭代器失效而且头尾插入不会让任何迭代器失效——这个特性在实现窗口滑动类算法时很关键。但注意deque的中间插入导致迭代器失效的范围虽然小不是没有。如果你在一个deque中间插入了元素持有指向插入点之后元素的迭代器还是可能失效。所以安全做法是需要稳定引用某个元素时存下标而不是存迭代器或者干脆用vector。5.3 priority_queue不能改堆内元素小心脏堆有时候你会想堆里的任务优先级变了我能不能直接改堆顶答案是不行——top()返回的是const T不能改。就算强行用const_cast改了堆的约束也被破坏了后续操作的复杂度会恶化行为完全不可预期。正确改法是先pop再push新的值。C17里可以用std::set配合自定义排序实现可修改优先的队列——如果确实需要动态修改任务优先级就别死磕priority_queue了。5.4 初始化方式的区别deque、vector、list都支持列表初始化priority_queue却不支持priority_queueint pq {1,2,3}。如果想用已有数组初始化可以这样vectorint data {3, 1, 4, 1, 5}; priority_queueint, vectorint pq(data.begin(), data.end()); // 等效于逐个 push复杂度 O(n) 而不是 O(n log n)因为用了建堆注意这里用范围构造函数建堆是O(n)不是O(n log n)性能表现和逐项push有本质区别。5.5 deque的operator[]和at的行为差异operator[]不检查越界越界是未定义行为程序可能崩得很抽象。at()会检查越界抛std::out_of_range。调试阶段建议先用at()等确定逻辑没问题再换成[]。这个原则对所有STL容器通用但deque因为底层分块的缘故越界更容易造成难查的内存错误。6. 面试追问这两个容器还有哪些值得说的点6.1 priority_queue的底层容器可以换成deque吗可以。模板第二个参数允许传dequeT甚至list——但list不行因为堆操作需要随机访问list不满足RandomAccessIterator的要求编译直接报错。deque满足随机访问可以作为底层容器。实际没人这么干因为vector的连续内存对堆算法更友好deque多一次跳转毫无必要。但这个问题的存在提醒我们priority_queue并不依赖vector它只依赖随机访问迭代器这个抽象能力。6.2 为什么priority_queue不给迭代器标准库设计者很克制。暴露迭代器意味着用户可以随意修改堆内任意元素一旦修改破坏了堆性质后续所有操作都不可信。宁可提供完整的底层算法make_heap/push_heap/pop_heap把灵活性交给用户自己掌控也不让封装好的容器变得脆弱。这种宁可少给不给坏的接口设计思路在STL里反复出现。6.3 deque的容器适配器std::queue和std::stack的默认底层容器都是deque。为什么因为它们各自只需要一端插入另一端删除或单端插入删除deque都支持还能提供O(1)复杂度。如果非要用vector实现queue头部删除是O(n)性能崩了list的缓存不友好。deque是两者的折中默认选它非常合理。6.4 一个扩展思路deque和priority_queue组合使用实际项目中我喜欢把两者配合用deque做请求的原始到达顺序缓冲区用priority_queue做按优先级处理的执行队列。请求来了先进deque后台线程按窗口批量取出来压入priority_queue执行器再按优先级处理。这种组合几乎把所有排队场景都覆盖了——既要保序又要分优先级的时候特别顺手。我自己做C开发这些年对priority_queue和deque的体会是绝大多数人只把它们当API字典里的两个词条用到才查一下其实底层那点东西搞明白了用起来完全是两种感觉。比如你知道priority_queue是上浮下沉那套逻辑遇到想改堆顶元素这种需求第一个念头就不会是改堆顶而是pop再push——因为你清楚堆的结构敏感。知道deque是中控器加缓冲区你也就不会在某个大循环里用dq[i]去高频访问因为你知道它比vector多一跳。如果这篇能让你下次面试时淡淡地说出priority_queue的本质就是vector加二叉堆deque的本质就是中控器加分段连续缓冲我就算没白写了。