1. 引言容器适配器的设计哲学在 C STL 中stack和queue被设计为容器适配器而非完整的容器。这是一种经典的适配器模式在库设计中的体现。适配器模式将一个类的接口转换成客户希望的另一个接口。适配器模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。STL 的stack和queue并不自己管理内存或存储元素而是通过封装一个底层容器如deque、vector、list来提供特定的接口。这种设计的优势在于复用性复用现有容器的所有实现细节灵活性允许用户根据场景选择不同的底层容器关注点分离适配器只关心接口语义容器只关心存储性能2. Stack 的深度剖析与模拟实现2.1 Stack 的核心概念与接口stack是一种后进先出LIFO, Last In First Out的数据结构。其核心操作只有几个操作功能时间复杂度push()向栈顶插入元素O(1)pop()移除栈顶元素O(1)top()访问栈顶元素O(1)empty()判断栈是否为空O(1)size()返回栈中元素数量O(1)STL 标准要求stack提供以下成员类型value_type元素类型container_type底层容器类型size_type无符号整数类型2.2 底层容器的选择策略stack的底层容器必须支持以下操作back()获取最后一个元素作为栈顶push_back()在尾部添加元素pop_back()删除尾部元素任何满足这些要求的容器都可以作为底层容器容器是否可作为 Stack 底层原因deque✅ 默认选择动态扩展内存布局合理性能均衡vector✅ 可选连续内存缓存友好但扩容时可能重分配list✅ 可选节点稳定不会使迭代器失效但内存开销大array❌ 不可用固定大小不支持动态增减默认选择deque的原因无需在栈顶预留空间不像vector那样可能频繁扩容内存碎片较少分配策略更高效支持 O(1) 的尾部操作2.3 模拟实现从零构建 MyStack我们将实现一个完整的MyStack类模板支持自定义底层容器标准接口异常安全移动语义cpp#include deque #include stdexcept namespace mystl { template typename T, typename Container std::dequeT class MyStack { 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; protected: container_type c; // 底层容器 public: // 构造与析构 // 默认构造调用底层容器的默认构造函数 MyStack() default; // 用指定容器构造 explicit MyStack(const container_type cont) : c(cont) {} explicit MyStack(container_type cont) : c(std::move(cont)) {} // 拷贝构造和移动构造由编译器生成即可 // 元素访问 // 返回栈顶元素的引用不检查是否为空 reference top() { return c.back(); } const_reference top() const { return c.back(); } // 容量操作 bool empty() const noexcept { return c.empty(); } size_type size() const noexcept { return c.size(); } // 修改操作 void push(const value_type value) { c.push_back(value); } void push(value_type value) { c.push_back(std::move(value)); } // 完美转发版本C11 及以上 template typename... Args void emplace(Args... args) { c.emplace_back(std::forwardArgs(args)...); } void pop() { // 注意标准库要求调用前非空这里按标准实现不做检查 c.pop_back(); } void swap(MyStack other) noexcept(noexcept(swap(c, other.c))) { using std::swap; swap(c, other.c); } // 关系操作符 friend bool operator(const MyStack lhs, const MyStack rhs) { return lhs.c rhs.c; } friend bool operator!(const MyStack lhs, const MyStack rhs) { return !(lhs rhs); } friend bool operator(const MyStack lhs, const MyStack rhs) { return lhs.c rhs.c; } // 其他关系操作符类似实现... }; // 非成员 swap template typename T, typename Container void swap(MyStackT, Container lhs, MyStackT, Container rhs) noexcept(noexcept(lhs.swap(rhs))) { lhs.swap(rhs); } } // namespace mystl2.4 完整代码与测试用例cpp#include iostream #include vector #include list int main() { // 测试默认 deque 版本 mystl::MyStackint s1; for (int i 1; i 5; i) { s1.push(i); } std::cout s1.top() s1.top() std::endl; // 5 std::cout s1.size() s1.size() std::endl; // 5 while (!s1.empty()) { std::cout s1.top() ; s1.pop(); } std::cout std::endl; // 5 4 3 2 1 // 测试 vector 作为底层 mystl::MyStackint, std::vectorint s2; s2.push(10); s2.push(20); std::cout s2.top() s2.top() std::endl; // 20 // 测试 emplace struct Point { int x, y; Point(int a, int b) : x(a), y(b) {} }; mystl::MyStackPoint s3; s3.emplace(3, 4); // 直接构造无需临时对象 std::cout Point: s3.top().x , s3.top().y std::endl; // 测试移动语义 std::vectorint vec{1, 2, 3}; mystl::MyStackint, std::vectorint s4(std::move(vec)); std::cout s4.size() s4.size() std::endl; // 3 return 0; }2.5 性能分析与复杂度保证操作复杂度说明push()O(1) 均摊底层容器的push_back可能触发扩容均摊 O(1)pop()O(1)仅删除尾部元素top()O(1)直接访问尾部size()O(1)容器通常维护 size 成员内存特性使用deque内存按块分配不会像vector那样在扩容时移动所有元素使用vector元素在内存中连续缓存命中率高但扩容时可能产生较大开销3. Queue 的深度剖析与模拟实现3.1 Queue 的核心概念与接口queue是一种先进先出FIFO, First In First Out的数据结构。其核心操作操作功能时间复杂度push()队尾插入元素O(1)pop()队首删除元素O(1)front()访问队首元素O(1)back()访问队尾元素O(1)empty()判断队列是否为空O(1)size()返回队列中元素数量O(1)3.2 底层容器的约束与优化queue的底层容器必须支持front()获取第一个元素back()获取最后一个元素push_back()在尾部添加元素pop_front()从头部删除元素满足这些要求的容器deque✅ 默认选择支持双向操作list✅ 可选但内存开销较大为什么不能用vectorvector没有pop_front()操作删除头部元素需要移动所有剩余元素时间复杂度 O(n)不符合队列的 O(1) 要求。3.3 模拟实现从零构建 MyQueuecpp#include deque #include list #include stdexcept namespace mystl { template typename T, typename Container std::dequeT class MyQueue { 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; protected: container_type c; public: // 构造 MyQueue() default; explicit MyQueue(const container_type cont) : c(cont) {} explicit MyQueue(container_type cont) : c(std::move(cont)) {} // 元素访问 reference front() { return c.front(); } const_reference front() const { return c.front(); } reference back() { return c.back(); } const_reference back() const { return c.back(); } // 容量 bool empty() const noexcept { return c.empty(); } size_type size() const noexcept { return c.size(); } // 修改 void push(const value_type value) { c.push_back(value); } void push(value_type value) { c.push_back(std::move(value)); } template typename... Args void emplace(Args... args) { c.emplace_back(std::forwardArgs(args)...); } void pop() { c.pop_front(); } void swap(MyQueue other) noexcept(noexcept(swap(c, other.c))) { using std::swap; swap(c, other.c); } // 关系操作符 friend bool operator(const MyQueue lhs, const MyQueue rhs) { return lhs.c rhs.c; } friend bool operator!(const MyQueue lhs, const MyQueue rhs) { return !(lhs rhs); } // ... 其他关系操作符 }; template typename T, typename Container void swap(MyQueueT, Container lhs, MyQueueT, Container rhs) noexcept(noexcept(lhs.swap(rhs))) { lhs.swap(rhs); } } // namespace mystl3.4 完整代码与测试用例cpp#include iostream int main() { // 基本测试 mystl::MyQueueint q1; for (int i 1; i 5; i) { q1.push(i); } std::cout front: q1.front() std::endl; // 1 std::cout back: q1.back() std::endl; // 5 std::cout size: q1.size() std::endl; // 5 while (!q1.empty()) { std::cout q1.front() ; q1.pop(); } std::cout std::endl; // 1 2 3 4 5 // 测试 list 作为底层 mystl::MyQueuestd::string, std::liststd::string q2; q2.push(Hello); q2.push(World); std::cout q2.front() q2.back() std::endl; // Hello World // 测试 emplace struct Person { std::string name; int age; Person(std::string n, int a) : name(std::move(n)), age(a) {} }; mystl::MyQueuePerson q3; q3.emplace(Alice, 30); q3.emplace(Bob, 25); std::cout q3.front().name : q3.front().age std::endl; // Alice: 30 // 测试移动构造 mystl::MyQueueint q4; q4.push(100); mystl::MyQueueint q5(std::move(q4)); std::cout q5.size() q5.size() std::endl; // 1 return 0; }3.5 双端队列 deque 的优势分析deque双端队列之所以成为stack和queue的默认底层容器是因为其独特的设计textdeque 的内存布局 ┌─────────┐ ┌─────────┐ ┌─────────┐ │ Block │ │ Block │ │ Block │ │ 0 │ │ 1 │ │ 2 │ └─────────┘ └─────────┘ └─────────┘ ↑ ↑ ↑ └───────────┴───────────┘ 中控数组deque 的核心特性分段连续内存数据存储在多个固定大小的块中通过中控数组管理O(1) 双端操作两端插入删除不需要移动元素无需整体扩容添加新块即可不会使所有元素失效迭代器复杂度较高相比vector迭代器更复杂但作为适配器底层这不影响性能对比总结操作vectordequelist尾部插入O(1) 均摊O(1)O(1)头部插入O(n)O(1)O(1)随机访问O(1)O(1)O(n)内存占用最小中等最大迭代器失效扩容时全失效插入两端不影响已有迭代器插入删除不影响其他对于stack只需要尾部操作vector在理论上也是一个好选择但deque避免了vector扩容时的元素拷贝开销。对于queue需要两端操作deque是最佳选择。4. 扩展与进阶4.1 自定义分配器支持现代 C 容器支持自定义分配器我们可以扩展实现cpptemplate typename T, typename Container std::dequeT, std::allocatorT class MyStack { // 上述实现已经通过 Container 间接支持了分配器 // 因为 std::deque 本身就支持分配器 }; // 使用自定义分配器示例 #include memory template typename T struct MyAllocator : std::allocatorT { // 自定义分配逻辑 }; mystl::MyStackint, std::dequeint, MyAllocatorint custom_stack;4.2 异常安全性与强异常保证我们的实现遵循了 STL 的异常安全级别操作异常安全保证push(const T)若拷贝抛出异常容器不变基本保证push(T)若移动抛出异常容器不变pop()不抛出异常若底层容器不抛top()不抛出异常emplace()若构造抛出异常容器不变强异常保证的实现技巧cppvoid push(const value_type value) { // 某些场景需要强异常保证可以这样实现 auto tmp value; // 先拷贝 c.push_back(std::move(tmp)); // 移动不会抛异常 }4.3 移动语义与完美转发我们在实现中已经充分利用了移动语义cppvoid push(value_type value) { c.push_back(std::move(value)); // 转移资源所有权 } template typename... Args void emplace(Args... args) { // 完美转发避免不必要的拷贝 c.emplace_back(std::forwardArgs(args)...); }性能影响移动语义避免了深拷贝尤其是对于std::string、std::vector等资源管理类emplace直接构造省去了临时对象的创建和销毁4.4 C11/17/20 标准演进对比特性C98C11C17C20移动语义❌✅✅✅完美转发❌✅✅✅emplace❌✅✅✅noexcept规范❌✅✅✅推导指引❌❌✅✅C17 的推导指引示例cpp// 类模板参数推导CTAD std::stack s1{std::dequeint{1,2,3}}; // C17 可推导类型5. 常见陷阱与最佳实践陷阱 1在空容器上调用 top()/front()cppstd::stackint s; s.top(); // 未定义行为最佳实践总是在调用前检查empty()cppif (!s.empty()) { auto val s.top(); }陷阱 2pop() 后使用失效的引用cppauto ref s.top(); s.pop(); ref; // 悬空引用已销毁的元素最佳实践在pop()前获取值或确保引用不再使用。陷阱 3期望随机访问cpp// 错误stack 不支持下标操作 // s[0]; // 编译错误 // 正确需要随机访问时使用 vector 或 deque陷阱 4底层容器的错误选择cpp// 错误queue 不能用 vector std::queueint, std::vectorint q; // 编译错误 // 正确使用 deque 或 list std::queueint, std::listint q;陷阱 5迭代器失效问题cppstd::stackint, std::vectorint s; s.push(1); auto top s.top(); s.push(2); // 可能触发 vector 扩容top 引用失效最佳实践总结默认使用默认容器大多数情况下deque是最佳选择优先使用 emplace避免不必要的临时对象注意异常安全在构造复杂对象时考虑emplace使用移动语义在合适的地方使用std::move自定义比较器需要改变顺序时考虑priority_queue6. 总结与思考设计亮点回顾适配器模式的应用stack和queue完美展示了如何通过组合现有容器来创建新的抽象体现了软件复用的思想。模板编程的威力通过模板参数用户可以根据需求自由选择底层容器实现零成本抽象。接口最小化原则只暴露必要的操作接口避免了不相关操作带来的误用风险。异常安全保证STL 设计者精心考虑了各种异常情况保证了基本的安全性和可预测性。与标准库的对比我们实现的MyStack和MyQueue与标准库版本在核心功能上完全一致但标准库还包含更完善的noexcept规范与容器库更紧密的集成针对特定编译器的优化性能考量场景推荐容器原因频繁 push/pop元素数量大deque避免扩容拷贝元素类型简单数量可控vector缓存友好需要稳定的迭代器list插入删除不影响其他元素需要优先级排序priority_queue堆实现思想延伸理解stack和queue的实现不仅能帮助我们更好地使用它们还能启发我们如何设计适配器类如何平衡抽象层次与性能如何通过组合而非继承实现复用如何提供灵活的类型参数化附录完整代码清单MyStack 完整实现cpp#ifndef MYSTACK_HPP #define MYSTACK_HPP #include deque #include utility namespace mystl { template typename T, typename Container std::dequeT class MyStack { 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; protected: container_type c; public: // 构造 MyStack() default; explicit MyStack(const container_type cont) : c(cont) {} explicit MyStack(container_type cont) : c(std::move(cont)) {} // 元素访问 reference top() { return c.back(); } const_reference top() const { return c.back(); } // 容量 bool empty() const noexcept { return c.empty(); } size_type size() const noexcept { return c.size(); } // 修改 void push(const value_type value) { c.push_back(value); } void push(value_type value) { c.push_back(std::move(value)); } template typename... Args void emplace(Args... args) { c.emplace_back(std::forwardArgs(args)...); } void pop() { c.pop_back(); } void swap(MyStack other) noexcept(noexcept(swap(c, other.c))) { using std::swap; swap(c, other.c); } // 关系操作符 friend bool operator(const MyStack lhs, const MyStack rhs) { return lhs.c rhs.c; } friend bool operator!(const MyStack lhs, const MyStack rhs) { return !(lhs rhs); } friend bool operator(const MyStack lhs, const MyStack rhs) { return lhs.c rhs.c; } }; template typename T, typename Container void swap(MyStackT, Container lhs, MyStackT, Container rhs) noexcept(noexcept(lhs.swap(rhs))) { lhs.swap(rhs); } } // namespace mystl #endif // MYSTACK_HPPMyQueue 完整实现cpp#ifndef MYQUEUE_HPP #define MYQUEUE_HPP #include deque #include utility namespace mystl { template typename T, typename Container std::dequeT class MyQueue { 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; protected: container_type c; public: // 构造 MyQueue() default; explicit MyQueue(const container_type cont) : c(cont) {} explicit MyQueue(container_type cont) : c(std::move(cont)) {} // 元素访问 reference front() { return c.front(); } const_reference front() const { return c.front(); } reference back() { return c.back(); } const_reference back() const { return c.back(); } // 容量 bool empty() const noexcept { return c.empty(); } size_type size() const noexcept { return c.size(); } // 修改 void push(const value_type value) { c.push_back(value); } void push(value_type value) { c.push_back(std::move(value)); } template typename... Args void emplace(Args... args) { c.emplace_back(std::forwardArgs(args)...); } void pop() { c.pop_front(); } void swap(MyQueue other) noexcept(noexcept(swap(c, other.c))) { using std::swap; swap(c, other.c); } // 关系操作符 friend bool operator(const MyQueue lhs, const MyQueue rhs) { return lhs.c rhs.c; } friend bool operator!(const MyQueue lhs, const MyQueue rhs) { return !(lhs rhs); } friend bool operator(const MyQueue lhs, const MyQueue rhs) { return lhs.c rhs.c; } }; template typename T, typename Container void swap(MyQueueT, Container lhs, MyQueueT, Container rhs) noexcept(noexcept(lhs.swap(rhs))) { lhs.swap(rhs); } } // namespace mystl #endif // MYQUEUE_HPP
STL：Stack和Queue的模拟实现——从原理到工业级代码的全方位解析
1. 引言容器适配器的设计哲学在 C STL 中stack和queue被设计为容器适配器而非完整的容器。这是一种经典的适配器模式在库设计中的体现。适配器模式将一个类的接口转换成客户希望的另一个接口。适配器模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。STL 的stack和queue并不自己管理内存或存储元素而是通过封装一个底层容器如deque、vector、list来提供特定的接口。这种设计的优势在于复用性复用现有容器的所有实现细节灵活性允许用户根据场景选择不同的底层容器关注点分离适配器只关心接口语义容器只关心存储性能2. Stack 的深度剖析与模拟实现2.1 Stack 的核心概念与接口stack是一种后进先出LIFO, Last In First Out的数据结构。其核心操作只有几个操作功能时间复杂度push()向栈顶插入元素O(1)pop()移除栈顶元素O(1)top()访问栈顶元素O(1)empty()判断栈是否为空O(1)size()返回栈中元素数量O(1)STL 标准要求stack提供以下成员类型value_type元素类型container_type底层容器类型size_type无符号整数类型2.2 底层容器的选择策略stack的底层容器必须支持以下操作back()获取最后一个元素作为栈顶push_back()在尾部添加元素pop_back()删除尾部元素任何满足这些要求的容器都可以作为底层容器容器是否可作为 Stack 底层原因deque✅ 默认选择动态扩展内存布局合理性能均衡vector✅ 可选连续内存缓存友好但扩容时可能重分配list✅ 可选节点稳定不会使迭代器失效但内存开销大array❌ 不可用固定大小不支持动态增减默认选择deque的原因无需在栈顶预留空间不像vector那样可能频繁扩容内存碎片较少分配策略更高效支持 O(1) 的尾部操作2.3 模拟实现从零构建 MyStack我们将实现一个完整的MyStack类模板支持自定义底层容器标准接口异常安全移动语义cpp#include deque #include stdexcept namespace mystl { template typename T, typename Container std::dequeT class MyStack { 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; protected: container_type c; // 底层容器 public: // 构造与析构 // 默认构造调用底层容器的默认构造函数 MyStack() default; // 用指定容器构造 explicit MyStack(const container_type cont) : c(cont) {} explicit MyStack(container_type cont) : c(std::move(cont)) {} // 拷贝构造和移动构造由编译器生成即可 // 元素访问 // 返回栈顶元素的引用不检查是否为空 reference top() { return c.back(); } const_reference top() const { return c.back(); } // 容量操作 bool empty() const noexcept { return c.empty(); } size_type size() const noexcept { return c.size(); } // 修改操作 void push(const value_type value) { c.push_back(value); } void push(value_type value) { c.push_back(std::move(value)); } // 完美转发版本C11 及以上 template typename... Args void emplace(Args... args) { c.emplace_back(std::forwardArgs(args)...); } void pop() { // 注意标准库要求调用前非空这里按标准实现不做检查 c.pop_back(); } void swap(MyStack other) noexcept(noexcept(swap(c, other.c))) { using std::swap; swap(c, other.c); } // 关系操作符 friend bool operator(const MyStack lhs, const MyStack rhs) { return lhs.c rhs.c; } friend bool operator!(const MyStack lhs, const MyStack rhs) { return !(lhs rhs); } friend bool operator(const MyStack lhs, const MyStack rhs) { return lhs.c rhs.c; } // 其他关系操作符类似实现... }; // 非成员 swap template typename T, typename Container void swap(MyStackT, Container lhs, MyStackT, Container rhs) noexcept(noexcept(lhs.swap(rhs))) { lhs.swap(rhs); } } // namespace mystl2.4 完整代码与测试用例cpp#include iostream #include vector #include list int main() { // 测试默认 deque 版本 mystl::MyStackint s1; for (int i 1; i 5; i) { s1.push(i); } std::cout s1.top() s1.top() std::endl; // 5 std::cout s1.size() s1.size() std::endl; // 5 while (!s1.empty()) { std::cout s1.top() ; s1.pop(); } std::cout std::endl; // 5 4 3 2 1 // 测试 vector 作为底层 mystl::MyStackint, std::vectorint s2; s2.push(10); s2.push(20); std::cout s2.top() s2.top() std::endl; // 20 // 测试 emplace struct Point { int x, y; Point(int a, int b) : x(a), y(b) {} }; mystl::MyStackPoint s3; s3.emplace(3, 4); // 直接构造无需临时对象 std::cout Point: s3.top().x , s3.top().y std::endl; // 测试移动语义 std::vectorint vec{1, 2, 3}; mystl::MyStackint, std::vectorint s4(std::move(vec)); std::cout s4.size() s4.size() std::endl; // 3 return 0; }2.5 性能分析与复杂度保证操作复杂度说明push()O(1) 均摊底层容器的push_back可能触发扩容均摊 O(1)pop()O(1)仅删除尾部元素top()O(1)直接访问尾部size()O(1)容器通常维护 size 成员内存特性使用deque内存按块分配不会像vector那样在扩容时移动所有元素使用vector元素在内存中连续缓存命中率高但扩容时可能产生较大开销3. Queue 的深度剖析与模拟实现3.1 Queue 的核心概念与接口queue是一种先进先出FIFO, First In First Out的数据结构。其核心操作操作功能时间复杂度push()队尾插入元素O(1)pop()队首删除元素O(1)front()访问队首元素O(1)back()访问队尾元素O(1)empty()判断队列是否为空O(1)size()返回队列中元素数量O(1)3.2 底层容器的约束与优化queue的底层容器必须支持front()获取第一个元素back()获取最后一个元素push_back()在尾部添加元素pop_front()从头部删除元素满足这些要求的容器deque✅ 默认选择支持双向操作list✅ 可选但内存开销较大为什么不能用vectorvector没有pop_front()操作删除头部元素需要移动所有剩余元素时间复杂度 O(n)不符合队列的 O(1) 要求。3.3 模拟实现从零构建 MyQueuecpp#include deque #include list #include stdexcept namespace mystl { template typename T, typename Container std::dequeT class MyQueue { 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; protected: container_type c; public: // 构造 MyQueue() default; explicit MyQueue(const container_type cont) : c(cont) {} explicit MyQueue(container_type cont) : c(std::move(cont)) {} // 元素访问 reference front() { return c.front(); } const_reference front() const { return c.front(); } reference back() { return c.back(); } const_reference back() const { return c.back(); } // 容量 bool empty() const noexcept { return c.empty(); } size_type size() const noexcept { return c.size(); } // 修改 void push(const value_type value) { c.push_back(value); } void push(value_type value) { c.push_back(std::move(value)); } template typename... Args void emplace(Args... args) { c.emplace_back(std::forwardArgs(args)...); } void pop() { c.pop_front(); } void swap(MyQueue other) noexcept(noexcept(swap(c, other.c))) { using std::swap; swap(c, other.c); } // 关系操作符 friend bool operator(const MyQueue lhs, const MyQueue rhs) { return lhs.c rhs.c; } friend bool operator!(const MyQueue lhs, const MyQueue rhs) { return !(lhs rhs); } // ... 其他关系操作符 }; template typename T, typename Container void swap(MyQueueT, Container lhs, MyQueueT, Container rhs) noexcept(noexcept(lhs.swap(rhs))) { lhs.swap(rhs); } } // namespace mystl3.4 完整代码与测试用例cpp#include iostream int main() { // 基本测试 mystl::MyQueueint q1; for (int i 1; i 5; i) { q1.push(i); } std::cout front: q1.front() std::endl; // 1 std::cout back: q1.back() std::endl; // 5 std::cout size: q1.size() std::endl; // 5 while (!q1.empty()) { std::cout q1.front() ; q1.pop(); } std::cout std::endl; // 1 2 3 4 5 // 测试 list 作为底层 mystl::MyQueuestd::string, std::liststd::string q2; q2.push(Hello); q2.push(World); std::cout q2.front() q2.back() std::endl; // Hello World // 测试 emplace struct Person { std::string name; int age; Person(std::string n, int a) : name(std::move(n)), age(a) {} }; mystl::MyQueuePerson q3; q3.emplace(Alice, 30); q3.emplace(Bob, 25); std::cout q3.front().name : q3.front().age std::endl; // Alice: 30 // 测试移动构造 mystl::MyQueueint q4; q4.push(100); mystl::MyQueueint q5(std::move(q4)); std::cout q5.size() q5.size() std::endl; // 1 return 0; }3.5 双端队列 deque 的优势分析deque双端队列之所以成为stack和queue的默认底层容器是因为其独特的设计textdeque 的内存布局 ┌─────────┐ ┌─────────┐ ┌─────────┐ │ Block │ │ Block │ │ Block │ │ 0 │ │ 1 │ │ 2 │ └─────────┘ └─────────┘ └─────────┘ ↑ ↑ ↑ └───────────┴───────────┘ 中控数组deque 的核心特性分段连续内存数据存储在多个固定大小的块中通过中控数组管理O(1) 双端操作两端插入删除不需要移动元素无需整体扩容添加新块即可不会使所有元素失效迭代器复杂度较高相比vector迭代器更复杂但作为适配器底层这不影响性能对比总结操作vectordequelist尾部插入O(1) 均摊O(1)O(1)头部插入O(n)O(1)O(1)随机访问O(1)O(1)O(n)内存占用最小中等最大迭代器失效扩容时全失效插入两端不影响已有迭代器插入删除不影响其他对于stack只需要尾部操作vector在理论上也是一个好选择但deque避免了vector扩容时的元素拷贝开销。对于queue需要两端操作deque是最佳选择。4. 扩展与进阶4.1 自定义分配器支持现代 C 容器支持自定义分配器我们可以扩展实现cpptemplate typename T, typename Container std::dequeT, std::allocatorT class MyStack { // 上述实现已经通过 Container 间接支持了分配器 // 因为 std::deque 本身就支持分配器 }; // 使用自定义分配器示例 #include memory template typename T struct MyAllocator : std::allocatorT { // 自定义分配逻辑 }; mystl::MyStackint, std::dequeint, MyAllocatorint custom_stack;4.2 异常安全性与强异常保证我们的实现遵循了 STL 的异常安全级别操作异常安全保证push(const T)若拷贝抛出异常容器不变基本保证push(T)若移动抛出异常容器不变pop()不抛出异常若底层容器不抛top()不抛出异常emplace()若构造抛出异常容器不变强异常保证的实现技巧cppvoid push(const value_type value) { // 某些场景需要强异常保证可以这样实现 auto tmp value; // 先拷贝 c.push_back(std::move(tmp)); // 移动不会抛异常 }4.3 移动语义与完美转发我们在实现中已经充分利用了移动语义cppvoid push(value_type value) { c.push_back(std::move(value)); // 转移资源所有权 } template typename... Args void emplace(Args... args) { // 完美转发避免不必要的拷贝 c.emplace_back(std::forwardArgs(args)...); }性能影响移动语义避免了深拷贝尤其是对于std::string、std::vector等资源管理类emplace直接构造省去了临时对象的创建和销毁4.4 C11/17/20 标准演进对比特性C98C11C17C20移动语义❌✅✅✅完美转发❌✅✅✅emplace❌✅✅✅noexcept规范❌✅✅✅推导指引❌❌✅✅C17 的推导指引示例cpp// 类模板参数推导CTAD std::stack s1{std::dequeint{1,2,3}}; // C17 可推导类型5. 常见陷阱与最佳实践陷阱 1在空容器上调用 top()/front()cppstd::stackint s; s.top(); // 未定义行为最佳实践总是在调用前检查empty()cppif (!s.empty()) { auto val s.top(); }陷阱 2pop() 后使用失效的引用cppauto ref s.top(); s.pop(); ref; // 悬空引用已销毁的元素最佳实践在pop()前获取值或确保引用不再使用。陷阱 3期望随机访问cpp// 错误stack 不支持下标操作 // s[0]; // 编译错误 // 正确需要随机访问时使用 vector 或 deque陷阱 4底层容器的错误选择cpp// 错误queue 不能用 vector std::queueint, std::vectorint q; // 编译错误 // 正确使用 deque 或 list std::queueint, std::listint q;陷阱 5迭代器失效问题cppstd::stackint, std::vectorint s; s.push(1); auto top s.top(); s.push(2); // 可能触发 vector 扩容top 引用失效最佳实践总结默认使用默认容器大多数情况下deque是最佳选择优先使用 emplace避免不必要的临时对象注意异常安全在构造复杂对象时考虑emplace使用移动语义在合适的地方使用std::move自定义比较器需要改变顺序时考虑priority_queue6. 总结与思考设计亮点回顾适配器模式的应用stack和queue完美展示了如何通过组合现有容器来创建新的抽象体现了软件复用的思想。模板编程的威力通过模板参数用户可以根据需求自由选择底层容器实现零成本抽象。接口最小化原则只暴露必要的操作接口避免了不相关操作带来的误用风险。异常安全保证STL 设计者精心考虑了各种异常情况保证了基本的安全性和可预测性。与标准库的对比我们实现的MyStack和MyQueue与标准库版本在核心功能上完全一致但标准库还包含更完善的noexcept规范与容器库更紧密的集成针对特定编译器的优化性能考量场景推荐容器原因频繁 push/pop元素数量大deque避免扩容拷贝元素类型简单数量可控vector缓存友好需要稳定的迭代器list插入删除不影响其他元素需要优先级排序priority_queue堆实现思想延伸理解stack和queue的实现不仅能帮助我们更好地使用它们还能启发我们如何设计适配器类如何平衡抽象层次与性能如何通过组合而非继承实现复用如何提供灵活的类型参数化附录完整代码清单MyStack 完整实现cpp#ifndef MYSTACK_HPP #define MYSTACK_HPP #include deque #include utility namespace mystl { template typename T, typename Container std::dequeT class MyStack { 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; protected: container_type c; public: // 构造 MyStack() default; explicit MyStack(const container_type cont) : c(cont) {} explicit MyStack(container_type cont) : c(std::move(cont)) {} // 元素访问 reference top() { return c.back(); } const_reference top() const { return c.back(); } // 容量 bool empty() const noexcept { return c.empty(); } size_type size() const noexcept { return c.size(); } // 修改 void push(const value_type value) { c.push_back(value); } void push(value_type value) { c.push_back(std::move(value)); } template typename... Args void emplace(Args... args) { c.emplace_back(std::forwardArgs(args)...); } void pop() { c.pop_back(); } void swap(MyStack other) noexcept(noexcept(swap(c, other.c))) { using std::swap; swap(c, other.c); } // 关系操作符 friend bool operator(const MyStack lhs, const MyStack rhs) { return lhs.c rhs.c; } friend bool operator!(const MyStack lhs, const MyStack rhs) { return !(lhs rhs); } friend bool operator(const MyStack lhs, const MyStack rhs) { return lhs.c rhs.c; } }; template typename T, typename Container void swap(MyStackT, Container lhs, MyStackT, Container rhs) noexcept(noexcept(lhs.swap(rhs))) { lhs.swap(rhs); } } // namespace mystl #endif // MYSTACK_HPPMyQueue 完整实现cpp#ifndef MYQUEUE_HPP #define MYQUEUE_HPP #include deque #include utility namespace mystl { template typename T, typename Container std::dequeT class MyQueue { 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; protected: container_type c; public: // 构造 MyQueue() default; explicit MyQueue(const container_type cont) : c(cont) {} explicit MyQueue(container_type cont) : c(std::move(cont)) {} // 元素访问 reference front() { return c.front(); } const_reference front() const { return c.front(); } reference back() { return c.back(); } const_reference back() const { return c.back(); } // 容量 bool empty() const noexcept { return c.empty(); } size_type size() const noexcept { return c.size(); } // 修改 void push(const value_type value) { c.push_back(value); } void push(value_type value) { c.push_back(std::move(value)); } template typename... Args void emplace(Args... args) { c.emplace_back(std::forwardArgs(args)...); } void pop() { c.pop_front(); } void swap(MyQueue other) noexcept(noexcept(swap(c, other.c))) { using std::swap; swap(c, other.c); } // 关系操作符 friend bool operator(const MyQueue lhs, const MyQueue rhs) { return lhs.c rhs.c; } friend bool operator!(const MyQueue lhs, const MyQueue rhs) { return !(lhs rhs); } friend bool operator(const MyQueue lhs, const MyQueue rhs) { return lhs.c rhs.c; } }; template typename T, typename Container void swap(MyQueueT, Container lhs, MyQueueT, Container rhs) noexcept(noexcept(lhs.swap(rhs))) { lhs.swap(rhs); } } // namespace mystl #endif // MYQUEUE_HPP
