💪 今日博客励志语录：
石头能被水滴穿，不是因为水有多强，而是因为它从未停过。
★★★ 本文前置知识：
模版
栈
那么栈这个数据结构相比大家已经十分熟悉，那么栈是一个后进先出的数据结构，那么在c语言期间，我们实现在栈这个数据结构采取的方式就是用数组的方式来实现，因为数组中有效数据的末尾就可以作为栈顶，那么数组的尾插以及尾删不需要挪动元素，时间复杂度是O(1)，所以数组就天然适配栈这个数据结构的底层实现，那么我们再定义一个结构体其中封装三个成员变量，分别是一个指针指向该动态数组的首元素的地址以及一个栈顶指针追踪栈顶位置和记录当前数组最大容量的变量以便扩容，然后再定义栈的初始化以及压栈和入栈的函数，所以知道在c语言期间栈的实现之后，那么我们c++可以同样模拟c语言的实现方式，底层维护一个数组，然后定义三个成员变量，也就是三个迭代器本质就是三个原生指针，指向该数组的首元素以及有效数据末尾和数组的末尾，来维护一个动态数组，然后再定义相关的构造函数以及入栈push以及出栈pop成员函数，但是我们其实在仔细思考观察一下我们刚才的实现方式，我们发现按照刚才的实现方式，定义三个迭代器维护一个动态数组，然后再定义相关比如empty和size和push函数，那么这些成员变量和成员函数其实和我们之前学过的vector的功能是高度重合，不能说完全相等只能说一模一样
那么自从我们学习完c++的模版之后，那么此时我们用c++编程的其中一个核心思想就是能不用自己造轮子就尽量不造，那么编译器有了模版可以根据类型不管是自定义类型还是内置类型，只有你提供了相关的定义，那么编译器都能来实例化出相应的类或者函数，所以这里我们我们就可以采取一个容器适配器模式来实现我们的栈
那么所谓的容器适配器的思想就是我们除了定义一个代表容器中存储数据类型的模版参数，还定义另一个模版参数，那么该模版参数就是容器的类型，因为到时候我们可以在栈的模版类中定义一个自定义类型的成员变量，那么该自定义类型就对应某个容器类型因为容器本质上就是一个自定义类型，例如vector< T >或者list< T >
所以我们先可以这样实现：
template<typename T,typename container>
class stack
{
private:
container _con;
};
那么接下来便是栈的成员函数：
成员函数
那么第一个想到的成员函数一定是构造函数，那么栈这里是否需要我们显示定义构造函数了，那么构造函数就是初始化成员变量，那么我们知道这里采取了容器适配器模式，所以我们采取的容器本身就有对应的默认构造函数，那么这里就无需我们自己手动编写构造函数
拷贝构造函数
那么栈有拷贝构造函数，那么拷贝构造函数就是接受一个已经初始化的栈对象来初始化还未初始化的栈对象，
那么这里的实现原理就是就是这里我们直接将初始化的栈对象赋值给该还未初始化的栈对象，那么由于对应的容器本身一定有对应的赋值运算符重载函数，那么其中一定实现了深拷贝，所以我们直接赋值即可，不用担心浅拷贝问题
stack(const stack<T,container>& l1)
{
_con = l1._con;
}
top函数
那么这里的top函数就是返回栈顶元素，那么我们栈顶元素就是位于容器的首部，那么这个时候就体现出stl的规范化的好处了，那么stl对其中的所有容器的成员函数的命名以及种类进行了规定与统一，那么这些容器都能够支持size函数以及empty函数等，这也为我们为什么能够采取容器适配器做了一个铺垫，也就是我们直接可以进行函数的复用，那么这里我们直接复用容器的front函数，得到首元素的值，然后返回
const T& top()
{
return _con.front();
}
push函数
那么push函数就是在栈尾部插入元素，那么这里我们就只需要调用容器内自带的push_back函数了，那么list以及vector以及包括我们之后讲的deque都有push_back函数的实现，那么这里deque先埋下一个伏笔
void push(const T& val)
{
_con.push_back(val);
}
pop函数
那么pop函数就是弹出栈顶元素，那么我们就复用容器的pop_back函数即可
void pop()
{
_con.pop_back();
}
empty函数
empty函数同样是复用容器内的empty函数
bool empty()
{
return _con.empty();
}
size函数
那么size函数复用容器提供的size函数
size_t size()
{
return _con.size();
}
swap函数
那么swap函数就是我们调用库里面的为我们提供的swap函数，交换对象的成员变量即可
void swap( stack<T, container>& l1)
{
std::swap(_con,l1._con);
}
那么这就是栈的全部实现包含成员函数以及成员变量，那么我们其实发现，栈的实现跟前面我们实现的list和vector相比，那简直要简单不少，简直就是奖励关，那么之所以容易实现该容器，还是感谢c++的模版能够让我们不用再自己造轮子
源码
#pragma once
#include<algorithm>
namespace wz
{
template<typename T,typename container>
class stack
{
private:
container _con;
public:
stack()
:_con()
{
}
stack(const stack<T,container>& l1)
{
_con = l1._con;
}
const T& top()
{
return _con.front();
}
void push(const T& val)
{
_con.push_back(val);
}
size_t size()
{
return _con.size();
}
void pop()
{
_con.pop_back();
}
bool empty()
{
return _con.empty();
}
void swap( stack<T, container>& l1)
{
std::swap(_con,l1._con);
}
};
}
#include"stack.h"
#include<iostream>
#include<vector>
using std::cout;
using std::endl;
int main()
{
wz::stack<int, std::vector<int>> l1;
l1.push(1);
l1.push(2);
l1.push(100);
l1.push(400);
l1.pop();
cout << l1.top() << endl;
l1.pop();
cout << "size: " << l1.size() << endl;
l1.pop();
wz::stack<int, std::vector<int>> l2;
l2.swap(l1);
l2.pop();
if (l2.empty())
{
cout << "stack is empty" << endl;
}
return 0;
}
运行截图：
那么在了解完以及模拟实现了栈之后，那么其实大家普遍会采取vector作为栈的默认容器，但是c++的stl的设计者却选择了另一个容器，那么其便是deque，那么选择使用deque一定有它的原因，那么在讲解c++的stl的设计者为什么选择deque之前，那么我们先来认识一下什么是deque
deque
那么接下来我们就来认识一下我们的deque，那么看看我们的deque相比与我们的list和vector有什么特别之处
那么deque也被称之为双端队列，那么之所以被称之为双端队列，那么我们也能从deque为我们提供的接口能够看出它为什么取这个名字，那么deque既为我们提供了push_front和pop_front成员函数，同时也有尾插和尾删的成员函数，那么相比于vector，那么vector就没有提供头插与头删的接口，虽然vector能够做到头插与头删，但是我们知道对于数组来说，头插与头删要移动大量的元素，那么效率不高，所以这也就是为什么vector没有提供头插与头删的原因，那么如果有头插和头删的需求，那么明显list是更好的选择，因为list的头插与头删的时间复杂度都是o(1)级别，那么就是因为list只需要修改节点之间的链接关系，同理对于尾插以及尾删也是一样，所以list提供了头插和头删以及尾插和尾删的成员函数
那么这里deque和list同样也提供了头插头删和尾插尾删，那么只能说明，对于deque来说，那么其头插和头删以及尾插和尾删的效率一样优秀，所以才可以提供，那么就意味着deque和list的结构是相似但是肯定是不完全相同的
而事实上deque的底层结构确实类似于链表，那么deque存储的数据是分布在一个一个物理内存不连续的节点中的，但是与链表不同的是，那么链表的每一个节点只能存储一个元素，并且节点内部还存储了前驱以及后继节点的指针，但是对于deque来说，那么deque中的每一个节点是一个数据块或者更为准确的来说，是一个动态数组，那么该数组存储的不只有一个元素而是有多个元素，但是它却没有额外存储其前驱数据块以及后继数据块的指针，而这些一个个动态数组在物理内存中又并不连续，那么如何来定位访问到这一个个的数据块呢？
所以这里deque还准备了一个中控数组，那么所谓的中控数组，本质上就是一个指针数组，那么说到这里，想必各位读者也一定大概知道或者猜到该数组的作用了，那么该指针数组中每一个元素是一个指针，其中指向的就是对应数据块的首元素，那么定位这些数据块就是通过中控数组来访问到这些数据块了
那么看到这里，想必读者心里大概有一个疑问：
第一个疑问就是为什么它要这么设计，也就是每一个节点是一个数据块也就是一个数组，为什么不只能是一个节点存储一个元素？
第二个疑问是deque如何实现这个结构？
那么要解释第一个问题，那么仅仅站在语言的角度是无法回答的，那么这个问题就得涉及到一点计算机组成原理的知识，那么我们知道CPU在运行我们的代码，我们代码中涉及到的各种数据，比如两个int类型的数相加，那么这两个int类型的数据都是存储在内存当中的，那么CPU在进行这些算术运算的时候，首先要做的就是访问内存，到内存中取出数据，那么CPU会通过地址线告诉内存我要的目标数据的地址，然后内存根据该地址定位到数据然后取走交给CPU
说到这里，我这里想问读者一个问题，此时你认为内存取走该数据时，比如在该场景下，CPU给了内存我要的int类型的变量a在内存中的地址，那么此时你觉得内存的行为是什么，是只仅仅取走该int类型的a变量的数据即可还是说不仅仅只是单单取该目标数据数据
那么有些读者如果认为只是单单取走该i目标数据也就是该int类型的a变量，那么说明对硬件还是不够了解，那么这里会涉及到计组的知识，那么我们就可以简单理解为访问内存其实是有成本或者说代价的，那么假设存在这么一个场景，就是我们遍历一个数组，写了一个for循环，循环n次，读取数组中的每一个元素，那么按照刚才的方式，那么意味着CPU要访问n次内存，那么访问内存是具有代价的，那么这样就到导致效率低下，所以事实上内存的行为是不仅仅取走该目标数据，同时还会取走目标数据周围相邻的数据，总共64字节然后后上传到CPU的缓存中，那么这样做的目的根据刚才的场景我们就可以得知，那么假设我们CPU访问完了一个数据，那么有可能下一个数据就在该数据的周围，比如刚才场景中，遍历访问数组中的元素，而CPU的行为，它不会先访问内存，而是优先访问缓存，因为访问缓存的速度是比内存要快很多的，如果缓存没有再去内存中访问，那么在刚才的场景下，如果遍历一个数组，那么从内存中取出该数组的第一个元素后，那么内存还会取出该数据相邻的元素，那么意味着可能直接把整个数组都从内存中取出放到缓存，那么接着CPU访问了一次内存，那么下一次访问的时候，先访问缓存，发现缓存有，就直接读取缓存中的数据，那么意味着遍历该数组，实际上可能只需要一次内存的访问。
所以这就引出了数组的好处，那么就是CPU的缓存命中率高，想必有的读者一定听过该名词就是缓存命中率，所以假设我们访问完deque的某个数据块中的某个元素，那么该元素所在的整个数据块会被加载进缓存中，那么如果下一次访问的元素还在数据块，那么CPU就可以直接去缓存快速定位，就不需要访问内存，而如果没有就大不了再访问一次内存，如果在，那么对于CPU就是赚了，这就就是为什么deque选择这么设计的原因，目的就是可以提高CPU的缓存命中率
那么关于第二个疑问，那么deque是如何实现的，那么deque内部首先会维护4个成员变量，分别是两个迭代器以及一个指向该指针数组的首元素地址的二级指针和指针数组的当前的容量，而这两个迭代器分别是start和end，那么这两个迭代器会指向有效数据的起始位置和结束位置，那么deque迭代器的构造相比于之前学的vector和list来说，那么就较为复杂
template <class T>
class deque {
private:
Iterator _start; // 第一个有效元素所在数据块的迭代器
Iterator _finish; // 最后一个有效元素的后继位置迭代器
T** _map; // 中控数组（二级指针）
size_t _map_size; // 中控数组容量
};
那么对于deque来说，那么它的迭代器内部封装了4个原生指针分别是first和end和cur和next，那么我们知道deque存储数据的节点是一个动态数组，那么这里每一个数组的大小都是固定的，那么首先这里deque的first指针就是指向该数组的起始位置，而last则是指向该数组的最后一个位置的下一个位置，还有一个cur指针则是用来定位以及变量该数据块的元素，而第四个node指针，则是保存当前数据块的在指针数组中的地址
template <class T>
struct _deque_iterator {
T* _first; // 当前数据块起始地址
T* _last; // 当前数据块末尾的下一个地址（边界）
T* _cur; // 当前指向的元素位置
T** _node; // 指向中控数组中当前块的指针（用于跨块跳转）
// 关键操作示例：operator++（后置）
_deque_iterator& operator++() {
++_cur;
if (_cur == _last) { // 到达当前块末尾
// 切换到下一数据块
++_node; // _node移动到中控数组下一项
_first = *_node; // 更新新块的起始地址
_last = _first + _block_size; // 更新新块边界
_cur = _first; // 指向新块首元素
}
return *this;
}
};
那么在介绍完deque的迭代器的构造后，那么我们再来认识一下deque的各个相关操作的成员函数，那么首先就是构造函数，那么deque的构造函数，默认的构造函数就是将两个迭代器给置为nullptr以及一个指向指针数组的指针置空也就是这是一个空的双端队列，那么带参的构造函数则是支持初始化设置n个元素并且带有初始值
默认：
deque() :
_start(nullptr, nullptr, nullptr, nullptr),
_finish(nullptr, nullptr, nullptr, nullptr),
_map(nullptr),
_map_size(0) {}
那么带参数的构造函数的实现原理，就是先初始化指针数组，开辟一定的大小的指针数组，那么接下来的一个细节就很关键，那么就是deque的插入的第一个元素的位置，很多读者会很自然的觉得插入的位置就在指针数组下标为0所指向的第一个数据块的首元素，但是我们再看来审视一下这种方式，如果你的下一步操作是在前面再插入一个元素也就是头插，那么必定就会涉及到扩容，因为前面没有数据块了，所以对于deque，它第一个插入的元素的位置是设置在指针数组中间位置的数据块中的中间位置，那么仔细品味一下，那么之所以设置在这，那么就是为了便于头插和尾插，减少扩容的次数
那么假设指针数组的长度为k，那么就在k/2位置处开辟一个固定大小假设为n长度的数据块，在该数据块的n/2位置处插入，然后初始化start和end指针，那么上文说过迭代器内部有4个指针，那么此时start迭代器中的这封装的4个指针，其中的first会指向该k/2位置处指向的数据块的起始位置，然后last会指向该k/2指向的数据块的结束位置，然后cur则是指向当前该数据块的n/2位置处，next则是保存当前数据块的在指针数组中的地址，同理last初始化也是一样，只不过其cur指针指向的是(n+1)/2位置处，因为start和end维护的右下数据的区间是左闭右开的[start,end],然后依次向后尾插，也就是调用push_back函数
deque(size_type n, const T& value = T()) {
// 1. 初始化中控数组（预留对称空间）
_map_size = std::max(8, n * 2); // 最小保证8个指针位
_map = _alloc_map(_map_size);
// 2. 计算中心位置（关键！）
size_t map_mid = _map_size / 2;
size_t block_mid = _block_size / 2;
// 3. 创建首个数据块并挂载到中心位置
T* new_block = _alloc_block();
_map[map_mid] = new_block;
// 4. 设置迭代器（核心四指针初始化）
_start._node = _map + map_mid; // 指向中控数组成员的指针
_start._first = new_block;
_start._last = new_block + _block_size;
_start._cur = new_block + block_mid; // 首元素居中
_finish = _start;
// 5. 批量插入元素
while (n--) {
push_back(value); // 尾插（或 push_front）
}
}
那么对于deque的push_back函数来说，那么它会从last位置开始插入，那么首先会检查该双端队列是否为空数组，也就是s指向指针数组的二级指针是否为nullptr，如果为空，那么会做与上文同样的初始化工作其中包括开辟指针数组等，然后接着从last位置插入，然后last指针往后移动，那么last指针往后移动就是调用迭代器的自增运算符重载函数，那么迭代器的自增运算符重载函数所做的行为就是将cur指针往后移动，并在cur位置处设置元素值，如果cur到达了last位置处，那么此时会利用迭代器的next指针，那么获取其下一个后继的数据块的地址，如果下一个数据块还没开辟，那么就开辟对应大小的动态数组然后设置好指针数组中对应的指针的值，然后重新设置这4个指针的值，让first和last指向下一个数据块的起始和结束位置，然后cur指针指向该数据块起始位置，如果说此时数据块已经到达结尾，也就是说没有下一个数据块了，那么就得涉及到指针数组的扩容
那么指针数组的扩容注意不是简单的重新开辟一个更大的数组然后拷贝数据，因为由于deque其支持头插和尾插，那么其新的指针数组的形态类似于在原数组的两端分别再加了一节，所以并不是简单的将原有的数据拷贝到新数组那么简单
void push_back(const T& value) {
if (_map == nullptr) {
// 初始化中控数组（默认8个指针位）
_map_size = 8;
_map = _allocate_map(_map_size);
// 创建首个数据块
T* new_block = _allocate_block();
size_t mid_idx = _map_size / 2;
_map[mid_idx] = new_block; // 挂载到中央位置
// 初始化首尾迭代器
_start._node = _map + mid_idx;
_start._first = new_block;
_start._last = new_block + _block_size;
_start._cur = new_block + (_block_size / 2); // 中心起始位
_finish = _start;
}
// 继续执行插入...
}
void push_back(const T& value) {
if (_finish._cur != _finish._last - 1) {
// 当前块有空位 → 直接插入
*_finish._cur = value;
++_finish._cur;
} else {
// 当前块已满 → 准备新块
if (_finish._node == _map + _map_size - 1) {
// 中控数组尾部空间不足 → 扩容
_reserve_map_back();
}
// 创建新数据块
T* new_block = _allocate_block();
*(_finish._node + 1) = new_block; // 挂载到中控数组
// 更新_finish迭代器
_finish._node++; // 指向中控数组新项
_finish._first = new_block;
_finish._last = new_block + _block_size;
_finish._cur = new_block; // 指向新块起始位置
// 插入元素
*_finish._cur = value;
++_finish._cur;
}
}
而对于push_front头插来说，那么与尾插的原理类似，只不过是在start的前一个位置插入，就需要先移动start迭代器，然在start迭代器指向的位置处插入
那么我们发现deque也支持随机访问也就是重载了[]运算符，那么我们根据上文的构造函数以及头插和尾插的原理，我们发现deque的数据主要是集中分布在指针数组中部位置处，意味着deque中的元素不一定填满整个指针数组，也不一定填满已经存在分配好的数据块，但是幸好的就是有start和end来维护有效数据所在的区间，那么给你一个下标，那么首先你要做的就是判断下标位置的合法性，而对于双端队列来说，那么它只有首个数据块（start迭代器指向数据所在的数据块）以及最后一个数据块（end迭代器指向的数据所在的数据块）可能存在填不满数据，中间的数据块的数据一定是满的，至于为什么，这里读者可以脑海中想象回忆一下头插和尾插的过程，那么每一个数据块的大小是固定的，那么这里我们就可以计算出有效元素的总数据量，那么判断该下标是否合法，如果合法，接下来判断是否在首数据块中，不在那么就要再进行计算，假设下标为x，首数据块元素个数为k，单个数据块长度为n，
那么首先进行除运算：（x-k)/n=m 得到其在第m+2个数据块处
然后取取模运算：(x-k)%n=q,得到其在第m+2个数据块的第q位置处
这就是deque的随机访问原理
reference operator[](size_type index) {
// 1. 计算首块剩余有效元素
size_type head_remaining = _start._last - _start._cur;
if (index < head_remaining) {
// 情况1：目标在首数据块内
return *(_start._cur + index);
} else {
// 2. 计算跨块偏移
size_type remaining_offset = index - head_remaining;
// 3. 计算数据块索引和块内偏移
size_type block_idx = remaining_offset / _block_size + 1; // +1跳过首块
size_type elem_idx = remaining_offset % _block_size;
// 4. 定位目标数据块
T* target_block = *(_start._node + block_idx);
return target_block[elem_idx];
}
}
那么介绍完deque的构造以及相关的实现之后，那么我们来评价deque这个结构，那么deque首先它支持随机访问，那么这一点vector也能做到，但是根据上文说的deque的原理我们不难发现，deque的随机访问要经过一系列运算，那么明显不如vetcor直接通过原生指针的算术运算效率高，其次它支持头尾插入删除，那么其中根据原理我们也知道对于头插与尾插的各种遍历会涉及到数据块的切换和中控指针数组的扩容，整个机制还是比较复杂的，那么相比于list的头插和尾插，那么效率也是不如list的，所以deque结合了两个容器的优点，但是它却无法将这两个优点发挥到极致，而vector和list则像一个专精选手，所以我们有比如随机访问的需求，我们不会考虑deque而是vector，同理如果有大量的头尾插入删除的需求，那么我们也不会考虑deque而是list，这也是为什么deque比较冷门，并且这里你也看我只是讲解其原理，没有自己也没有建议读者去模拟实现。所以客观来说，这里选择deque用作栈的默认容器，其实我觉得不如用vector好，因为这里涉及到尾插与尾删，那么vector的效率其实更不错一点
queue
那么queue就是我们熟知的队列，那么这个数据结构我们已经非常熟悉了，那么它是一个先进先出的数据结构，那么在c语言期间实现我们是采取链表来实现我们的队列的，因为队列要从头部插入和尾删除，所以链表能够更好的适应这个场景，所以我们会定义一个节点然后相关的初始化以及入队和出队的函数，那么有了上文的stack的实现的经验，那么这里我们知道对于c++来实现queue来说，那么我们不用再需要我们自己去造轮子来实现链表了，直接利用list，所以这里的queue也采取了容器适配器模式
那么这里queue的第一个模版参数就是容器中存储的数据类型，第二个参数就是容器的类型，那么和stack同样，那么这里queue的成员变量就是一个自定义类型的成员变量，那么这个自定义类型就是对应我们的容器
template<typename T,typename container>
class queue
{
private:
container _con;
}；
那么设计者给queue的第二个模版参数的默认参数是同样是双端队列
成员函数
那么这里由于成员变量是自定义类型，所以queue的构造函数就可以调用其自定义类型的默认构造函数即可不需要我们自己显示实现一个默认构造函数
push函数
那么push函数则是可以复用适配的容器本身实现的push_back函数
void push(const T& val)
{
_con.push_back(val);
}
pop函数
那么pop函数则是复用适配的容器自己本身实现的pop_front函数
void pop()
{
_con.pop_front();
}
empty函数
那么empty函数同样是复用容器本身实现的empty函数
bool empty()
{
return _con.empty();
}
size函数
复用容器本身实现的size函数
size_t size()
{
return _con.size();
}
swap函数
调用标准库提供的swap函数来交换成员变量
void swap(queue<T, container>& l1)
{
std::swap(_con, l1.queue);
}
那么剩余的成员函数基本上也是简单的一个复用，那么这里就不过的介绍了，这里stack和queue的核心思想就是一个容器适配器模式
源码
queue.h:
#pragma once
#include<algorithm>
namespace wz
{
template<typename T,typename container>
class queue
{
private:
container _con;
public:
queue()
:_con()
{
}
queue(const queue<T,container>& l1)
{
_con = l1._con;
}
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_front();
}
const T& front()
{
return _con.front();
}
const T& back()
{
return _con.back();
}
bool empty()
{
return _con.empty();
}
void swap(queue<T, container>& l1)
{
std::swap(_con, l1._con);
}
size_t size()
{
return _con.size();
}
};
}
queue.cpp:
#include"queue.h"
#include<iostream>
#include<list>
using std::cout;
using std::endl;
int main()
{
wz::queue<int, std::list<int>> l1;
l1.push(1);
l1.push(33);
l1.push(44);
l1.push(52);
l1.push(11);
l1.pop();
wz::queue<int, std::list<int>> l2(l1);
while (!l2.empty())
{
cout << l2.front() << " ";
l2.pop();
}
cout << endl;
l2.swap(l1);
cout << l1.size() << endl;
return 0;
}
运行截图：
结语
那么这就是本文关于stack和deque和queue的全部讲解了，那么也建议读者下来自己去实现stack和queue，来加深自己的理解，那么下一期我会更新优先级队列，那么如果本文对你有帮组的话，希望三连加关注哦，你的支持就是我创作最大的动力！
