厦门路桥建设集团有限公司网站wordpress相关文章

厦门路桥建设集团有限公司网站,wordpress相关文章,wordpress自带搜索引擎,重庆市建设工程信息网中标公告STL 中的 stack 和 queue 并不是独立新建的容器类#xff0c;而是“容器适配器”#xff1a;对底层容器接口的一层封装#xff08;包装#xff09;#xff0c;把底层容器暴露的接口变成特定的“栈/队列”接口。 默认情况下#xff0c;STL 的 stack 和 queue 使用 deque 作…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_backvectorO(1) 摇摆扩容摊销、dequeO(1)、listO(1)push_front / pop_frontdequeO(1)、listO(1)、vectorO(n)随机访问vectorO(1)、deque接近 O(1)、listO(n)实现stack适配器要点与常见错误模板默认参数注意templateclass T, class Container dequeT成员函数的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 适配转换出 stacktemplateclassT,classContainerstd::dequeTclassstack{public:usingvalue_typeT;usingcontainer_typeContainer;usingsize_typestd::size_t;// 默认构造 / 析构由底层容器负责voidpush(constTx){_con.push_back(x);}voidpush(Tx){_con.push_back(std::move(x));}voidpop(){assert(!empty()pop on empty stack);_con.pop_back();}Ttop(){assert(!empty()top on empty stack);return_con.back();}constTtop()const{assert(!empty()top on empty stack);return_con.back();}size_typesize()constnoexcept{return_con.size();}boolempty()constnoexcept{return_con.empty();}private:Container _con;// 封装出一个容器};}使用示例#includeiostream#includevectorintmain(){sqtque::stackints;// 默认使用 dequeints.push(1);s.push(2);std::couts.top()\n;// 2s.pop();std::couts.top()\n;// 1// 使用 vector 作为底层容器可行但 vector 不支持 push_frontsqtque::stackint,std::vectorintsv;sv.push(10);std::coutsv.top()\n;return0;}容易踩的坑top()/pop()在空容器上未定义行为最好在调试或库接口中显式检查或断言。若要与标准std::stack完全兼容考虑添加构造重载接受容器参数和访问底层容器的成员函数如c()。性能权衡如果你只在尾部操作并且需要最高速的随机访问用vector若需要稳定的头尾 O(1)用deque若频繁在中间插入删除且已持有迭代器考虑list。结语理解容器适配器的核心在于“接口的封装”和“底层容器的选择”。实现时应注意模板默认参数写法、成员函数的 const/ noexcept 语义与空容器的边界条件。通过上述改进可以让自实现的stack更安全、更 STL 风格、更易于扩展。