从“会用”到“模拟实现”对一个C开发者来说差的并不是代码量而是对容器设计意图的理解。就拿STL里的std::stack、std::queue、std::priority_queue来说很多人天天用知道push、pop、top怎么调用但一旦被问到“为什么stack默认容器是deque而不是vector”“priority_queue为什么不支持遍历”“为什么用仿函数而不是函数指针”这些问题就很容易卡壳。这篇博文我打算直接带大家手写这三个容器适配器通过模拟实现把底层机制彻底摊开。这里的STL指的是C标准模板库和3D打印的STL文件格式没有关系。写模拟实现的价值不在于让你去造一个比标准库更好的轮子而在于让你站在库设计者的角度重新审视问题。当你亲手写出templateclass T, class Container std::dequeT这个类模板骨架时你才会明白为什么适配器模式在STL里这么重要当你自己实现priority_queue的堆调整时你才会真正理解push_heap和pop_heap为什么长得那样。所以这篇文章非常适合正在学习C、准备面试、或者对STL源码有好奇心的朋友阅读过程中我建议你打开编译器跟着敲一遍很多疑问会在键盘上自动消失。1. 为什么说“会用”不等于“懂”三个容器的真实身份1.1 容器 vs 容器适配器要模拟实现第一件事是把它们的身份搞清楚。std::vector、std::list、std::deque是真正的容器它们自己管理内存、自己存数据提供迭代器、提供随机访问能力。而std::stack、std::queue、std::priority_queue这三个家伙在STL的分类里有一个专门的称呼容器适配器。容器适配器的意思是它本身不管理存储而是在另一个容器的基础上对外提供一套受限的、符合特定语义的接口。std::stack内部持有的是一个std::deque但它对外只暴露push、pop、top让你只能从尾部操作从而把deque变成一个“后进先出”的结构。std::queue同理它内部也可以是一个deque但只允许尾部进、头部出变成“先进先出”。std::priority_queue则是在std::vector的基础上通过堆算法维护一个“最大元素永远在堆顶”的结构。如果你在某个代码里写下std::stackint然后试图遍历它编译器会直接报错因为stack压根没有提供迭代器接口。这不是缺陷而是设计上故意的“功能阉割”。容器适配器的存在意义就是不让你有机会破坏它规定的访问规则。这种设计哲学在真实工程里到处都是不是所有数据都该被随意遍历和修改有时候对外暴露的东西越少出错的概率就越低。1.2 为什么默认底层是deque不是vector这是面试高频题也是理解适配器设计的钥匙。std::stack和std::queue的第二个模板参数默认值是std::dequeT但很多人会疑惑std::vector不也能完成尾部插入和删除吗为什么不用vector对于std::stack你确实可以把底层容器换成std::vector代码也能跑。但std::queue是个明显的分界线queue需要“头部删除”用std::vector做头部删除是O(n)级别的操作因为要搬移所有元素。std::deque的设计目标就是“头尾插入删除都是O(1)”所以queue天然应该默认基于deque。那stack为什么也不选vector而选deque这就要细看deque的内存布局了。deque内部是一段一段的连续空间用中控器(map)串起来。头部插入时如果当前缓冲区没有位置就在前面新增一段缓冲区尾部插入同理。它虽然是分段连续的但operator[]仍然能做到O(1)的随机访问只不过常数比vector大一点需要一次双层的指针索引计算。对于stack来说它只需要在尾部操作deque的尾部操作和vector几乎一样快而且deque的扩容策略比vector更温和。vector扩容是要拷贝/移动所有旧元素到新内存的deque的段式结构让它扩容时不需要搬移已有元素只是再分配一小段缓冲区。所以单论push/pop性能deque在大多数情况下是优于vector的。这个结论听起来反直觉但实测下来在尾部高频压栈弹栈的场景里deque确实稳。std::priority_queue为什么不选deque因为priority_queue要频繁进行随机位置访问来实现堆调整deque虽然支持operator[]但常数比vector大而且堆调整每次都要做大量的“读元素、比较、交换”操作用deque只会白白增加开销。vector是连续内存缓存友好度高operator[]是最快的所以priority_queue的默认底层容器是std::vectorT。这个默认值的选择不是随意的背后是操作模式与容器特性的匹配。1.3 三个适配器的行为差异三个适配器虽然结构相似但对外语义完全不同。std::stack是后进先出典型场景是函数调用栈、括号匹配、撤销操作。std::queue是先进先出典型场景是消息队列、任务调度、缓冲区排队。std::priority_queue是“每次能拿到当前集合里最大或最小的元素”典型场景是任务优先级调度、Top-K问题、Dijkstra算法的优先队列优化。它们都没有迭代器都只提供受限接口但受限的方式各不相同。stack只看得到栈顶queue只看得到队头priority_queue只看得到堆顶。这种设计让你在使用时根本不需要关心内部实现只要按语义调用就行。但反过来说如果你不理解内部实现一旦遇到性能问题、自定义类型比较出错、迭代器相关的问题就会很被动。模拟实现的目的就是把这一层窗户纸捅破。2. 整体设计先定接口再谈实现2.1 类模板的三个参数模拟实现的第一步是把类模板的骨架写出来。标准库的设计是这样的std::stackT, Container std::dequeT两个模板参数第二个是底层容器类型。std::queueT, Container std::dequeT同上。std::priority_queueT, Container std::vectorT, Compare std::lessT三个模板参数第三个是仿函数比较器。注意到没有这里并没有“自定义allocator”参数其实有标准库的容器都支持分配器但为了教学简化我这里的模拟实现不展开allocator只看核心逻辑。你掌握主干之后再看标准库源码会轻松很多。为什么用容器类型作为模板参数这是适配器模式最精彩的地方。适配器不关心底层容器是谁只要它满足某些接口要求就行了。对于stack要求底层容器支持push_back、pop_back、back、empty、size。对于queue要求支持push_back、pop_front、front、back、empty、size。这意味着你甚至可以传一个自己实现的容器进去只要满足接口stack的功能就是完整的。这种“鸭子类型”的约束方式在C模板世界里非常常见。2.2 接口设计应保持一致在开始写代码之前我们先明确要实现的接口。没有接口设计就去写实现很容易东一榔头西一棒槌。我列一下我的模拟实现要支持的方法接口stackqueuepriority_queueempty()检查栈空检查队空检查堆空size()返回大小返回大小返回大小top()栈顶引用队头引用堆顶引用push()尾部插入尾部插入尾部插入后堆调整pop()尾部删除头部删除堆顶删除后堆调整emplace()就地构造就地构造就地构造后堆调整swap()交换底层容器交换底层容器交换底层容器我建议你在实现时模仿标准库的接口命名不要自己发明新名字。这样好处很多一是代码阅读的人一看就懂二是你以后看标准库文档、用标准库的时候没有心智负担三是面试官问起来也方便对比。2.3 类模板骨架怎么写这里我给出stack的类模板骨架queue和priority_queue类似namespace my_stl { template class T, class Container std::dequeT class stack { public: using value_type typename Container::value_type; using container_type Container; using size_type typename Container::size_type; using reference typename Container::reference; using const_reference typename Container::const_reference; stack() default; explicit stack(const Container cont) : c(cont) {} bool empty() const { return c.empty(); } size_type size() const { return c.size(); } reference top() { return c.back(); } const_reference top() const { return c.back(); } void push(const value_type value) { c.push_back(value); } void push(value_type value) { c.push_back(std::move(value)); } template class... Args void emplace(Args... args) { c.emplace_back(std::forwardArgs(args)...); } void pop() { c.pop_back(); } void swap(stack other) noexcept(noexcept(c.swap(other.c))) { c.swap(other.c); } protected: Container c; }; }有几个点是刻意这样写的。第一protected保护成员Container c这样派生类可以访问到底层容器但外部调用者碰不到。第二类型别名全部用using而不是typedef这是现代C的风格。第三push同时提供左值引用和右值引用重载这样插入临时对象时能触发移动语义减少拷贝。第四top返回的是back的引用因为stack的“栈顶”就是底层容器的“尾部”。3. 从零手写Stack和Queue的模拟实现3.1 Stack的完整实现与验证Stack的实现非常简单到这一步你会感觉它像一个“壳”。确实容器适配器的本质就是壳它把所有操作都转发给底层容器。但这种转发不是无脑的它是在语法层面把底层容器的能力裁剪到只剩stack语义。Stack的完整实现我已经在2.3中给出了接下来写一个简单的测试用例验证它#include iostream #include deque #include vector int main() { my_stl::stackint stk; stk.push(1); stk.push(2); stk.push(3); std::cout size stk.size() \n; // 3 std::cout top stk.top() \n; // 3 stk.pop(); std::cout top after pop stk.top() \n; // 2 // 使用vector作为底层容器 my_stl::stackint, std::vectorint stk2; stk2.push(10); stk2.emplace(20); std::cout stk2.top stk2.top() \n; // 20 return 0; }你可以试试把Container换成std::list代码一样能跑。只要底层容器支持push_back、pop_back、backstack就能工作。这种可替换性正是适配器模式的核心价值。不过有一点要注意如果你传一个std::forward_list作为底层容器编译会报错因为forward_list没有push_back和back。这正好验证了约束的存在——适配器对底层容器的接口是有要求的只是这种要求在C里通过编译错误来体现而不是通过文档里的继承关系来体现。3.2 Queue的完整实现与验证Queue比Stack多了一个变化它需要pop_front。这意味着底层容器的选择范围更窄了。std::vector没有pop_front你不能用vector做queue的底层容器。但std::list和std::deque都可以。namespace my_stl { template class T, class Container std::dequeT class queue { public: using value_type typename Container::value_type; using container_type Container; using size_type typename Container::size_type; using reference typename Container::reference; using const_reference typename Container::const_reference; queue() default; explicit queue(const Container cont) : c(cont) {} bool empty() const { return c.empty(); } size_type size() const { return c.size(); } reference front() { return c.front(); } const_reference front() const { return c.front(); } reference back() { return c.back(); } const_reference back() const { return c.back(); } void push(const value_type value) { c.push_back(value); } void push(value_type value) { c.push_back(std::move(value)); } template class... Args void emplace(Args... args) { c.emplace_back(std::forwardArgs(args)...); } void pop() { c.pop_front(); } void swap(queue other) noexcept(noexcept(c.swap(other.c))) { c.swap(other.c); } protected: Container c; }; }这里的核心点是front和back都返回引用但pop只从头部弹。如果你尝试用my_stl::queueint, std::vectorint编译器会告诉你vector没有pop_front成员函数。这不是坏事它让你被迫思考“哪些容器适合做queue的底层”同时也验证了STL默认选择deque的合理性。测试一下#include iostream #include deque #include list int main() { my_stl::queueint q; q.push(1); q.push(2); q.push(3); std::cout front q.front() \n; // 1 std::cout back q.back() \n; // 3 q.pop(); std::cout front after pop q.front() \n; // 2 my_stl::queueint, std::listint q2; q2.push(100); q2.push(200); q2.pop(); std::cout q2.front q2.front() \n; // 200 return 0; }到这里你已经实现了两个容器适配器。你会发现它们的实现难度远低于vector和deque本身因为它们没有内存管理、没有迭代器实现、没有复杂的数据结构只是把现有的容器包了一层壳。但请不要小看这层壳——它定义了行为边界是设计意图的体现。4. 真正的重头戏Priority_Queue的模拟实现4.1 三个成员容器、比较器、堆算法Priority_queue的模拟实现难度主要体现在两个地方一是堆算法的实现二是比较器的使用方式。它内部有三个关键成员底层容器c、比较器comp、以及一组堆调整算法。很多人第一次写priority_queue的时候会陷入一个误区试图自己去实现heap数据结构。其实不用堆本质上就是一个数组这里就是vector通过下标关系表达父子关系。对于下标为i的元素它的左孩子是2*i1右孩子是2*i2父节点是(i-1)/2。这些下标关系是理解堆调整的基础。堆调整分两种向上调整和向下调整。插入元素时先把元素放到尾部然后向上调整让它“浮”到合适的位置。弹出堆顶时把堆顶和最后一个元素交换再弹出最后一个元素然后从堆顶向下调整让新的堆顶“沉”到合适的位置。4.2 向上调整与向下调整的细节先写两个辅助函数。向上调整adjust_up从某个孩子节点开始不断和父节点比较。如果父节点“小于”孩子节点就交换然后继续往上走。这里的关键是“小于”这个语义它取决于比较器comp。void adjust_up(size_type child) { size_type parent (child - 1) / 2; while (child 0) { if (comp(c[parent], c[child])) { std::swap(c[parent], c[child]); child parent; parent (child - 1) / 2; } else { break; } } }向下调整adjust_down从某个父节点开始先找到孩子节点然后找出左右孩子中较大的一个如果父节点“小于”较大的孩子就交换然后继续往下走。void adjust_down(size_type parent) { size_type child parent * 2 1; while (child c.size()) { // 选出左右孩子中较大的一个 if (child 1 c.size() comp(c[child], c[child 1])) { child; } if (comp(c[parent], c[child])) { std::swap(c[parent], c[child]); parent child; child parent * 2 1; } else { break; } } }如果你之前没接触过堆这里最容易出错的是child 1 c.size()这个边界条件。当左孩子已经存在但右孩子不存在时不能去访问child1否则就是越界。很多新手写的堆排序列越界基本都是栽在这个地方。这两段代码配合comp的语义就是priority_queue的灵魂。注意到comp在堆调整里出现了两次一次是比较父和子是否要交换一次是比较两个子节点谁更大。把比较逻辑抽出来整个堆调整算法就不关心元素类型了。这正是泛型编程的威力算法与数据类型解耦。4.3 priority_queue的完整实现下面是完整的priority_queue模拟实现。我把make_heap、adjust_up、adjust_down都封装成私有成员函数并实现了标准库那几个关键接口。namespace my_stl { template class T, class Container std::vectorT, class Compare std::lessT class priority_queue { public: using value_type typename Container::value_type; using container_type Container; using size_type typename Container::size_type; using reference typename Container::reference; using const_reference typename Container::const_reference; priority_queue() default; explicit priority_queue(const Compare compare) : comp(compare) {} priority_queue(const Compare compare, Container cont) : comp(compare), c(std::move(cont)) { make_heap(); } template class InputIt priority_queue(InputIt first, InputIt last, const Compare compare Compare()) : comp(compare), c(first, last) { make_heap(); } bool empty() const { return c.empty(); } size_type size() const { return c.size(); } const_reference top() const { return c.front(); } void push(const value_type value) { c.push_back(value); adjust_up(c.size() - 1); } void push(value_type value) { c.push_back(std::move(value)); adjust_up(c.size() - 1); } template class... Args void emplace(Args... args) { c.emplace_back(std::forwardArgs(args)...); adjust_up(c.size() - 1); } void pop() { if (empty()) return; std::swap(c.front(), c.back()); c.pop_back(); if (!empty()) adjust_down(0); } void swap(priority_queue other) noexcept( noexcept(c.swap(other.c)) noexcept(std::swap(comp, other.comp))) { c.swap(other.c); std::swap(comp, other.comp); } protected: void make_heap() { if (c.size() 2) return; // 从最后一个非叶子节点开始逐个向下调整 for (size_type i (c.size() - 1 - 1) / 2; i 0; --i) { adjust_down(i); } adjust_down(0); } void adjust_up(size_type child) { size_type parent (child - 1) / 2; while (child 0) { if (comp(c[parent], c[child])) { std::swap(c[parent], c[child]); child parent; parent (child - 1) / 2; } else { break; } } } void adjust_down(size_type parent) { size_type child parent * 2 1; while (child c.size()) { if (child 1 c.size() comp(c[child], c[child 1])) { child; } if (comp(c[parent], c[child])) { std::swap(c[parent], c[child]); parent child; child parent * 2 1; } else { break; } } } protected: Compare comp; Container c; }; }这里有几个设计细节值得展开。第一个是top()为什么返回c.front()而不是像vector那样支持随机访问。堆顶就是最大元素它总是被放在数组的第一个位置。如果你返回了reference而不是const_reference外部就可以通过pq.top() 100来修改堆顶元素但这会破坏堆结构。标准库的priority_queue::top()返回的是const_reference防止外部修改。所以我的实现也返回const_reference这是一个很重要的安全设计。第二个是pop()操作。标准实现是先std::pop_heap再把元素pop_back出去我这里直接手写了交换和向下调整。为什么pop之后要做向下调整因为交换后数组里除了堆顶其余部分仍然满足堆序只有堆顶可能不满足。这种情况下单独对堆顶做一次向下调整就能恢复整个堆序。第三个是make_heap()的起始下标。最后一个非叶子节点的下标是(size-2)/2也就是(size-1-1)/2。从它开始往前逐个向下调整就能把任意数组整理成合法的堆。我举个例子数组[3, 1, 4, 1, 5, 9, 2, 6]size为8从下标3开始调整然后2、1、0最后整个数组就满足最大堆性质。这个过程和排序算法里的建堆逻辑一致理解了它后面看std::make_heap源码会轻松不少。4.4 为什么默认是最大堆less的堆语义这是priority_queue里最反直觉的一个点Compare的默认值是std::lessT字面意思是“小于”但priority_queue弹出的却是最大值。很多初学者第一次看到这个默认参数时都会懵一下。要解释清楚这个问题得回到堆调整里那句核心判断if (comp(c[parent], c[child]))。当comp(c[parent], c[child])返回true时说明父节点“小于”孩子节点此时就交换它们。换句话说comp表达的是“parent 是否应该排在 child 前面”的意思。如果comp是std::less那么parent child时交换结果就是父节点永远不小于子节点也就是大根堆。所以请记住这个结论std::lessT对应的堆是大根堆std::greaterT对应的是小根堆。你如果需要小根堆把第三个模板参数显式传成std::greaterT即可// 小根堆 my_stl::priority_queueint, std::vectorint, std::greaterint min_heap; min_heap.push(10); min_heap.push(5); min_heap.push(20); std::cout min_heap.top() \n; // 输出 5这个细节值得你在面试时主动讲出来因为这能证明你不是背接口而是真的理解比较器的语义。5. 常见问题与排查技巧实录5.1 模板实现不能放.cpp文件这是所有C模板学习者都会踩的第一个坑。如果你把stack、queue、priority_queue的声明放在.h文件里把实现放在.cpp文件里然后在另一个.cpp文件里使用它们链接器会报“未定义引用”的错误。原因在于模板不是普通的函数或类它不是一个具体的实体而是一个“图纸”。编译器在使用模板时需要用模板参数去“实例化”出真正的类。而实例化要求编译器能看到完整的模板定义。如果把实现藏在.cpp里使用端只看到了声明编译器无法实例化于是只能留一个符号让链接器去找但链接器同样看不到实现于是报错。解决方式有几种。最简单的是把所有模板代码放在同一个头文件里这也是标准库的做法。另一种是显式实例化在实现文件里写template class my_stl::stackint;但这会严重限制模板的通用性每用一个新的类型参数就要声明一次非常麻烦。我建议你习惯第一种方式模板实现放头文件不要分离编译。5.2 自定义类型放入priority_queue报错std::lessT默认使用operator来比较两个对象。如果你定义了一个类型struct Task { int priority; std::string name; };然后直接塞进priority_queueTask编译器会报错提示no match for operator。这是自定义类型进入排序型容器最常见的坑。解决方案有两种一是在Task里重载operator二是给priority_queue传入自定义仿函数。我强烈推荐第二种因为有时候同一个类型在不同场景下需要不同的排序规则把比较策略外置更灵活。比如struct Task { int priority; std::string name; }; struct TaskCmp { bool operator()(const Task a, const Task b) const { // 注意这里写的是 a 是否应该排在 b 后面 return a.priority b.priority; } }; my_stl::priority_queueTask, std::vectorTask, TaskCmp pq;这里要特别注意仿函数的语义operator()返回true时表示a应该排在b的后面。放到堆里就是a的优先级比b低时才会交换。我见过不少同学在自定义仿函数时把比较方向搞反结果得到完全相反的优先级顺序。建议你写完后先跑一个push(高优先级任务)push(低优先级任务)top()的小测试确认堆顶元素和预期一致。5.3 空容器调用top或pop调用空stack的top、空queue的front、空priority_queue的top都是未定义行为。标准库根本不会帮你检查你在模拟实现里也可以不检查。但实际工程里这种未定义行为是最难排查的它可能不崩溃可能返回一个垃圾值也可能在你发布后某个诡异的输入下突然崩溃。我的习惯是在关键接口处加断言。比如模拟实现里可以加上assert(!c.empty())然后通过NDEBUG宏在release版本里关掉。如果你想把防御做扎实可以抛一个std::out_of_range异常但要注意这会让top变成有代价的调用和标准库的零开销原则有冲突。实际项目中我建议调用方做好empty()检查就像pop之前先看empty()一样。这个习惯能帮你省掉无数崩溃排查时间。5.4 底层容器选型不当导致性能问题使用这三个适配器时你完全可以显式指定底层容器。Stack可以用std::vectorQueue可以用std::list甚至你还可以用一个自研的容器。但不同的选型会导致天差地别的性能。Stack如果数据量巨大用std::deque是均衡的选择但如果你的元素是小对象且栈的最大深度已知用std::vector提前reserve掉内存性能会更稳定。Queue的大数据量场景std::list每个节点有额外的指针开销而且节点在内存中不连续缓存命中率低std::deque虽然也是分段连续但整体缓存友好度远好于list。所以默认给queue用deque是经验主义的胜利。Priority_queue只有一种合理选择连续内存容器。堆调整最核心的瓶颈是随机访问和交换std::vector是唯一在随机访问上做到极致的容器。如果你非要用std::deque作为priority_queue的底层容器你会发现代码能跑但性能会明显下降因为deque的operator[]比vector慢。这也是为什么标准的priority_queue干脆默认vector不给使用者其他选项。5.5 面试必问为什么容器适配器没有迭代器这个问题比看起来深。没有迭代器本质上是为了保证结构不变性。Stack如果给你一个迭代器你就能遍历整个栈还能通过迭代器修改中间的元素这会让“后进先出”的语义荡然无存。Queue和priority_queue同理。如果通过迭代器访问底层数组那priority_queue的堆序性质随时可能被破坏整个数据结构就失效了。标准库通过“不提供迭代器”这种强制手段把用户的访问路径限制在合法的几个接口里。这是一种“接口即契约”的设计思想。在模拟实现过程中你会发现这个限制是自然而然形成的因为我们根本没有实现begin()、end()所以外部代码无法获得指向内部容器的迭代器。当你在自己的项目里设计数据结构的对外接口时不妨也考虑一下哪些操作会破坏内部不变量该不该把它们暴露出去另外一个面试里常追问的点是priority_queue为什么不能像std::vector那样用迭代器遍历因为它本质上只是vector加一堆堆算法如果允许遍历堆结构调整后迭代器就全失效了而且外部拿着迭代器修改元素会破坏堆序。所以容器适配器的出现就是用“功能残缺”换取“结构安全”。这个思想在很多成熟库里都能看到比如Java的Collections.unmodifiableList它同样是为了安全而主动限制功能。写在后面的一点心得把这三个容器适配器完整手写一遍之后你会发现自己对STL的认知发生了微妙的变化。以前用stack时它是个黑盒现在你会下意识想到哦它内部就是一个dequetop就是调用back。以前写priority_queue时心里总会嘀咕为什么堆顶是最大值现在你看到comp(c[parent], c[child])这行代码就知道语义全在这里。我自己的学习路径是先照着标准库文档手写再在源码里搜push_back、pop_front这些转发调用最后尝试修改底层容器类型跑通测试。这个过程不需要一次做完但每次动手都会有新发现。比如我在模拟实现queue时才真正理解了为什么std::list的pop_front是O(1)而std::vector没有pop_front在写heap调整时才彻底搞懂make_heap、push_heap、pop_heap这三个算法的配合关系。纸上得来终觉浅绝知此事要躬行这句话放在STL源码学习上尤其合适。如果你也想动手我建议你最后再加一个小挑战给这几个模拟实现加上static_assert来检测底层容器是否满足接口要求比如检查std::is_same_vdecltype(c.push_back(std::declvalT())), void。这样做虽然代码量增加了但你会更深刻地体会到C模板约束的边界在哪里。祝编码顺利。
手写STL容器适配器：从模拟实现彻底搞懂stack、queue与priority_queue
从“会用”到“模拟实现”对一个C开发者来说差的并不是代码量而是对容器设计意图的理解。就拿STL里的std::stack、std::queue、std::priority_queue来说很多人天天用知道push、pop、top怎么调用但一旦被问到“为什么stack默认容器是deque而不是vector”“priority_queue为什么不支持遍历”“为什么用仿函数而不是函数指针”这些问题就很容易卡壳。这篇博文我打算直接带大家手写这三个容器适配器通过模拟实现把底层机制彻底摊开。这里的STL指的是C标准模板库和3D打印的STL文件格式没有关系。写模拟实现的价值不在于让你去造一个比标准库更好的轮子而在于让你站在库设计者的角度重新审视问题。当你亲手写出templateclass T, class Container std::dequeT这个类模板骨架时你才会明白为什么适配器模式在STL里这么重要当你自己实现priority_queue的堆调整时你才会真正理解push_heap和pop_heap为什么长得那样。所以这篇文章非常适合正在学习C、准备面试、或者对STL源码有好奇心的朋友阅读过程中我建议你打开编译器跟着敲一遍很多疑问会在键盘上自动消失。1. 为什么说“会用”不等于“懂”三个容器的真实身份1.1 容器 vs 容器适配器要模拟实现第一件事是把它们的身份搞清楚。std::vector、std::list、std::deque是真正的容器它们自己管理内存、自己存数据提供迭代器、提供随机访问能力。而std::stack、std::queue、std::priority_queue这三个家伙在STL的分类里有一个专门的称呼容器适配器。容器适配器的意思是它本身不管理存储而是在另一个容器的基础上对外提供一套受限的、符合特定语义的接口。std::stack内部持有的是一个std::deque但它对外只暴露push、pop、top让你只能从尾部操作从而把deque变成一个“后进先出”的结构。std::queue同理它内部也可以是一个deque但只允许尾部进、头部出变成“先进先出”。std::priority_queue则是在std::vector的基础上通过堆算法维护一个“最大元素永远在堆顶”的结构。如果你在某个代码里写下std::stackint然后试图遍历它编译器会直接报错因为stack压根没有提供迭代器接口。这不是缺陷而是设计上故意的“功能阉割”。容器适配器的存在意义就是不让你有机会破坏它规定的访问规则。这种设计哲学在真实工程里到处都是不是所有数据都该被随意遍历和修改有时候对外暴露的东西越少出错的概率就越低。1.2 为什么默认底层是deque不是vector这是面试高频题也是理解适配器设计的钥匙。std::stack和std::queue的第二个模板参数默认值是std::dequeT但很多人会疑惑std::vector不也能完成尾部插入和删除吗为什么不用vector对于std::stack你确实可以把底层容器换成std::vector代码也能跑。但std::queue是个明显的分界线queue需要“头部删除”用std::vector做头部删除是O(n)级别的操作因为要搬移所有元素。std::deque的设计目标就是“头尾插入删除都是O(1)”所以queue天然应该默认基于deque。那stack为什么也不选vector而选deque这就要细看deque的内存布局了。deque内部是一段一段的连续空间用中控器(map)串起来。头部插入时如果当前缓冲区没有位置就在前面新增一段缓冲区尾部插入同理。它虽然是分段连续的但operator[]仍然能做到O(1)的随机访问只不过常数比vector大一点需要一次双层的指针索引计算。对于stack来说它只需要在尾部操作deque的尾部操作和vector几乎一样快而且deque的扩容策略比vector更温和。vector扩容是要拷贝/移动所有旧元素到新内存的deque的段式结构让它扩容时不需要搬移已有元素只是再分配一小段缓冲区。所以单论push/pop性能deque在大多数情况下是优于vector的。这个结论听起来反直觉但实测下来在尾部高频压栈弹栈的场景里deque确实稳。std::priority_queue为什么不选deque因为priority_queue要频繁进行随机位置访问来实现堆调整deque虽然支持operator[]但常数比vector大而且堆调整每次都要做大量的“读元素、比较、交换”操作用deque只会白白增加开销。vector是连续内存缓存友好度高operator[]是最快的所以priority_queue的默认底层容器是std::vectorT。这个默认值的选择不是随意的背后是操作模式与容器特性的匹配。1.3 三个适配器的行为差异三个适配器虽然结构相似但对外语义完全不同。std::stack是后进先出典型场景是函数调用栈、括号匹配、撤销操作。std::queue是先进先出典型场景是消息队列、任务调度、缓冲区排队。std::priority_queue是“每次能拿到当前集合里最大或最小的元素”典型场景是任务优先级调度、Top-K问题、Dijkstra算法的优先队列优化。它们都没有迭代器都只提供受限接口但受限的方式各不相同。stack只看得到栈顶queue只看得到队头priority_queue只看得到堆顶。这种设计让你在使用时根本不需要关心内部实现只要按语义调用就行。但反过来说如果你不理解内部实现一旦遇到性能问题、自定义类型比较出错、迭代器相关的问题就会很被动。模拟实现的目的就是把这一层窗户纸捅破。2. 整体设计先定接口再谈实现2.1 类模板的三个参数模拟实现的第一步是把类模板的骨架写出来。标准库的设计是这样的std::stackT, Container std::dequeT两个模板参数第二个是底层容器类型。std::queueT, Container std::dequeT同上。std::priority_queueT, Container std::vectorT, Compare std::lessT三个模板参数第三个是仿函数比较器。注意到没有这里并没有“自定义allocator”参数其实有标准库的容器都支持分配器但为了教学简化我这里的模拟实现不展开allocator只看核心逻辑。你掌握主干之后再看标准库源码会轻松很多。为什么用容器类型作为模板参数这是适配器模式最精彩的地方。适配器不关心底层容器是谁只要它满足某些接口要求就行了。对于stack要求底层容器支持push_back、pop_back、back、empty、size。对于queue要求支持push_back、pop_front、front、back、empty、size。这意味着你甚至可以传一个自己实现的容器进去只要满足接口stack的功能就是完整的。这种“鸭子类型”的约束方式在C模板世界里非常常见。2.2 接口设计应保持一致在开始写代码之前我们先明确要实现的接口。没有接口设计就去写实现很容易东一榔头西一棒槌。我列一下我的模拟实现要支持的方法接口stackqueuepriority_queueempty()检查栈空检查队空检查堆空size()返回大小返回大小返回大小top()栈顶引用队头引用堆顶引用push()尾部插入尾部插入尾部插入后堆调整pop()尾部删除头部删除堆顶删除后堆调整emplace()就地构造就地构造就地构造后堆调整swap()交换底层容器交换底层容器交换底层容器我建议你在实现时模仿标准库的接口命名不要自己发明新名字。这样好处很多一是代码阅读的人一看就懂二是你以后看标准库文档、用标准库的时候没有心智负担三是面试官问起来也方便对比。2.3 类模板骨架怎么写这里我给出stack的类模板骨架queue和priority_queue类似namespace my_stl { template class T, class Container std::dequeT class stack { public: using value_type typename Container::value_type; using container_type Container; using size_type typename Container::size_type; using reference typename Container::reference; using const_reference typename Container::const_reference; stack() default; explicit stack(const Container cont) : c(cont) {} bool empty() const { return c.empty(); } size_type size() const { return c.size(); } reference top() { return c.back(); } const_reference top() const { return c.back(); } void push(const value_type value) { c.push_back(value); } void push(value_type value) { c.push_back(std::move(value)); } template class... Args void emplace(Args... args) { c.emplace_back(std::forwardArgs(args)...); } void pop() { c.pop_back(); } void swap(stack other) noexcept(noexcept(c.swap(other.c))) { c.swap(other.c); } protected: Container c; }; }有几个点是刻意这样写的。第一protected保护成员Container c这样派生类可以访问到底层容器但外部调用者碰不到。第二类型别名全部用using而不是typedef这是现代C的风格。第三push同时提供左值引用和右值引用重载这样插入临时对象时能触发移动语义减少拷贝。第四top返回的是back的引用因为stack的“栈顶”就是底层容器的“尾部”。3. 从零手写Stack和Queue的模拟实现3.1 Stack的完整实现与验证Stack的实现非常简单到这一步你会感觉它像一个“壳”。确实容器适配器的本质就是壳它把所有操作都转发给底层容器。但这种转发不是无脑的它是在语法层面把底层容器的能力裁剪到只剩stack语义。Stack的完整实现我已经在2.3中给出了接下来写一个简单的测试用例验证它#include iostream #include deque #include vector int main() { my_stl::stackint stk; stk.push(1); stk.push(2); stk.push(3); std::cout size stk.size() \n; // 3 std::cout top stk.top() \n; // 3 stk.pop(); std::cout top after pop stk.top() \n; // 2 // 使用vector作为底层容器 my_stl::stackint, std::vectorint stk2; stk2.push(10); stk2.emplace(20); std::cout stk2.top stk2.top() \n; // 20 return 0; }你可以试试把Container换成std::list代码一样能跑。只要底层容器支持push_back、pop_back、backstack就能工作。这种可替换性正是适配器模式的核心价值。不过有一点要注意如果你传一个std::forward_list作为底层容器编译会报错因为forward_list没有push_back和back。这正好验证了约束的存在——适配器对底层容器的接口是有要求的只是这种要求在C里通过编译错误来体现而不是通过文档里的继承关系来体现。3.2 Queue的完整实现与验证Queue比Stack多了一个变化它需要pop_front。这意味着底层容器的选择范围更窄了。std::vector没有pop_front你不能用vector做queue的底层容器。但std::list和std::deque都可以。namespace my_stl { template class T, class Container std::dequeT class queue { public: using value_type typename Container::value_type; using container_type Container; using size_type typename Container::size_type; using reference typename Container::reference; using const_reference typename Container::const_reference; queue() default; explicit queue(const Container cont) : c(cont) {} bool empty() const { return c.empty(); } size_type size() const { return c.size(); } reference front() { return c.front(); } const_reference front() const { return c.front(); } reference back() { return c.back(); } const_reference back() const { return c.back(); } void push(const value_type value) { c.push_back(value); } void push(value_type value) { c.push_back(std::move(value)); } template class... Args void emplace(Args... args) { c.emplace_back(std::forwardArgs(args)...); } void pop() { c.pop_front(); } void swap(queue other) noexcept(noexcept(c.swap(other.c))) { c.swap(other.c); } protected: Container c; }; }这里的核心点是front和back都返回引用但pop只从头部弹。如果你尝试用my_stl::queueint, std::vectorint编译器会告诉你vector没有pop_front成员函数。这不是坏事它让你被迫思考“哪些容器适合做queue的底层”同时也验证了STL默认选择deque的合理性。测试一下#include iostream #include deque #include list int main() { my_stl::queueint q; q.push(1); q.push(2); q.push(3); std::cout front q.front() \n; // 1 std::cout back q.back() \n; // 3 q.pop(); std::cout front after pop q.front() \n; // 2 my_stl::queueint, std::listint q2; q2.push(100); q2.push(200); q2.pop(); std::cout q2.front q2.front() \n; // 200 return 0; }到这里你已经实现了两个容器适配器。你会发现它们的实现难度远低于vector和deque本身因为它们没有内存管理、没有迭代器实现、没有复杂的数据结构只是把现有的容器包了一层壳。但请不要小看这层壳——它定义了行为边界是设计意图的体现。4. 真正的重头戏Priority_Queue的模拟实现4.1 三个成员容器、比较器、堆算法Priority_queue的模拟实现难度主要体现在两个地方一是堆算法的实现二是比较器的使用方式。它内部有三个关键成员底层容器c、比较器comp、以及一组堆调整算法。很多人第一次写priority_queue的时候会陷入一个误区试图自己去实现heap数据结构。其实不用堆本质上就是一个数组这里就是vector通过下标关系表达父子关系。对于下标为i的元素它的左孩子是2*i1右孩子是2*i2父节点是(i-1)/2。这些下标关系是理解堆调整的基础。堆调整分两种向上调整和向下调整。插入元素时先把元素放到尾部然后向上调整让它“浮”到合适的位置。弹出堆顶时把堆顶和最后一个元素交换再弹出最后一个元素然后从堆顶向下调整让新的堆顶“沉”到合适的位置。4.2 向上调整与向下调整的细节先写两个辅助函数。向上调整adjust_up从某个孩子节点开始不断和父节点比较。如果父节点“小于”孩子节点就交换然后继续往上走。这里的关键是“小于”这个语义它取决于比较器comp。void adjust_up(size_type child) { size_type parent (child - 1) / 2; while (child 0) { if (comp(c[parent], c[child])) { std::swap(c[parent], c[child]); child parent; parent (child - 1) / 2; } else { break; } } }向下调整adjust_down从某个父节点开始先找到孩子节点然后找出左右孩子中较大的一个如果父节点“小于”较大的孩子就交换然后继续往下走。void adjust_down(size_type parent) { size_type child parent * 2 1; while (child c.size()) { // 选出左右孩子中较大的一个 if (child 1 c.size() comp(c[child], c[child 1])) { child; } if (comp(c[parent], c[child])) { std::swap(c[parent], c[child]); parent child; child parent * 2 1; } else { break; } } }如果你之前没接触过堆这里最容易出错的是child 1 c.size()这个边界条件。当左孩子已经存在但右孩子不存在时不能去访问child1否则就是越界。很多新手写的堆排序列越界基本都是栽在这个地方。这两段代码配合comp的语义就是priority_queue的灵魂。注意到comp在堆调整里出现了两次一次是比较父和子是否要交换一次是比较两个子节点谁更大。把比较逻辑抽出来整个堆调整算法就不关心元素类型了。这正是泛型编程的威力算法与数据类型解耦。4.3 priority_queue的完整实现下面是完整的priority_queue模拟实现。我把make_heap、adjust_up、adjust_down都封装成私有成员函数并实现了标准库那几个关键接口。namespace my_stl { template class T, class Container std::vectorT, class Compare std::lessT class priority_queue { public: using value_type typename Container::value_type; using container_type Container; using size_type typename Container::size_type; using reference typename Container::reference; using const_reference typename Container::const_reference; priority_queue() default; explicit priority_queue(const Compare compare) : comp(compare) {} priority_queue(const Compare compare, Container cont) : comp(compare), c(std::move(cont)) { make_heap(); } template class InputIt priority_queue(InputIt first, InputIt last, const Compare compare Compare()) : comp(compare), c(first, last) { make_heap(); } bool empty() const { return c.empty(); } size_type size() const { return c.size(); } const_reference top() const { return c.front(); } void push(const value_type value) { c.push_back(value); adjust_up(c.size() - 1); } void push(value_type value) { c.push_back(std::move(value)); adjust_up(c.size() - 1); } template class... Args void emplace(Args... args) { c.emplace_back(std::forwardArgs(args)...); adjust_up(c.size() - 1); } void pop() { if (empty()) return; std::swap(c.front(), c.back()); c.pop_back(); if (!empty()) adjust_down(0); } void swap(priority_queue other) noexcept( noexcept(c.swap(other.c)) noexcept(std::swap(comp, other.comp))) { c.swap(other.c); std::swap(comp, other.comp); } protected: void make_heap() { if (c.size() 2) return; // 从最后一个非叶子节点开始逐个向下调整 for (size_type i (c.size() - 1 - 1) / 2; i 0; --i) { adjust_down(i); } adjust_down(0); } void adjust_up(size_type child) { size_type parent (child - 1) / 2; while (child 0) { if (comp(c[parent], c[child])) { std::swap(c[parent], c[child]); child parent; parent (child - 1) / 2; } else { break; } } } void adjust_down(size_type parent) { size_type child parent * 2 1; while (child c.size()) { if (child 1 c.size() comp(c[child], c[child 1])) { child; } if (comp(c[parent], c[child])) { std::swap(c[parent], c[child]); parent child; child parent * 2 1; } else { break; } } } protected: Compare comp; Container c; }; }这里有几个设计细节值得展开。第一个是top()为什么返回c.front()而不是像vector那样支持随机访问。堆顶就是最大元素它总是被放在数组的第一个位置。如果你返回了reference而不是const_reference外部就可以通过pq.top() 100来修改堆顶元素但这会破坏堆结构。标准库的priority_queue::top()返回的是const_reference防止外部修改。所以我的实现也返回const_reference这是一个很重要的安全设计。第二个是pop()操作。标准实现是先std::pop_heap再把元素pop_back出去我这里直接手写了交换和向下调整。为什么pop之后要做向下调整因为交换后数组里除了堆顶其余部分仍然满足堆序只有堆顶可能不满足。这种情况下单独对堆顶做一次向下调整就能恢复整个堆序。第三个是make_heap()的起始下标。最后一个非叶子节点的下标是(size-2)/2也就是(size-1-1)/2。从它开始往前逐个向下调整就能把任意数组整理成合法的堆。我举个例子数组[3, 1, 4, 1, 5, 9, 2, 6]size为8从下标3开始调整然后2、1、0最后整个数组就满足最大堆性质。这个过程和排序算法里的建堆逻辑一致理解了它后面看std::make_heap源码会轻松不少。4.4 为什么默认是最大堆less的堆语义这是priority_queue里最反直觉的一个点Compare的默认值是std::lessT字面意思是“小于”但priority_queue弹出的却是最大值。很多初学者第一次看到这个默认参数时都会懵一下。要解释清楚这个问题得回到堆调整里那句核心判断if (comp(c[parent], c[child]))。当comp(c[parent], c[child])返回true时说明父节点“小于”孩子节点此时就交换它们。换句话说comp表达的是“parent 是否应该排在 child 前面”的意思。如果comp是std::less那么parent child时交换结果就是父节点永远不小于子节点也就是大根堆。所以请记住这个结论std::lessT对应的堆是大根堆std::greaterT对应的是小根堆。你如果需要小根堆把第三个模板参数显式传成std::greaterT即可// 小根堆 my_stl::priority_queueint, std::vectorint, std::greaterint min_heap; min_heap.push(10); min_heap.push(5); min_heap.push(20); std::cout min_heap.top() \n; // 输出 5这个细节值得你在面试时主动讲出来因为这能证明你不是背接口而是真的理解比较器的语义。5. 常见问题与排查技巧实录5.1 模板实现不能放.cpp文件这是所有C模板学习者都会踩的第一个坑。如果你把stack、queue、priority_queue的声明放在.h文件里把实现放在.cpp文件里然后在另一个.cpp文件里使用它们链接器会报“未定义引用”的错误。原因在于模板不是普通的函数或类它不是一个具体的实体而是一个“图纸”。编译器在使用模板时需要用模板参数去“实例化”出真正的类。而实例化要求编译器能看到完整的模板定义。如果把实现藏在.cpp里使用端只看到了声明编译器无法实例化于是只能留一个符号让链接器去找但链接器同样看不到实现于是报错。解决方式有几种。最简单的是把所有模板代码放在同一个头文件里这也是标准库的做法。另一种是显式实例化在实现文件里写template class my_stl::stackint;但这会严重限制模板的通用性每用一个新的类型参数就要声明一次非常麻烦。我建议你习惯第一种方式模板实现放头文件不要分离编译。5.2 自定义类型放入priority_queue报错std::lessT默认使用operator来比较两个对象。如果你定义了一个类型struct Task { int priority; std::string name; };然后直接塞进priority_queueTask编译器会报错提示no match for operator。这是自定义类型进入排序型容器最常见的坑。解决方案有两种一是在Task里重载operator二是给priority_queue传入自定义仿函数。我强烈推荐第二种因为有时候同一个类型在不同场景下需要不同的排序规则把比较策略外置更灵活。比如struct Task { int priority; std::string name; }; struct TaskCmp { bool operator()(const Task a, const Task b) const { // 注意这里写的是 a 是否应该排在 b 后面 return a.priority b.priority; } }; my_stl::priority_queueTask, std::vectorTask, TaskCmp pq;这里要特别注意仿函数的语义operator()返回true时表示a应该排在b的后面。放到堆里就是a的优先级比b低时才会交换。我见过不少同学在自定义仿函数时把比较方向搞反结果得到完全相反的优先级顺序。建议你写完后先跑一个push(高优先级任务)push(低优先级任务)top()的小测试确认堆顶元素和预期一致。5.3 空容器调用top或pop调用空stack的top、空queue的front、空priority_queue的top都是未定义行为。标准库根本不会帮你检查你在模拟实现里也可以不检查。但实际工程里这种未定义行为是最难排查的它可能不崩溃可能返回一个垃圾值也可能在你发布后某个诡异的输入下突然崩溃。我的习惯是在关键接口处加断言。比如模拟实现里可以加上assert(!c.empty())然后通过NDEBUG宏在release版本里关掉。如果你想把防御做扎实可以抛一个std::out_of_range异常但要注意这会让top变成有代价的调用和标准库的零开销原则有冲突。实际项目中我建议调用方做好empty()检查就像pop之前先看empty()一样。这个习惯能帮你省掉无数崩溃排查时间。5.4 底层容器选型不当导致性能问题使用这三个适配器时你完全可以显式指定底层容器。Stack可以用std::vectorQueue可以用std::list甚至你还可以用一个自研的容器。但不同的选型会导致天差地别的性能。Stack如果数据量巨大用std::deque是均衡的选择但如果你的元素是小对象且栈的最大深度已知用std::vector提前reserve掉内存性能会更稳定。Queue的大数据量场景std::list每个节点有额外的指针开销而且节点在内存中不连续缓存命中率低std::deque虽然也是分段连续但整体缓存友好度远好于list。所以默认给queue用deque是经验主义的胜利。Priority_queue只有一种合理选择连续内存容器。堆调整最核心的瓶颈是随机访问和交换std::vector是唯一在随机访问上做到极致的容器。如果你非要用std::deque作为priority_queue的底层容器你会发现代码能跑但性能会明显下降因为deque的operator[]比vector慢。这也是为什么标准的priority_queue干脆默认vector不给使用者其他选项。5.5 面试必问为什么容器适配器没有迭代器这个问题比看起来深。没有迭代器本质上是为了保证结构不变性。Stack如果给你一个迭代器你就能遍历整个栈还能通过迭代器修改中间的元素这会让“后进先出”的语义荡然无存。Queue和priority_queue同理。如果通过迭代器访问底层数组那priority_queue的堆序性质随时可能被破坏整个数据结构就失效了。标准库通过“不提供迭代器”这种强制手段把用户的访问路径限制在合法的几个接口里。这是一种“接口即契约”的设计思想。在模拟实现过程中你会发现这个限制是自然而然形成的因为我们根本没有实现begin()、end()所以外部代码无法获得指向内部容器的迭代器。当你在自己的项目里设计数据结构的对外接口时不妨也考虑一下哪些操作会破坏内部不变量该不该把它们暴露出去另外一个面试里常追问的点是priority_queue为什么不能像std::vector那样用迭代器遍历因为它本质上只是vector加一堆堆算法如果允许遍历堆结构调整后迭代器就全失效了而且外部拿着迭代器修改元素会破坏堆序。所以容器适配器的出现就是用“功能残缺”换取“结构安全”。这个思想在很多成熟库里都能看到比如Java的Collections.unmodifiableList它同样是为了安全而主动限制功能。写在后面的一点心得把这三个容器适配器完整手写一遍之后你会发现自己对STL的认知发生了微妙的变化。以前用stack时它是个黑盒现在你会下意识想到哦它内部就是一个dequetop就是调用back。以前写priority_queue时心里总会嘀咕为什么堆顶是最大值现在你看到comp(c[parent], c[child])这行代码就知道语义全在这里。我自己的学习路径是先照着标准库文档手写再在源码里搜push_back、pop_front这些转发调用最后尝试修改底层容器类型跑通测试。这个过程不需要一次做完但每次动手都会有新发现。比如我在模拟实现queue时才真正理解了为什么std::list的pop_front是O(1)而std::vector没有pop_front在写heap调整时才彻底搞懂make_heap、push_heap、pop_heap这三个算法的配合关系。纸上得来终觉浅绝知此事要躬行这句话放在STL源码学习上尤其合适。如果你也想动手我建议你最后再加一个小挑战给这几个模拟实现加上static_assert来检测底层容器是否满足接口要求比如检查std::is_same_vdecltype(c.push_back(std::declvalT())), void。这样做虽然代码量增加了但你会更深刻地体会到C模板约束的边界在哪里。祝编码顺利。