c++编程(18)——deque的模拟实现(2)容器篇

欢迎来到博主的专栏——c++编程
博主ID:代码小豪

文章目录

    • deque的数据结构
    • deque的构造
      • 默认构造
      • 填充构造
    • deque的其他操作
    • deque的插入、删除
      • push_back和push_front
      • pop_back和pop_front
      • clear、erase和insert操作
    • 传送门

在上一篇中,我们已经实现了deque最核心的部分,即deque的迭代器,在deque容器当中,迭代器充当了非常重要的角色,在deque的大多数操作当中,都是对迭代器进行操作

deque的数据结构

回到deque容器,我们知道deque的成员有以下几个

  1. 迭代器first,指向首元素
  2. 迭代器last,指向末尾元素的后一个
  3. 中控数组map,管理缓冲区
  4. 中控数组个数mapsize,管理缓冲区个数’

deque的构造

我们先来看看如何构造一个空的deque容器,即deque的默认构造。

一个未初始化的deque是这样的
在这里插入图片描述
如何初始化出一个空的deque容器呢?首先我们要为map分配出多个未使用的缓冲区,然后初始化出map的中间部分的缓冲区,并将first和last迭代器指向缓冲区的中间位置。

为什么一定要用map的中间部分呢?在前面我们已经讲过了,deque是一个双端队列,那么deque必须要做到头尾插入,如果我们不选择中间部分作为初始空间,那么deque会出现某一端的效率变低。

在这里插入图片描述
所以正确的方式应该是在中间部分进行初始化
在这里插入图片描述
我们先为map配置好缓冲区,并且安排好deque的结构,将这部分的操作写成一个函数,命名为CreateMapAndNode。意思是创建中控数组,并且生成缓冲区(注意这个函数会经常出现在deque的构造当中)。

void CreateMapAndNode(size_t elementNum)
{
	size_t nodeNum = elementNum / bufsize + 1;//判断待使用的缓冲区有几个
	mapsize = nodeNum < 8 ? 8 : nodeNum + 2;//预留缓冲区,提高效率
	map = new pointer[mapsize];//开辟mapsize个缓冲区

	//计算出[nstart,nfinish]的区间
	map_poniter nstart = map + (mapsize - (elementNum / bufsize)) / 2;
	map_poniter nfinsh = nstart + nodeNum - 1;

	//初始化这个区间
	map_poniter tmp = nstart;
	while (tmp <= nfinsh)
	{
		*tmp = new T[bufsize];//生成缓冲区
		tmp++;
	}

	//初始化迭代器strat和finish,使得这两个迭代器指向deque的起始地址和结尾地址
	start.setnode(nstart);
	finish.setnode(nfinsh);
	start.cur = start.first;
	finish.cur = finish.first + (elementNum % bufsize);
}

先来解释一下这个函数中出现的几个重要参数吧。

(1)elementNum,为deque容器初始化的元素个数。(2)nodeNum,初始化这些元素个数需要多少个缓冲区(3)nstart,nfinish,这是一个区间的两个边界,[nstart,nfinsh]是这些元素所在的缓冲区区间。

要注意CreateNodeAndMap是一个只在为deque容器初始化的时候才能用,即只会出现在deque的构造函数当中。因此这个函数的行为其实就是一个初始化的行为,因此不会有插入元素的操作。只是开辟map和缓冲区的空间。

这个函数的逻辑是有点复杂的,博主在这里进行按照顺序梳理一下。

  1. 先确定deque会初始化多少个元素
  2. 确定这些元素会占据多少个缓冲区,缓冲区个数=elementNum/bufsize+1
  3. 为map开辟空间,为了避免频繁扩容导致的时间开销,我们要为map预留出一部分区间,因此可以看到,mapsize如果小于8,就预留8个缓冲区,如果mapsize的个数大于8,就多预留2个缓冲区
  4. [nstart,nfish]会处在中控数组的中间的区段,因为保持在中间,可以让头尾两端的扩充空间一样,保持头尾插入、删除的效率不变。
  5. 将[nstart,nfinsh]的空间开辟出来,便于后续插入数据。

默认构造

由于默认构造不需要插入任何数据,因此在调用CreateMapAndNode的时候不需要插入任何的数据,因此传入数据0即可

deque()
{
	CreateMapAndNode(0);
}

填充构造

填充构造就是在初始化deque容器时,向deque容器插入N个值为val的元素。

deque(size_t n, T val)
{
	CreateMapAndNode(n);//生成n个元素的空间
	map_poniter cur;
	for (cur = start.node; cur < finish.node; cur++)
	{
		fill(*cur, *cur + bufsize, val);
	}
	fill(finish.first, finish.last, val);
}
template<class inputiterator,class T>
void fill(inputiterator first, inputiterator last, T val)
{
	while (first != last)
	{
		*first = val;
		first++;
	}
}

这个fill的作用是将[first,last)区间内的所有元素都填充为val,放在填充构造当中,就是为缓冲区内的元素都填充为val。

deque的其他操作

iterator begin() { return start; }
iterator end() { return finish; }
T& front(){return *start;}

T& back(){
	iterator tmp = finish;
	tmp--;
	return *tmp;
}
T& operator[](size_t pos){
	assert(pos < size())
	return *(start+pos);
}

size_t size(){return finish - start;}
bool empty() { return finish == start; }

当我们为deque设计好begin(),end()之后,我们可以用范围for(range for)来遍历整个deque。

void testmydeque()
{
	deque<int> dq1(5, 10);
	for (auto& e : dq1)
	{
		cout << e << " ";//10 10 10 10 10 
	}
	cout << dq1.front() << endl; //10
	cout << dq1.back() << endl;//10
	cout << dq1[5] << endl;//error pos>=size()
}

后续不再提供测试案例,如果感兴趣可以去博主的代码仓库查看,链接将会放在文章末尾。

deque的插入、删除

push_back和push_front

我们先来完成deque的pushback()和popback(),由于在插入的过程中可能会出现缓冲区空间不足的情况,此时我们就需要开辟新的缓冲区,来容纳这些数据。

void push_back(const T& val)
{
	if (finish.cur != finish.last-1)//判断是否来到了缓冲区边界
	{
		*finish = val;
		++finish;
	}
	else {//到达边界,需要开辟新的缓冲区
		ReserveMapAtBack();//判断一下是否需要在map的后端新增缓冲区
		*(finish.node + 1) = new T[bufsize];
		*finish = val;
		finish.setnode(finish.node + 1);
		finish.cur = finish.first;
	}
}

这里的pushback会对下面的三种情况进行不同的操作
情况1:当尾端的缓冲区还有剩余空间时
在这里插入图片描述
情况2,当缓冲区没有空间,但是map中还有多于的缓冲区
由于并不是map数组管理的所有缓冲区都开辟了空间,因为这可能会导致空间浪费的现象,所以deque采取的策略是,先为map获取多个缓冲区,为已使用的缓冲区开辟空间,盈余的缓冲区不开辟空间,秉承一个用一个缓冲区开一个缓冲区的原则。
在这里插入图片描述
有没有发现deque在尾插时,插入的位置在末尾迭代器finish的上一个,这是由于c++规定STL中的末尾迭代器必须保持[begin,end)的区间,即容器的的末尾迭代器指向的是有效数据的后一位。

情况三:当缓冲区的剩余空间不足,并且map没有多于的后端缓冲区时。
此时需要将重新生成一个map,这个map可以管理更多的缓冲区,接着再将原map的元素转移到新map上。
在这里插入图片描述
这个操作我们交给了ReserveMapAtBack()函数。它会判断我们是否需要再尾端添加新的缓冲区。

void ReserveMapAtBack(size_t AddNode = 1)
{
	if (AddNode > mapsize - (finish.node - map-1))
		reallocmap(AddNode, false);
}

AddNode是要增加的缓冲区个数。如果满足要增加的缓冲区个数。大于末端缓冲区的盈余个数,就要重新配置一个map。配置新map的操作我们使用reallocmap来实现。

由于不仅仅pushback会重新配置map,pushpop也会重新配置map,因此我们将realoocmap设计成可以在尾端重新配置,也能在头端重新配置。reallocmap函数如下:

void reallocmap(size_t AddNode,bool AllocAtFront)
{
	size_t oldnodes = finish.node - start.node + 1;//旧的有效缓冲区个数
	size_t newnodes = oldnodes + AddNode;//新的有效缓冲区个数

	map_poniter newstart;
	size_t newmapsize = mapsize+(mapsize > AddNode ? mapsize : AddNode) + 2;//新map的管理缓冲区个数

	map_poniter newmap = new pointer[newmapsize];//生成新的map数组
			
			//计算新的迭代器区间
	newstart = newmap + (newmapsize - newnodes) / 2
		+ (AllocAtFront ? AddNode:0);
	map_poniter newfinish = newstart + oldnodes - 1;

	copynode(start.node, finish.node + 1, newstart);//将旧缓冲区交给新的map管理
	delete[] map;//释放旧map
			//更改迭代器以及容器数据
	map = newmap;
	mapsize = newmapsize;
	start.setnode(newstart);
	finish.setnode(newfinish);
}

具体步骤如下

  1. 先计算旧缓冲区的个数
  2. 再计算新缓冲区的个数,新缓冲区个数=旧缓冲区个数+新增缓冲区个数
  3. 计算新的map的缓冲区
  4. 为新map开辟空间
  5. 计算新缓冲区的区间[newstart,newfinish]
  6. 将旧map的有效缓冲区交给新map管理
  7. 删除旧map
  8. 调整迭代器,以及deque的容器数据

copynode函数可以将数据拷贝到指定数据上。

template<class inputiterator, class outputiterator>
void copynode(inputiterator first, inputiterator last, outputiterator dest)
{
	while (first != last)
	{
		*dest = *first;
		dest++;
		first++;
	}
}

pushfront()也可以复用这些函数,因此我们写起来会轻松很多。

void push_front(const T&val)
{
	if (start.cur != start.first)
	{
		start--;
		*start = val;
	}
	else {
		ReserveMapAtFront();
		*(start.node - 1) = new T[bufsize];
		start--;
		*start = val;
	}
}

push_front也有三种情况,但是和push_back面临的问题类似,因此博主不多赘述了。

pop_back和pop_front

void pop_back()
{
	assert(!empty());//空容器不能调用pop_back
	if (finish.cur != finish.first)
	{
		finish--;
	}
	else {
		delete[] finish.first;//释放缓冲区
		finish.setnode(finish.node - 1);
		finish.cur = finish.last - 1;
	}
}

pop_back会出现两种情况。

  1. 如果尾删后缓冲区仍有元素(即first.cur!=first.first),就让迭代器指向上一个元素
  2. 如果尾删后缓冲区没有元素,为了继续贯彻用一个缓冲区开一个缓冲区的原则,就需要对没有元素的缓冲区进行释放。

在这里插入图片描述

在这里插入图片描述
pop_front的操作和pop_back比较类似,也是要判断缓冲区有没有剩余元素

void pop_front()
{
	assert(!empty());
	if (start.cur != start.last - 1)
	{
		start++;
	}
	else
	{
		delete start.first;
		start.setnode(start.node + 1);
		start.cur = start.first;
	}
}

clear、erase和insert操作

void clear()
{
	for (map_poniter node = start.node; node <= finish.node; ++node)
		delete[] * node;//清除所有缓冲区
	//调整迭代器start和finish
	map_poniter node = map + mapsize / 2;
	*node = new T[bufsize];
	start.setnode(node);
	start.cur = start.first;
	finish = start;
}

clear操作是清理deque容器的所有元素。具体操作如下:

  1. 释放当前的所有缓冲区
  2. 在map数组的中间部分开辟一个新的缓冲区,这个缓冲区为空
  3. 调整finish和start的迭代区间。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

erase操作是删除pos迭代器指向位置的元素,代码如下:

iterator erase(iterator pos)
{
	iterator next = pos+1 ;
	int index = pos - start;//偏移量
	if (index < size() / 2)
	{
		copyAtFront(start,pos,next);//从前往后拷贝
		pop_front();//删除前面的冗余元素
	}
	else {
		copy(next, finish, pos);//从后向前拷贝
		pop_back();
	}
	return start + index;
}

erase的步骤如下:

  1. 先计算偏移量,来判断这个删除的元素位于前半段还是后半段
  2. 如果元素处于后半段,就从后往前挪动数据,调用copy函数
  3. 如果元素 处于前半段,就从前往后挪动数据,调用coptAtFront函数
  4. 之所以要分前后半段,主要还是因为挪动的数据越少,效率越高。

在这里插入图片描述
往前挪动的函数是copyAtFront,代码如下:

template<class inputiterator, class outputiterator>
void copyAtFront(inputiterator first,inputiterator last,outputiterator dest)//从后往前拷贝
{
	while (last != first)
	{
		--last;
		--dest;
		*dest = *last;
	}
}

在这里插入图片描述
从后往前挪动的代码是copy,实际上这个copy和copynode的代码完全一样,可以用来复用,之所以写成两个不一样的名字,是因为博主希望在文中为其做一个区分,而博主的源代码中。copynode和copy都写成了同一个模板函数,写为copy。

template<class inputiterator, class outputiterator>
void copy(inputiterator first, inputiterator last, outputiterator dest)
{
	while (first != last)
	{
		*dest = *first;
		dest++;
		first++;
	}
}

在pos位置上插入一个值为val的元素

iterator insert(iterator pos, const T& val)
{
	if (pos.cur == start.cur) {//如果插入在开头,交给push_front
		push_front(val);
		return start;
	}
	else if (pos.cur == finish.cur) {//如果插入在末尾,交个push_back
		push_back(val);
		return finish - 1;
	}
	else {//插入在中间位置
		int index = pos - start;//计算偏移量
		if (index < size() / 2) {
			push_front(front());//最前端加上与第一个元素同值的元素
			pos = start + index;//标记一下,待会方便挪动数据
			iterator pos1 = pos;
			++pos1;
			copy(start+2, pos1, start+1);
		}
		else
		{
			push_back(back());//在尾端加上一个与最后一个元素同值的元素
			pos = start + index;
			copyAtFront(pos, finish-2, finish-1);
		}
		*pos = val;
		return pos;
	}
}

关于头插和尾插的方式博主就不赘述了,关键的点在于如何在中间插入,其实这与erase存在异曲同工之妙。

不要被各种变量吓到了,其实本质上就是为了挪动数据,让数据插入到pos位置中。
在这里插入图片描述
在这里插入图片描述

传送门

deque的模拟实现——迭代器篇:deque的模拟实现(1)迭代器篇
deque的模拟实现源码:deque的模拟实现源码

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/714947.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

循环队列

循环队列是一种线性数据结构&#xff0c;其操作表现基于 FIFO&#xff08;First In First Out&#xff0c;先进先出&#xff09;原则并且队尾被连接在队首以形成一个循环。 这种结构克服了普通队列在元素入队和出队时需要移动大量元素的缺点。 在循环队列中&#xff0c;当元素…

Centos实现Mysql8.4安装及主主同步

8.4的Msyql在同步的时候与之前的版本有很大不同&#xff0c;这里记录一下安装流程 Mysql安装 官网下载 选择自己的版本&#xff0c;选第一个 复制下载链接 在服务器上创建一个msyql目录 使用命令下载,链接换自己的 wget https://dev.mysql.com/get/mysql84-community-relea…

跟着刘二大人学pytorch(第---10---节课之卷积神经网络)

文章目录 0 前言0.1 课程链接&#xff1a;0.2 课件下载地址&#xff1a; 回忆卷积卷积过程&#xff08;以输入为单通道、1个卷积核为例&#xff09;卷积过程&#xff08;以输入为3通道、1个卷积核为例&#xff09;卷积过程&#xff08;以输入为N通道、1个卷积核为例&#xff09…

接口测试工作准备

前面已经讲了接口测试的原理&#xff0c;接下来讲接口测试如何准备。分为了解项目背景、收集项目相关资料、部署接口测试环境。 1、了解项目背景 1、首先我们应该去了解项目的应用范围&#xff0c;了解业务场景需要调用的接口&#xff0c;确定接口测试的接口个数、接口名字、接…

Spring配置那些事

一、引言 配置是一个项目中不那么起眼&#xff0c;但却有非常重要的东西。在工程项目中&#xff0c;我们一般会将可修改、易变、不确定的值作为配置项&#xff0c;在配置文件/配置中心中设置。 比方说&#xff0c;不同环境有不同的数据库地址、不同的线程池大小等&#xff0c…

创建STM32F10X空项目教程

创建STM32F10X系列的空项目工程 官网下载STM32标准外设软件库 STM32标准外设软件库 创建一个空文件夹作为主工程文件夹在主工程文件夹中&#xff0c;创建三个空文件夹 CMSIS - 存放内核函数及启动引导文件 FWLIB - 存放库函数 USER - 存放用户的函数将STM32标准外设软件库文件…

Git学习记录v1.0

1、常用操作 git clonegit configgit branchgitt checkoutgit statusgit addgit commitgit pushgit pullgit loggit tag 1.1 git clone 从git服务器拉取代码 git clone https://gitee.com/xxx/studyJava.git1.2 git config 配置开发者用户名和邮箱 git config user.name …

Javaweb04-Servlet技术2(HttpServletResponse, HttpServletRequest)

Servlet技术基础 HttpServletResponse对象 HttpServletResponce对象是继承ServletResponse接口&#xff0c;专门用于封装Http请求 HttpServletResponce有关响应行的方法 方法说明功能描述void setStatus(int stauts)用于设置HTTP响应消息的状态码&#xff0c;并生成响应状态…

【C++ 11 新特性】lambda 表达式详解

文章目录 1. 常见 lambda 面试题&#x1f58a; 1. 常见 lambda 面试题&#x1f58a; &#x1f34e;① 如果⼀个 lambda 表达式作为参数传递给⼀个函数&#xff0c;那这个函数可以使⽤这个 lambda 表达式捕获的变量吗 ? &#x1f427; 函数本身无法直接访问到 lambda表达式捕获…

教资认定报名照片要求小于190kb…

教资认定报名照片要求小于190kb…… 要求&#xff1a;文件小于190kb&#xff0c;宽度290-300&#xff0c;高度408-418 方法&#xff1a;vx搜随时照-教资认定 直接制作合规尺寸即可&#xff0c;还可以打印纸质版邮寄到家

ffmpeg解封装rtsp并录制视频-(2)使用VLC模拟一个rtsp服务器并用ffmpeg解封装该rtsp流

VCL模拟服务器并打开播放该视频文件&#xff1a; - 准备好一个mp4文件&#xff0c;打开vlc软件 - 选择“媒体”》“流” - 添加一个mp4文件 - 点击下方按钮选择“串流” - 下一步目标选择rtsp 点击“添加” - 端口默认8554 - 路径设置 /test - 用…

JavaFX VBox

VBox布局将子节点堆叠在垂直列中。新添加的子节点被放置在上一个子节点的下面。默认情况下&#xff0c;VBox尊重子节点的首选宽度和高度。 当父节点不可调整大小时&#xff0c;例如Group节点&#xff0c;最大垂直列的宽度基于具有最大优选宽度的节点。 默认情况下&#xff0c;…

揭秘神秘的种子:Adobe联合宾夕法尼亚大学发布文本到图像扩散模型大规模种子分析

文章链接&#xff1a;https://arxiv.org/pdf/2405.14828 最近对文本到图像&#xff08;T2I&#xff09;扩散模型的进展促进了创造性和逼真的图像合成。通过变化随机种子&#xff0c;可以为固定的文本提示生成各种图像。在技术上&#xff0c;种子控制着初始噪声&#xff0c;并…

Linux_应用篇(17) FrameBuffer 应用编程

本章学习 Linux 下的 Framebuffer 应用编程&#xff0c; 通过对本章内容的学习&#xff0c; 大家将会了解到 Framebuffer 设备究竟是什么&#xff1f;以及如何编写应用程序来操控 FrameBuffer 设备。 本章将会讨论如下主题。 ⚫ 什么是 Framebuffer 设备&#xff1f; ⚫ LCD 显…

分布式系统中的经典思想实验——两将军问题和拜占庭将军问题

文章目录 一、两将军问题1.1 问题描述1.2 深入理解两将军问题1.3 实验结论 二、拜占庭将军问题2.1 问题描述2.2 深入理解拜占庭将军问题2.3 解决方案 三、两将军和拜占庭问题的关系3.1 区别和联系3.2 应用与现实意义 参考资料 一、两将军问题 1.1 问题描述 两将军问题描述的是…

BetterZip 5软件详细安装步骤(最新版软件下载)

​BetterZip是一款功能强大的Mac解/压缩软件&#xff0c;可以满足用户对文件压缩、解压、加密和保护等方面的需求。以下是关于BetterZip软件的主要功能、特点和使用方法的详细介绍&#xff0c;以及对其用户友好度、稳定性和安全性的评价。 安 装 包 获 取 地 址: BetterZip 5-…

半导体芯片结构以及译码驱动

一.半导体芯片结构 可能并不是只有一个芯片&#xff0c;有多个芯片就需要片选线了。 二.半导体存储芯片的译码驱动 主要有两种方式&#xff1a;线选法和重合法 线选法&#xff1a;每一个存储单元都用一根字选择线选中&#xff0c;直接选中存储单元的各位。&#xff08;一维…

从 Acme.Sh V3.0 说说 ZeroSSL

熟悉明月的都知道&#xff0c;明月一直都在使用 acme.sh 作为服务器端申请、部署、续期免费 SSL 证书的主要工具&#xff0c;今天在帮一个站长申请 SSL 证书的时候发现 acme.sh v3.0 开始默认的免费 SSL 证书变更为&#xff1a;ZeroSSL 了&#xff0c;这个 ZeroSSL 其实跟明月一…

Java NIO ByteBuffer 使用方法

前言 最近在使用spring boot websocket xterm.js 给 k8s pod做了个在线的 web 终端&#xff0c;发现websocket的类核心方法&#xff0c;用的都是ByteBuffer传递数据&#xff0c;如下&#xff1a; OnMessagepublic void onMessage(Session session, ByteBuffer byteBuffer) {…

【深度学习量化交易1】一个金融小白尝试量化交易的设想、畅享和遐想

关注我的朋友们可能知道&#xff0c;我经常在信号处理的领域出没&#xff0c;时不时会发一些信号处理、深度学习科普向的文章。 不过算法研究久了&#xff0c;总想做一些更有趣的事情。 比如用深度学习算法赚大钱。。毕竟有什么事情能比暴富更有意思呢。 一、神经网络与彩票…