C STL stack、queue 与 priority_queue 底层剖析容器适配器的设计哲学这篇不聊pushpop怎么用。如果你还在背接口先去看 cppreference。这里只干三件事容器适配器到底是什么设计模式为什么 STL 不把 stack 和 queue 算进容器deque 的底层分段连续结构——为什么它天生是给 stack 和 queue 当爹的料priority_queue 的堆维护到底在干什么make_heap/push_heap/pop_heap的复杂度怎么保证一、容器适配器这不是容器是包装纸STL 的容器家族分三类序列式容器vector、list、deque——自己管内存自己管数据关联式容器map、set、unordered_map——自己管键值关系容器适配器stack、queue、priority_queue——不自己管任何事适配器的核心思想来自设计模式里的Adapter Pattern把一个类的接口转换成客户希望的另一个接口。stack 和 queue 本质上就是对某个底层容器的接口做了一层裁剪和重命名。templateclassT,classContainerdequeTclassstack{Container _c;public:voidpush(constTx){_c.push_back(x);}voidpop(){_c.pop_back();}Ttop(){return_c.back();}// ...};看到没有stack 自己没有内存没有节点什么都没有。它只有一个_c所有操作都转发给_c。这就是为什么 STL 不把 stack 和 queue 划入容器——它们没有独立的存储语义只是容器的一种使用方式。1.1 为什么这种设计是合理的假设 STL 把 stack 做成独立容器底层用链表实现。那你会得到什么一套和 vector/list/deque 完全不同的内存管理逻辑一堆重复的 bug内存泄漏、迭代器失效无法复用已有的优化比如 vector 的缓存友好性适配器模式把栈的抽象语义和底层存储解耦。你要栈语义行随便挑一个底层容器只要它支持push_back/pop_back就行。想缓存友好选 vector想稳定迭代器选 list想两头通吃选 deque。这是典型的组合优于继承——stack has-a Container而不是 stack is-a Container。1.2 底层容器的选择策略底层容器stack 适合queue 适合原因vector适合不适合vector 没有pop_frontqueue 需要头删list适合适合双向链表头删尾插都是 O(1)但缓存极差deque最适合最适合分段连续头尾操作都 O(1)缓存比 list 好PPT 里提到 stack 可以用 vector 模拟queue 可以用 list 模拟。这没问题但默认用 deque 是经过深思熟虑的。下一节拆 deque 的底。二、deque分段连续的障眼法deque 全称 double-ended queue双端队列。它的设计目标很直接头尾插入删除都是 O(1)同时保持比 list 更好的缓存友好性。2.1 内存布局不是数组是数组的数组deque 的底层不是一大块连续内存而是一组固定大小的小数组buffer再用一个**中控数组map**来索引这些小数组。map中控数组存储各 buffer 的指针 ------------------------ | ptr| ptr| ptr| ptr| ptr| ptr| ------------------------ | | | v v v ----- ----- ----- |a b c| |d e f| |g h i| -- 每个 buffer 固定大小如 512 个元素 ----- ----- ----- ^ ^ begin end中控数组本身也是动态的满了就扩容——但扩容成本很低因为它只存指针不存元素。搬移的是指针数组不是元素本身。2.2 迭代器的负担deque 要维持随机访问的假象迭代器设计比 vector 复杂得多。一个 deque 迭代器通常要存四个东西struct_Deque_iterator{T*_M_cur;// 指向当前元素T*_M_first;// 指向当前 buffer 的首元素T*_M_last;// 指向当前 buffer 的尾后位置T**_M_node;// 指向中控数组中的当前 buffer 指针};四个指针32 字节64 位系统。对比 vector 迭代器就是一个T*8 字节差距巨大。为什么需要这么多因为 deque 的操作要处理跨 buffer 边界Selfoperator(){_M_cur;if(_M_cur_M_last){// 走到当前 buffer 末尾了_M_node;// 跳到中控数组的下一个指针_M_first*_M_node;_M_last_M_firstbuffer_size;_M_cur_M_first;}return*this;}每次都要做一次边界检查。遍历 deque 时这个检查的频率是每 512 个元素一次假设 buffer 大小为 512。听起来不多但和 vector 的直接指针相比分支预测失败和额外内存访问的代价是实实在在的。2.3 deque 的致命缺陷遍历慢PPT 里总结得很到位deque 不适合遍历。原因有三迭代器跨 buffer 的边界检查每次接近 buffer 末尾都要判断分支预测失败率高缓存不连续虽然单个 buffer 内部连续但 buffer 之间散落在堆上。跳转到下一个 buffer 时大概率缓存未命中预取失效CPU 的硬件预取器对连续内存效果好对 deque 这种连续一小段、跳一大段的模式完全抓瞎实测数据遍历 100 万个 intvector 通常比 deque 快 20%-50%。如果元素类型更大差距会更明显。2.4 那为什么 stack 和 queue 默认用 deque因为 stack 和 queue不需要遍历。它们的操作只有stackpush_back尾插、pop_back尾删、back访问尾部queuepush_back尾插、pop_front头删、front/back访问头尾deque 的弱点遍历慢被完美回避而它的 strengths 全部用上头尾操作都是 O(1)比 vector 的头删 O(N) 强太多扩容不搬元素中控数组扩容只搬指针元素留在原地。vector 扩容要搬全部元素缓存比 list 好单个 buffer 内部连续空间利用率远高于 list 的 24 字节节点PPT 里的原话是结合了 deque 的优点而完美的避开了其缺陷。确实如此。三、priority_queue堆算法的自动化外壳priority_queue 也是容器适配器但它的底层逻辑比 stack/queue 复杂——它不只是转发接口还要在每次插入和删除后维护堆结构。3.1 默认是大堆priority_queueintpq;// 默认大堆top() 返回最大元素底层容器默认是 vector。为什么用 vector因为堆在逻辑上是完全二叉树物理上最好用数组存储——父节点 i 的左右孩子是 2i1 和 2i2。vector 的连续内存天然适合这个映射。3.2 堆维护的三个算法STL 提供了三个堆算法priority_queue 内部自动调用make_heap把一段无序数据变成堆make_heap(first,last);// O(N)时间复杂度 O(N) 不是 O(N log N)。因为它用自下而上的堆化bottom-up heapify从最后一个非叶子节点开始逐个向下调整。叶子节点不需要调整所以实际工作量是 N/2 N/4 N/8 … ≈ N。push_heap在堆尾插入元素后向上调整push_heap(first,last);// O(log N)假设堆已经有 N 个元素vector 的push_back把新元素放到位置 N。然后push_heap让这个元素和父节点比较如果更大就交换一路向上冒泡到根。pop_heap把堆顶移到末尾然后向下调整pop_heap(first,last);// O(log N)这个操作的名字很迷惑——它不是真的弹出元素。它做的是把堆顶first和最后一个元素last-1交换对[first, last-1)这段做向下调整恢复堆结构返回后原来的堆顶现在在last-1可以被pop_back()真正移除priority_queue 的pop()内部就是pop_heappop_back。3.3 为什么priority_queue的迭代器被封死了priority_queue不提供迭代器。不是因为实现不了而是语义上不允许。堆的结构是局部有序——只保证父节点大于或小于子节点不保证兄弟节点之间有序。如果你拿到迭代器遍历一遍看到的不是有序序列而是让人困惑的半乱序状态。STL 干脆不提供迭代器避免用户误用。如果你需要有序遍历应该先把元素倒到 vector 里再sort而不是用 priority_queue 的迭代器虽然你拿不到。3.4 自定义比较器大堆变小堆// 小堆top() 返回最小元素priority_queueint,vectorint,greaterintmin_pq;greaterint是一个函数对象functor内部重载了operator()templateclassTstructgreater{booloperator()(constTa,constTb)const{returnab;}};堆算法在比较时用comp(a, b)判断a 的优先级是否低于 b。greater让大值被视为低优先级于是小值上浮到堆顶。对于自定义类型你需要提供operator用于大堆或operator用于小堆。如果两个都提供可以灵活切换。四、从底层看经典问题4.1 最小栈双栈法的空间开销PPT 里的最小栈用两个 stack 实现_elem存数据_min存当前最小值。voidpush(intx){_elem.push(x);if(_min.empty()||x_min.top())_min.push(x);}voidpop(){if(_min.top()_elem.top())_min.pop();_elem.pop();}空间复杂度不是严格的 O(N)。当输入序列单调递减时_min和_elem一样大O(N)。当输入单调递增时_min只存一个元素O(1)。平均情况下接近 O(N)。一个优化思路_min里不存重复值存值, 计数对。但 PPT 里的版本没有做这个优化教学代码追求简洁。4.2 用两个栈实现队列经典面试题。核心思想入队栈只负责push出队栈只负责pop和front当出队栈为空时把入队栈的所有元素倒到出队栈均摊复杂度 O(1)。最坏情况下一次pop要搬 N 个元素但每个元素最多被搬两次入队栈 → 出队栈 → 弹出所以均摊下来是 O(1)。4.3 逆波兰表达式求值栈的经典应用。PPT 里的代码有个细节值得注意intrights.top();s.pop();intlefts.top();s.pop();s.push(leftright);减法和除法不是交换律的所以必须先弹出右操作数再弹出左操作数。如果顺序反了5 3 -会变成3 - 5 -2而不是正确的2。五、性能实测vector vs list vs deque 当 stack虽然理论上三种容器都能当 stack 的底层但实际性能差距明显。写一个简单测试连续 push 100 万个 int然后连续 pop 100 万个 int。// 测试框架示意templateclassContainervoidbench_stack(){stackint,Containers;for(inti0;i1e6;i)s.push(i);while(!s.empty())s.pop();}典型结果gcc -O2x86_64底层容器push 阶段pop 阶段总时间vector快快最快deque接近 vector接近 vector接近 vectorlist慢 3-5x慢 3-5x明显慢vector 和 deque 在只操作尾部时性能接近因为 deque 的尾部操作不需要跨 buffer。list 慢是因为每次new/delete节点都有堆分配开销。但注意如果测试包含大量交替 push/popdeque 和 vector 的差距会拉大——vector 在临界容量时可能触发扩容deque 的中控数组扩容只搬指针。六、设计思想的延伸6.1 适配器模式的通用性stack/queue/priority_queue 都是适配器但适配的维度不同stack/queue接口适配——裁剪底层容器的接口只暴露 LIFO/FIFO 语义priority_queue行为适配——在转发接口的同时附加堆维护的副作用这种分层设计让 STL 的代码复用率达到极致。stack 的源代码只有几十行因为它把所有工作都委托给了底层容器。6.2 不提供迭代器是一种设计决策stack、queue、priority_queue 都不提供迭代器。这不是偷懒而是接口隔离原则——只暴露用户需要的操作隐藏可能破坏数据结构不变量的操作。如果 stack 提供了迭代器用户就能随便修改中间元素破坏栈的不变量。priority_queue 如果提供迭代器用户可能误以为遍历结果是有序的。6.3 deque 的启示没有银弹deque 试图兼顾 vector 的缓存友好和 list 的头尾操作效率结果得到了一个两头都好、中间拉胯的结构。遍历慢、迭代器臃肿、实现复杂——这些代价在需要线性遍历的场景下无法接受。这告诉我们数据结构的设计是权衡trade-off。deque 在 stack/queue 的场景下是完美选择因为它回避了自己的弱点。但如果你在写一个需要频繁遍历的队列比如滑动窗口deque 可能不是最优解。七、总结搞懂 stack、queue、priority_queue 的底层核心就这几条它们是适配器不是容器。所有操作都委托给底层容器自己没有存储语义。默认底层是 deque 不是偶然。deque 的头尾 O(1) 分段连续完美匹配 stack/queue 的操作模式同时回避了遍历慢的缺陷。priority_queue 的堆维护是自动的。push_heap/pop_heap/make_heap三个算法撑起了所有操作复杂度分别是 O(log N) / O(log N) / O(N)。不提供迭代器是刻意的设计。避免用户破坏数据结构的不变量避免误用。最后留一个思考题如果你要设计一个中位数队列——支持 push、pop、以及 O(1) 查询当前队列中位数——你会怎么组合 STL 的容器和适配器提示两个 priority_queue。