玉林做网站公司校园网络设计方案

玉林做网站公司,校园网络设计方案,重庆装饰公司,北京网页设计平台目录前言一、stack的模拟实现1.1 适配器Container的封装概念二、queue的模拟实现三、deque的介绍3.1 deque的使用3.2 CPU高速缓存访问命中率与数据访问效率3.2.1 数据访问效率3.2.2 CPU高速缓存访问命中率结语#x1f3ac; 云泽Q#xff1a;个人主页#x1f525; 专栏传送入…目录前言一、stack的模拟实现1.1 适配器Container的封装概念二、queue的模拟实现三、deque的介绍3.1 deque的使用3.2 CPU高速缓存访问命中率与数据访问效率3.2.1 数据访问效率3.2.2 CPU高速缓存访问命中率结语 云泽Q个人主页 专栏传送入口: 《C语言》《数据结构》《C》《Linux》《蓝桥杯系列》⛺️遇见安然遇见你不负代码不负卿~前言大家好啊我是云泽Q欢迎阅读我的文章一名热爱计算机技术的在校大学生喜欢在课余时间做一些计算机技术的总结性文章希望我的文章能为你解答困惑~一、stack的模拟实现对于一般人来说模拟实现的栈的底层就是一个数组让数组尾部做栈顶。无论是数组栈还是链式栈很多的东西都是和顺序表和链表是类似的但是STL中的栈不是这样实现的STL在设计初的考量就是相似的一些东西直接复用像实现一个数组栈直接如图封装一个vector实现就不用再实现顺序表和链表的内部的一些逻辑了。1.1 适配器Container的封装概念且C设计STL的这些大佬的思路还更开阔一些他们还加入了一种叫做容器适配器Container转换的意思的东西这样封装适配器的思路是非常牛的“自己从头实现栈” 的写法比如注释里的T* _a_top_capacity—— 需要自己管理动态数组的扩容、释放而现在这个stack是“复用现有容器比如vector/list的功能包装成栈的接口”底层存储完全交给Container比如vector自己只封装 “栈需要的操作”push/pop/top 等。这种适配结构的核心优点【少写重复代码】复用现有容器不用自己实现底层存储原来注释里的 “数组栈” 需要自己写动态数组的初始化、扩容比如_capacity满了要realloc内存的释放防止内存泄漏下标访问、边界检查等。而现在的stack直接用vector/list作为底层容器 —— 这些容器本身已经实现了动态扩容、内存管理、尾插 / 尾删等功能你只需要调用_con.push_back()/_con.pop_back()相当于 “站在现有容器的肩膀上”不用重复造轮子。【灵活切换场景】换底层容器只改模板参数不用动栈的逻辑代码里用的是vector int 作为底层yunze::stackint, vector int 但如果场景变了比如需要 “频繁在栈顶插入 / 删除且不想承担vector扩容的开销”—— 只需要把模板参数换成list int 代码改成yunze::stackint,listintst;// 底层变成链表其他代码完全不用改st.push(1);// 还是用同样的push接口st.top();// 还是用同样的top接口底层容器换了但栈的调用代码完全不用改—— 因为stack封装了统一的接口不管底层是vector还是list对外都是 “栈的操作”。【统一接口】不用关心底层实现只用记 “栈的用法”不管底层是vector数组还是list链表你用这个stack时只需要调用push/pop/top—— 不用关心底层是 “数组尾插” 还是 “链表尾插”也不用记vector的push_back或list的push_back细节只需要记 “栈的标准操作” 即可降低了学习和使用的成本。【稳定可靠】借现有容器的成熟性减少 bugSTL 里的vector/list是经过大量测试、优化的容器比自己写的 “数组栈”比如注释里的T* _a更稳定比如vector的扩容逻辑是经过性能优化的通常是 2 倍扩容减少频繁申请内存的开销list的尾插 / 尾删是 O (1) 且不会有内存碎片问题这些容器本身也做了边界检查比如empty()时调用back()会报错。用它们作为底层比自己手写的存储结构更不容易出 bug。【适配多类型】底层容器支持的类型栈都能直接用比如你想存string类型的栈只需要写yunze::stackstring,vectorstringst;st.push(hello);coutst.top()endl;// 输出hello因为vector string 本身支持string类型你的stack不需要额外写任何代码直接适配所有Container支持的类型。看到这里可能看着该全新的写法还有一些疑问下面再看一下具体的模板参数实例化和函数调用过程库中的STL还支持使用缺省参数deque一个容器deque既不是一个数组栈也不是一个链式栈而是一个双端队列适配出来的栈双端队列不要求先进先出其在功能上是list和vector的融合体二、queue的模拟实现队列是队尾入数据队头出数据也可以在queue的类中用erase代替pop_front();vector不支持直接头删但是erase是支持头删的但是这就让效率强行降低了STL中的vector设计之初没有直接支持头删接口的原因就是希望少用功能上还是支持的voidpop(){_con.erase();}三、deque的介绍deque双端队列是一种双开口的“连续”空间的数据结构双开口的含义是可以在头尾两端进行插入和删除操作且时间复杂度为O1也可以在中间任意位置插入删除与vector比较头插效率高不需要搬移元素与list比较空间利用率比较高其在功能上是list和vector的融合体接口和list和vector的接口都基本是类似的3.1 deque的使用仅管从功能上看deque好像可以替代vector和list但是在实际情况下是不可以的如果可以的话STL就没有vector和list两个容器了deque更像是一个有着很好的设计初衷为了解决vector和list的问题但实际成品没有达到预期的一个容器但是其也有很多可取之处下图是vector和list的优缺点3.2 CPU高速缓存访问命中率与数据访问效率3.2.1 数据访问效率CPU高速缓存访问命中率高间接的也就是说数据访问效率高反之。该优缺点在归并排序和快速排序的性能测试尤其体现这里的性能测试该篇文章有写C List 容器详解迭代器失效、排序与高效操作这里上面打错了是100w个数据的数组。排序的性能差异就是由于数据的访问效率低排序的过程就要对数据结构中的数据进行大量的访问和交换数据越多这个差异就体现出来了3.2.2 CPU高速缓存访问命中率下面说一下CPU高速缓存访问命中率这个概念一、计算机存储介质的层级特性计算机的存储体系核心是“速度越快→容量越小→成本越高”的层级设计从慢到快、从大到小分为硬盘永久存储介质断电数据不丢失容量极大几百 GB~ 数 TB但访问速度最慢毫秒级。程序 / 文件的持久化存储依赖硬盘读取硬盘数据时需先将数据加载到内存中才能被 CPU 访问内存临时存储介质断电数据丢失容量适中8GB/16GB/32GB 为主访问速度远快于硬盘几十纳秒级但仍慢于 CPU 运算速度。所有运行中的程序、数据结构如 vector/list的实际数据都存储在内存中CPU 缓存L1/L2/L3介于内存和寄存器之间的高速存储容量远小于内存L1 几十 KB、L2 几百 KB、L3 几 MB~ 几十 MB访问速度是内存的 10~100 倍纳秒级寄存器CPU 内部的超高速存储几字节几十字节速度最快亚纳秒级但容量极小仅能存储 CPU 运算时的临时数据如 操作的中间值。还有专门写该部分原理的博客程序员相关的CPU缓存知识结语