STL容器性能探秘：stack、queue、deque的实现与CPU缓存命中率优化-洪萨配资

前言

大家好啊，我是云泽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::stack<int, vector< int >>），但如果场景变了：

比如需要 “频繁在栈顶插入 / 删除，且不想承担vector扩容的开销”—— 只需要把模板参数换成list< int >，代码改成：

yunze::stack<int,list<int>>st;// 底层变成链表，其他代码完全不用改st.push(1);// 还是用同样的push接口st.top();// 还是用同样的top接口

底层容器换了，但栈的调用代码完全不用改—— 因为stack封装了统一的接口，不管底层是vector还是list，对外都是 “栈的操作”。

【统一接口】不用关心底层实现，只用记 “栈的用法”
不管底层是vector（数组）还是list（链表），你用这个stack时，只需要调用push/pop/top—— 不用关心底层是 “数组尾插” 还是 “链表尾插”，也不用记vector的push_back或list的push_back细节，只需要记 “栈的标准操作” 即可，降低了学习和使用的成本。
【稳定可靠】借现有容器的成熟性，减少 bug
STL 里的vector/list是经过大量测试、优化的容器，比自己写的 “数组栈”（比如注释里的T* _a）更稳定：

比如vector的扩容逻辑是经过性能优化的（通常是 2 倍扩容，减少频繁申请内存的开销）；
list的尾插 / 尾删是 O (1) 且不会有内存碎片问题；
这些容器本身也做了边界检查（比如empty()时调用back()会报错）。
用它们作为底层，比自己手写的存储结构更不容易出 bug。

【适配多类型】底层容器支持的类型，栈都能直接用
比如你想存string类型的栈，只需要写：

yunze::stack<string,vector<string>>st;st.push("hello");cout<<st.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（双端队列）：是一种双开口的“连续”空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O（1），也可以在中间任意位置插入删除，与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缓存知识