从零手写C++ STL stack和queue：彻底搞懂容器适配器与deque底层原理

先说个结论STL里的stack和queue可能是你最早接触、也最容易“轻视”的两个容器。不少朋友会用std::stackint和std::queueint刷题但被问到“stack的底层到底是什么为什么默认用deque如果让你不用STL自己实现一个你会怎么写”就卡壳了。这篇博文就干一件事从零手写stack和queue的所有关键操作把接口设计、底层容器选型、异常安全、内存扩容这些平时藏在黑盒里的东西全部摊开。适合对C有一定基础、想深入理解STL设计思路的读者也适合准备面试想进阶一把的朋友。我先把话放前面自己实现STL容器适配器不是为了在生产环境里替换标准库——标准库经过几十年的迭代远比我们随手写的健壮。真正有价值的是在实现过程中搞明白三个问题到底什么是“容器适配器”它和普通容器有什么本质区别为什么stack和queue默认使用deque而不是看起来更自然的vector或list当push、pop、拷贝、扩容这些操作组合在一起时代码正确的隐藏前提是什么1. 为什么非要从零实现一遍stack和queue1.1 面试和工程中真正考的底层认知很多人觉得“从零实现stack”就是定义一个数组、维护一个栈顶指针十分钟搞定。但STL里的stack远远不止“一个数组”这么简单。你去面C岗位面试官问“实现一个stack”他心里其实想听到的是你懂不懂容器适配器这个概念、懂不懂底层容器可替换、懂不懂操作的时间复杂度和异常安全。如果只是闷头写int data[100]; int topIndex;那和写C语言没有区别CSTL的设计思想完全没体现出来。换个角度自己在工程里如果你正在写一个底层库不希望外部依赖标准库的std::stack比如嵌入式环境、老平台不支持完整STL又不想抛弃STL的容器思路那手写一个轻量适配器是完全合理的需求。这种情况下你不仅要实现功能还要让接口长得像STL方便以后无缝替换回来。1.2 stack和queue是容器适配器不是容器先把这个核心概念掰清楚std::stack和std::queue本身并不是容器它们是包装在其他容器之上的一层“接口限制器”。stack只允许在一端栈顶插入删除提供push/pop/top。queue只允许一端插入队尾、另一端删除队头提供push/pop/front/back。底层真正存储数据的是std::deque、std::list这些容器。stack和queue做的事情是把底层容器的全部接口“关掉一半”只暴露符合栈/队列语义的那部分。所以它们被称为容器适配器。这个设计的好处是底层容器可以换。std::stackint, std::vectorint stk;就把底层换成了vector栈的操作照常。同样std::queueint, std::listint q;也是合法的。而queue如果硬要用vector做底层编译会报错为什么后面我会专门讲。理解了适配器思想你的实现思路就清晰了我们不需要自己管理内存不需要写链表节点只需要在选定底层容器的基础上调用它的接口限制外部访问权限即可。2. 底层容器选型为什么默认用deque而不是vector或list2.1 三种候选容器的增删和内存表现先看STL本身的选择std::stack和std::queue的默认底层容器都是std::deque。为什么不是vector或list这得从三种容器的特性讲起。容器push_back/pop_backpush_front/pop_front随机访问内存布局适合做stack底层适合做queue底层vectorO(1) 均摊O(n)O(1)连续内存可以不行头删O(n)dequeO(1) 均摊O(1) 均摊O(1)分段连续完美完美listO(1)O(1)O(n)节点独立可以可以对于stack来说只需要push_back/pop_backvector完全能胜任。那STL为什么不用vector这里面有几个隐情vector扩容是“整体搬迁”。当vector容量不够时会申请一块更大内存把旧元素全部拷贝/移动过去。如果元素很大或拷贝成本高扩容瞬间代价很大。deque采用分段连续存储——它由多块固定大小的缓冲区组成扩容时只是新增一块缓冲区不需要搬运已有元素。所以deque的均摊复杂度虽然也是O(1)但单次push的最坏代价比vector小得多。vector不能做queue的底层。queue需要push_back配合pop_frontvector的pop_front复杂度是O(n)元素全部前移这完全没法接受。所以要么用deque要么用list。list虽然头删O(1)但每个节点需要额外存储前后指针内存开销大而且缓存局部性差。deque是“双端都能高效操作”的正好同时满足stack和queue。deque迭代器不失效但指针/引用可能失效。这个特性很微妙在deque中间插入元素会导致迭代器失效但在两端插入元素时迭代器不会失效只是引用和指针会失效。对stack和queue来说操作都发生在两端所以deque的迭代器稳定性很适合做适配器底层。2.2 空间分配策略与迭代器失效的对比再深入一层比较一下vector和deque的内存策略vector维护start/finish/end_of_storage三个指针扩容时如果finish end_of_storage就找新内存整块搬迁。迭代器就是普通指针扩容后所有迭代器全部失效。deque内部维护一个中控器map一个指针数组每个指针指向一块缓冲区通常512字节。push_back时如果当前缓冲区满了就新申请一个缓冲区并映射到map里。因此在两端push时已有元素的地址不变但指向已有元素的指针/引用可能因为map重新分配而失效迭代器通过两级结构能追踪而裸指针引用会失效。对stack和queue来说我们只关心两端操作deque的这种特性已经足够。但如果你实现自己的适配器并且希望“push后之前获得的引用依然有效”那你底层可以考虑std::list——list在任何位置插入都不会使已有迭代器、指针、引用失效。当然list也有代价无法随机访问每个节点有额外指针开销内存碎片化严重。2.3 自定义底层容器需要满足什么条件STL的stack和queue模板都有一个Container参数templateclass T, class Container std::dequeT class stack; templateclass T, class Container std::dequeT class queue;这里Container不是随便什么类型都行它必须满足一系列要求。我们实现自己的版本时也要定义清楚这些“概念约束”否则就跟瞎写没区别。对stack的底层容器必须支持push_backpop_backback()size()empty()可拷贝构造、可赋值对queue的底层容器必须支持push_backpop_frontfront()back()size()empty()所以vector可以用作stack的底层它满足上述条件但不能用作queue的底层——因为vector没有pop_front。这也是为什么std::queueint, std::vectorint会编译失败。我们自己实现时也应该在模板参数中声明_Container std::dequeT并且通过static_assert或者编译期检查提示用户“你的底层容器不支持某些操作”。当然实际上你调用c.pop_front()时编译器就会报错只是报错信息可能很晦涩。更友好的做法是使用std::void_t或C20的requires来给出清晰提示不过这里我们先不展开重点是核心逻辑。3. 从零实现stack接口设计、代码落地与边界处理3.1 核心成员与构造/析构/拷贝控制我们直接从代码开始自己实现一个stack。为了不跟STL重名可以放在自己的命名空间里或者叫my_stack。我采用类模板底层容器作为模板参数。#include deque #include type_traits #include stdexcept namespace my_stl { templatetypename T, typename Container std::dequeT class stack { public: // 类型别名方便外部使用 using container_type Container; using value_type typename Container::value_type; using size_type typename Container::size_type; using reference typename Container::reference; using const_reference typename Container::const_reference; protected: Container c; // 底层容器 public: // 默认构造直接使用Container的默认构造 stack() default; // 用自定义容器构造 explicit stack(const Container cont) : c(cont) {} // 拷贝构造、赋值用默认实现即可 // 因为Container自身具备正确的深拷贝行为 stack(const stack other) default; stack operator(const stack other) default; // 移动构造、移动赋值 stack(stack other) noexcept noexcept(noexcept(Container(std::move(other.c)))) : c(std::move(other.c)) {} stack operator(stack other) noexcept( noexcept(std::declvalContainer().operator(std::move(other.c)))) { c std::move(other.c); return *this; } // 关键操作 bool empty() const noexcept { return c.empty(); } size_type size() const noexcept { 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)); } templatetypename... 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))) { using std::swap; swap(c, other.c); } friend bool operator(const stack lhs, const stack rhs) { return lhs.c rhs.c; } friend bool operator!(const stack lhs, const stack rhs) { return lhs.c ! rhs.c; } }; } // namespace my_stl这段代码虽然不长但信息量极大。有几个细节你需要特别注意。3.2 push/pop/top/empty/size的细节逐个拆解关键接口的设计理由为什么top()返回引用而不是值reference top() { return c.back(); } const_reference top() const { return c.back(); }如果返回T值那用户做stk.top() 5就编译不过也拿不到真正的栈顶元素来修改。返回back()的引用意味着外部可以直接修改栈顶元素。注意这允许用户“作弊”绕过栈的约束——他可以修改栈顶元素但不能删除或插入其他位置。这是STL设计的妥协栈的语义约束的是插入/删除位置而不是“禁止修改栈顶值”。为什么empty()和size()用noexcept因为查询容器状态不会抛异常也不用访问可能失败的内存。这里标记noexcept有助于编译器优化也让使用者调用起来更有把握。为什么pop()不返回被删除的元素很多初学者会问为什么不能T val stk.pop()两个原因返回元素值需要先拷贝一份再删除多余的开销而且如果拷贝构造抛异常那到底是删还是没删栈里存的对象可能没有拷贝构造只能移动强制返回值会编译失败。所以STL的设计是pop()只负责删除要取元素先用top()拿到引用然后拷贝/移动出来再pop()。即T value stk.top(); stk.pop();这个模式必须记住否则你自定义栈的接口就会设计歪。push为什么要同时提供const左值引用和右值引用两个版本因为push(const T)无法处理临时对象的高效插入。如果只提供push(const T)对右值也只能拷贝白白多一次拷贝。提供push(T)后stk.push(std::move(x))能调用移动构造stk.push(10)时常量10会先构造临时int然后匹配右值版本直接移动进底层容器省一次拷贝。这里还需要注意Container::push_back(T)本身就有重载我们这里只是转发。emplace为什么是变长模板emplace允许直接在容器内构造对象避免临时对象创建和移动。比如stk.emplace(hello, 5, c)如果T是一个自定义类构造函数接收字符串、整数和字符那emplace会在底层容器的内存上直接调用构造函数而不是先构造一个临时T再push进去。这在性能敏感场景是实打实的优化。pop()的边界问题空栈调用pop会怎样标准STL规定对空stack调用pop()是未定义行为标准库一般不会帮你检查。我们自己的实现也没检查因为检查需要额外的if(empty()) throw ...这会造成每次pop都多一次分支判断破坏性能。所以正确用法是调用者保证非空。如果你非要做一个安全版本可以加一个带异常检查的pop_safe()但不要改变pop()的语义。3.3 基于deque和vector的两种实现对比我们的实现默认底层是deque但模板参数允许你传vectormy_stl::stackint, std::vectorint stk;这时所有操作照样正确因为vector支持push_back、pop_back、back、empty、size。那两种底层内存表现有什么差异我们来实测#include iostream #include deque #include vector #include chrono struct Node { int data; Node(int d) : data(d) {} }; int main() { const int N 1000000; // vector 作为底层 auto t1 std::chrono::high_resolution_clock::now(); std::vectorint v; for (int i 0; i N; i) v.push_back(i); while (!v.empty()) v.pop_back(); auto t2 std::chrono::high_resolution_clock::now(); std::cout vector time: std::chrono::duration_caststd::chrono::milliseconds(t2 - t1).count() ms\n; // deque 作为底层 t1 std::chrono::high_resolution_clock::now(); std::dequeint d; for (int i 0; i N; i) d.push_back(i); while (!d.empty()) d.pop_back(); t2 std::chrono::high_resolution_clock::now(); std::cout deque time: std::chrono::duration_caststd::chrono::milliseconds(t2 - t1).count() ms\n; return 0; }在我的机器上Release模式vector通常比deque略快一些因为vector连续内存缓存命中率高。那为什么STL默认还是选deque因为stack的性能瓶颈在push的“单次最坏时间”和“内存碎片”上。vector扩容时如果元素数量很大一次性拷贝可能造成明显卡顿实时系统无法接受deque分摊到块延迟稳定。另外vector存储元素必须连续当元素是复杂大对象时整体搬迁成本更高。STL作为通用库要照顾极端场景所以默认deque非常合理。如果你实现的stack用于已知最大容量、且想极致性能可以传vector并提前reserve避免扩容。这时候我们自己的模板参数设计就显出了优势。4. 从零实现queueFIFO语义与底层容器的约束4.1 queue的接口定义与实现queue和stack的结构几乎一样差别只在于top()变成front()和back()pop()删除的是队头底层调用pop_front()。代码直接上namespace my_stl { templatetypename T, typename Container std::dequeT class queue { public: using container_type Container; using value_type typename Container::value_type; using size_type typename Container::size_type; using reference typename Container::reference; using const_reference typename Container::const_reference; protected: Container c; public: queue() default; explicit queue(const Container cont) : c(cont) {} queue(const queue other) default; queue operator(const queue other) default; queue(queue other) noexcept : c(std::move(other.c)) {} queue operator(queue other) noexcept { c std::move(other.c); return *this; } bool empty() const noexcept { return c.empty(); } size_type size() const noexcept { 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)); } templatetypename... 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))) { using std::swap; swap(c, other.c); } friend bool operator(const queue lhs, const queue rhs) { return lhs.c rhs.c; } friend bool operator!(const queue lhs, const queue rhs) { return lhs.c ! rhs.c; } }; } // namespace my_stl4.2 为什么queue不能用vector直接做底层容器这个坑非常经典。很多初学者会尝试std::queueint, std::vectorint q; // 编译错误错误信息类似于std::vectorint does not provide a class type pop_front因为queue::pop()内部会调用c.pop_front()而std::vector只有pop_back没有pop_front。这其实是好事——编译期强制你选择正确的容器。可能你会想我可以给vector补充一个pop_front吗不行为vector实现pop_front除非你把头元素后面的元素全部前移一位复杂度O(n)。而这会让queue::pop()从O(1)退化到O(n)整个队列就废了。所以STL在容器层面就直接禁止vector作为queue的底层容器。记住这句话queue底层必须是一个支持“队尾push_back、队头pop_front”的容器。标准库里只有deque和list满足要求。你自定义容器时也要遵循这个约束。4.3 自定义queue的front/back的引用返回问题queue和stack有一点不同queue需要同时暴露front()和back()。front()返回队头元素引用back()返回队尾元素引用。这里要特别注意如果你持有back()返回的引用然后再执行push这个引用可能失效。具体来说如果底层是dequepush_back之后之前back()返回的引用会失效因为deque两端插入时“引用/指针”可能失效迭代器一般不会。如果底层是listpush_back之后之前的引用和迭代器始终有效。所以通用的安全使用模式是my_stl::queueint q; q.push(10); q.push(20); // 持有引用做点什么但一旦再次push之前的引用就当它不存在 int ref q.front(); ref 30; // 可以修改了队头 q.push(40); // 之后不要再使用ref在自定义实现中我们直接透传底层容器的front()和back()。如果你希望提供更强的引用稳定性保证可以选择list做底层但这与“默认deque”的默认行为就不一致了。工程上通常默认deque不承诺引用在push后依然有效因此使用时要小心。5. 异常安全、动态扩容与性能实测5.1 异常安全push时allocator抛异常怎么办自己实现容器适配器时最容易被忽视的就是异常安全。标准库的push提供了基本异常安全保证如果push由于内存不足等原因抛出异常容器保持原有的有效状态size不变元素不缺失不产生内存泄漏。我们基于deque的push_back其实已经自带这个保证——deque内部如果扩容失败会正确回滚并释放临时申请的内存。但如果你自己写一个底层容器比如用原生数组自实现就要特别注意push时先分配新内存如果拷贝元素中途抛异常必须把已拷贝的部分析构掉、释放新内存保持原容器不变。这个繁琐的“事务”逻辑通常交给库实现。所以我们的适配器其实“白嫖”了底层容器提供的安全保证。还有一个小细节stack(uint32_t size)这种带容量上限的实现当容量已满时再push怎么办标准STL的stack没有“容量上限”概念。如果你实现一个固定容量的栈建议设计为push返回bool或者抛出std::overflow_error。不要自己静默截断那样动静态查错都很难受。5.2 动态扩容对迭代器的影响与reserve策略提到扩容先澄清一个基本事实std::stack和std::queue根本不提供reserve()。为什么因为默认的底层容器是dequedeque没有reserve()接口。如果你希望预分配空间只能显式构造一个vector再把它传给stackstd::vectorint storage; storage.reserve(10000); // 预先分配容量 std::stackint, std::vectorint stk(std::move(storage));注意这里storage被拷贝进stack了。如果要避免拷贝可以std::stackint, std::vectorint stk; // 没有直接方式拿到底层容器除非通过暴露容器类型 static_caststd::vectorint(stk).reserve(10000);这是利用stack继承自container_type标准库中stack的底层容器是protected成员你可以通过继承来访问但标准库不保证这种技巧长期有效。我自己实现时把Container c放在protected区用户可以定义子类访问class MyVecStack : public my_stl::stackint, std::vectorint { public: void reserve(size_t n) { this-c.reserve(n); } };这是适配器设计的一个天然弱点隐藏底层容器后一些底层特化能力也被隐藏了。工程上如果确实需要reserve直接使用相应容器就好不必套上stack的壳。5.3 实测push入栈/入队的耗时曲线为了看清不同底层容器的性能差异我写了一个小基准分别测试stackint, vectorint、stackint, dequeint和queueint, listint的pushpop累计耗时。样本数量从1万到100万观察曲线。#include iostream #include vector #include deque #include list #include chrono templatetypename StackLike double test_push_pop(int n) { auto start std::chrono::steady_clock::now(); StackLike s; for (int i 0; i n; i) s.push(i); while (!s.empty()) s.pop(); auto end std::chrono::steady_clock::now(); return std::chrono::durationdouble, std::milli(end - start).count(); } int main() { std::vectorint sizes {10000, 50000, 100000, 500000}; for (int n : sizes) { double t_vec test_push_popstd::stackint, std::vectorint(n); double t_deq test_push_popstd::stackint, std::dequeint(n); double t_list test_push_popstd::queueint, std::listint(n); std::cout n n : vector t_vec ms, deque t_deq ms, list(queue) t_list ms\n; } return 0; }实测结论O2编译g 11Ubuntu小数据量1万以下差异很小毫秒级没必要在意。中等数据量10万以上vector deque list。vector命中缓存list每个节点分散在堆上缓存不友好耗时大约是vector的2~3倍。deque居中因为deque为了支持双端操作多了一个中控器映射push时偶发获取新缓冲区也略慢于vector。所以如果只在栈场景堆栈vector底层的性能通常是最好的。但STL默认deque并非为了“最快”而是为了“稳兼容双端最坏情况可控”。理解这种权衡比背下结论更有意义。6. 常见坑与调试技巧size_t无符号、栈溢出、内存泄漏6.1 size_t比较被坑判断栈空后取top的顺序我见过无数人写这种代码while (!stk.empty()) { int v stk.top(); // 这行没问题 stk.pop(); }这个没问题。有问题的通常是for (size_t i stk.size(); i 0; --i) { // 死循环 ... }size_t是无符号类型i--到0之后再减1变成SIZE_MAX永远不会小于0死循环。正确写法while (!stk.empty()) { ... }或者如果你确实要按序处理固定次数可以先取sizesize_t n stk.size(); for (size_t i 0; i n; i) { stk.pop(); // 不要在里面用stk.size()判断因为pop会改变size }还有更深层的坑先判断empty再访问top。虽然top()本身不改变状态但如果你忘了判断对一个空栈调用top()是未定义行为。标准STL不检查我们自定义也不检查。一旦空栈top可能直接拿到非法地址的数据调试时非常迷惑。所以养成习惯if (!s.empty()) { auto val s.top(); }我建议在自己实现的调试版本里可以加断言reference top() { assert(!c.empty()); // 仅Debug模式 return c.back(); }要包含cassert这样Release编译时断言自动消失不影响性能。6.2 复制栈和队列时深浅拷贝的陷阱我们的实现里拷贝构造和赋值都是 default底层Container c会正确深拷贝。但如果你是手动管理内存的实现这里就是重灾区。举个例子如果你用原生数组实现栈struct Stack { int* data; int cap; int topIndex; };当Stack a拷贝给Stack b时如果只是b.data a.data两个栈的data指针指向同一块内存。之后a.pop()修改了数据b的内容也跟着变析构时double free程序直接崩。这就是浅拷贝的典型问题。解决方式有两个实现拷贝构造函数和拷贝赋值运算符为每个栈复制一份独立的内存。利用Container c的自动管理这正是我们实现的优势——底层容器已经处理了深拷贝适配器无需重写。如果你需要用自定义的底层容器记住你的Container类型必须满足“值语义”即拷贝后两个对象完全独立。std::vector、std::deque、std::list都满足。6.3 如何用valgrind和gdb排查自己实现的问题当我们自己写的stack/queue出现内存错误或程序异常时怎么定位推荐两个工具valgrind memcheck检测内存泄漏、越界读写、使用未初始化内存。编译时加-g运行g -g -o test_stack my_stack_test.cpp valgrind --toolmemcheck --leak-checkfull ./test_stack输出里如果出现Invalid write of size 4之类的会明确指出在哪一行源码。如果出现definitely lost: X bytes in Y blocks说明有泄漏。gdb定位崩溃点。比如空栈top可能不会立刻崩溃而是数据不对。你可以用gdb设置断点或catch throw捕获异常。常用命令gdb ./test_stack break my_stl::stackint::top # 打断点 run bt # 查看调用栈 print c.size() # 看底层容器大小一个技巧调试时给typo的类或者函数加断言比如assert(c.size() 0)能快速把“滑落式错误”转成“刚性的崩溃点”。我经常在实现底层容器适配器后做一组随机操作序列来验证与标准库行为一致。比如生成随机的push/pop/emplace操作同时作用于my_stack和std_stack每一步比较size()、top()是否一致。跑一百万次随机序列如果全部一致基本说明逻辑正确。如果你也写一个测试程序会发现像“比较两个栈的相等”这种边角操作也要定义清楚——我们实现的operator比较的是底层容器而不是逐元素比较这在语义上是等价的因为元素顺序本身就是栈的存储顺序。最后分享一个个人心得自己实现STL容器适配器最大的价值不是写出一份可以代替标准库的代码而是让你在以后用std::stack/std::queue时能意识到背后有“接口适配”“底层容器可替换”“异常安全保证”“复合操作的正确顺序”这些设计维度。面试时能把这些讲透比手写十个栈都管用。如果你准备挑战自己不妨再试试实现priority_queue它虽然名字里带queue但实现完全不同——底层用的heap算法加vector那又是一套新的思路了。