C++ 的容器适配器——从stack/queue看

STL 中的stack和queue并不是独立新建的容器类，而是“容器适配器”：对底层容器接口的一层封装（包装），把底层容器暴露的接口变成特定的“栈/队列”接口。
默认情况下，STL 的stack和queue使用deque作为底层容器，因为deque在头尾操作和随机访问之间提供了折中性能。

什么是容器适配器

适配器的作用是“将一个类的接口转换为客户希望的另一个接口”。
stack：只允许在一端插入/删除；queue：允许在一端入、一端出（FIFO）。
适配器并不自己管理内存，而是复用底层容器（deque,vector,list等）。

三种常见底层容器比较

• vector
  • 优点：尾插尾删高效、连续内存、随机访问 O(1)。
  • 缺点：头插或中间插入删除代价高（O(n)），扩容涉及复制/移动。
• list（双向链表）
  • 优点：任意位置插入/删除 O(1)（在已定位位置），不需要连续内存。
  • 缺点：不支持随机访问，内存开销大，缓存局部性差。
• deque
  • 优点：头尾插入均高效、支持下标访问（不是完全连续但接近），适合做stack/queue默认容器。
  • 缺点：中间插入删除依然 O(n)。

复杂度速览（常见操作）

• push_back / pop_back：vectorO(1) 摇摆（扩容摊销）、dequeO(1)、listO(1)
• push_front / pop_front：dequeO(1)、listO(1)、vectorO(n)
• 随机访问：vectorO(1)、deque接近 O(1)、listO(n)

实现stack适配器要点与常见错误

• 模板默认参数：注意template<class T, class Container = deque<T>>
• 成员函数的const与noexcept：比如top()、size()、empty()应该标记为const（不改变对象状态），size()/empty()可标记noexcept。
• top()返回引用：应返回const T&或T&取决于用途，通常提供const版本和非常量版本。
• 异常与未定义行为：对空栈调用top()/pop()是未定义行为（与 STL 一致）；可以在包装层增加断言或抛出异常以增强调试信息。
• 成员别名：提供using container_type = Container; using value_type = T;有助于与 STL 接口兼容。

改进后的stack参考实现

namespacesqtque{// 用 Container 适配转换出 stacktemplate<classT,classContainer=std::deque<T>>classstack{public:usingvalue_type=T;usingcontainer_type=Container;usingsize_type=std::size_t;// 默认构造 / 析构由底层容器负责voidpush(constT&x){_con.push_back(x);}voidpush(T&&x){_con.push_back(std::move(x));}voidpop(){assert(!empty()&&"pop on empty stack");_con.pop_back();}T&top(){assert(!empty()&&"top on empty stack");return_con.back();}constT&top()const{assert(!empty()&&"top on empty stack");return_con.back();}size_typesize()constnoexcept{return_con.size();}boolempty()constnoexcept{return_con.empty();}private:Container _con;// 封装出一个容器};}

使用示例

#include<iostream>#include<vector>intmain(){sqtque::stack<int>s;// 默认使用 deque<int>s.push(1);s.push(2);std::cout<<s.top()<<'\n';// 2s.pop();std::cout<<s.top()<<'\n';// 1// 使用 vector 作为底层容器（可行，但 vector 不支持 push_front）sqtque::stack<int,std::vector<int>>sv;sv.push(10);std::cout<<sv.top()<<'\n';return0;}

容易踩的坑

• top()/pop()在空容器上未定义行为，最好在调试或库接口中显式检查或断言。
• 若要与标准std::stack完全兼容，考虑添加构造重载（接受容器参数）和访问底层容器的成员函数（如c()）。
• 性能权衡：如果你只在尾部操作并且需要最高速的随机访问，用vector；若需要稳定的头尾 O(1)，用deque；若频繁在中间插入删除且已持有迭代器，考虑list。

结语

理解容器适配器的核心在于“接口的封装”和“底层容器的选择”。实现时应注意模板默认参数写法、成员函数的 const/ noexcept 语义与空容器的边界条件。通过上述改进可以让自实现的stack更安全、更 STL 风格、更易于扩展。