C++(17)——list的模拟实现
前面的文章中,介绍了,
的模拟实现,本篇文章将介绍对于
的模拟实现。
目录
1. list的基本结构:
2. list功能实现:尾部插入元素:
3. list迭代器的实现:
4. list功能实现:在任意位置前插入元素:
4.1 函数实现方法:
4.2 函数运行逻辑:
5. list功能实现:删除任意位置的结点:
6. 拷贝构造与赋值重载:
7. list功能实现:clear与析构函数:
1. list的基本结构:
对于,可以将其看作数据结构中的双向带头循环链表一起学数据结构(4)——带头结点的双向循环链表_带头结点的双循环链表-CSDN博客
针对于双向带头循环链表,其基本构成单元为如下图所示:

其中,用来保存上一个结点的地址,
用于保存下一个结点的地址,
用于保存数据。对于上述结构单元,可以由下方的代码表示:
namespace violent
{template<class T>struct ListNode{ListNode<T>* _prev;ListNode<T>* _next;T _data;};
}
对于双向带头循环链表,其结构可以由下图表示:
其中,链表的第一个结点称为哨兵位头结点,此结点的不用于存储数据,只是利用
建立其他结点的关系。因此,在编写针对于链表单元结构的构造函数时,需要考虑到哨兵位头结点。本文将采用隐式类型转换的方式,来完成对于构造函数的编写:
template<class T>struct ListNode{ListNode(const T& x = T()): _prev(nullptr), _next(nullptr), _data(x){}ListNode<T>* _prev;ListNode<T>* _next;T _data;};
对于一个带头双向循环链表结构的实现,可以看作是若干个结构单元的相互链接,因此在初始化链表结构时,只需要在构造函数中,完成对于哨兵位头结点的建立,以及其内部指针的指向即可,即:

具体的实现方法,就是再创建一个类,名为的类,将上述表示单个结点结构的类作为一种类型引入到
,即:
template<class T>class list{typedef ListNode<T> Node;Node* _node;};
通过上述给出的图片,可以得到下面的构造函数:
class list{typedef ListNode<T> Node;public:list(){_phead = new Node;_phead->_next = _phead;_phead->_prev = _phead;}Node* _phead;};
2. list功能实现:尾部插入元素:
在插入一个元素之前,首先需要创建一个新的结构单元用于保存这个元素,例如需要插入的元素为,需要提前创建一个名为
的结点用于存储该元素,即:
Node* newnode = new Node(x);
当进行插入时,即:

第一步,首先获取链表最后一个结点的地址,这里命名为,通过上图不难得出
.
第二步,建立与
的联系,即:
,
,对于此关系的图片表示是如下:

最后一步:建立与
的联系,即
,

代码实现如下:
void push_back(const T& x){Node* newnode = new Node(x);Node* tail = _phead->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _phead;_phead->_prev = newnode;}
3. list迭代器的实现:
在中,由于这两种数据结构的空间是连续的,因此,在实现其迭代器功能时,通常先利用
对指针进行更名,使用时直接
即可。
但是对于,前面说到
的结构可以近似的看为链表,由于链表的空间不连续,因此,在使用迭代器进行访问时,对迭代器
不能达成访问空间中下一个结点的目的。对于
来说,正确访问下一个结点的访问为通过本结点的
获取下一个结点的地址。因此,可以考虑使用运算符重载,将
的运行逻辑从指向连续空间的下一个地址改为通过本结点的
访问下一个结点。
但是,运算符重载只能针对于自定义类型,因为迭代器的实现是依托于指针来完成的。虽然在前面利用创建自定义类型的方式创建了链表中单个结点结构的对象,但是,需要注意,此处运算符重载进行重载的目标并不是这个自定义类型,而是这个类型的指针,而指针是一个内置类型,因此,不能直接完成对于指针的重载。而是再创建一个自定义类型用于封装指针,在内部进行运算符重载。
对于封装方法:首先需要将表示单个结点结构的自定义类型引入到新的类中,此处将这个类命名为___
。为了方便使用,将表示单个结点结构的类重命名为
,成员变量为类型为
的指针。即:
template<class T>struct __list_iterator{typedef ListNode<T> Node;Node* _node;};
对于上述类的初始化如下:
template<class T>struct __list_iterator{typedef ListNode<T> Node;__list_iterator(Node* node): _node(node){}Node* _node;};
为了正常的使用迭代器来完成对于的打印,不但需要对于
,还需要对于
和
进行重载,代码如下:
template<class T>struct __list_iterator{typedef ListNode<T> Node;typedef __list_iterator<T> self;__list_iterator(Node* node): _node(node){}self& operator++(){_node = _node->_next;return *this;}self& operator++(int){self tmp(_node);_node = _node->next;return tmp;}T& operator*(){return _node->_data;}bool operator!=(const self& s){return _node != s._node;}Node* _node;};
在完成上述步骤后,向中引入__
_
,再添加
两个函数用于表示链表的起始和结束。
需要注意的是,在定义链表的起始时,并不能定义成哨兵位头结点,因为哨兵位头结点并没有保存数据,在访问链表时,需要从第一个保存数据的结点开始访问。而对于尾结点,由于链表是双向循环的。因此,可以将不存储任意数据的哨兵位头结点看作尾结点,代码如下:
typedef __list_iterator<T> iterator;iterator begin(){return _phead->_next;}iterator end(){return _phead;}
在完成了上述步骤后,就可以使用迭代器对于进行正常的访问,例如:
void test1(){list<int> It;It.push_back(1);It.push_back(2);It.push_back(3);It.push_back(4);list<int>::iterator it1 = It.begin();while (it1 != It.end()){cout << *it1 << ' ';++it1;}}
代码运行结果如下:

4. list功能实现:在任意位置前插入元素:
4.1 函数实现方法:
与尾部插入元素的大致思路相同,首先需要创建一个结点来存储这个元素:
Node* newnode = new Node(x);
例如,需要在位置之前插入这个结点,首先需要获取
位置的前一个结点的地址
。但是,
只是类型为
的一个对象,需要先创建一个变量
,来存储
中成员变量
,也就是这个结点的地址,通过
来获取
位置前一个结点的坐标,即:
Node* cur = pos._node;
Node* prev = cur->_prev;
在对 这三个位置所代表的结点进行连接,即:
void insert(iterator pos,const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;}
利用下方的代码对于函数功能进行测试,即:
It.insert(It.begin(), 5);It.insert(It.begin(), 6);It.insert(It.begin(), 7);It.insert(It.begin(), 8);for (auto e : It){cout << e << ' ';}
运行结果如下:

4.2 函数运行逻辑:
为了更清晰的了解的动作逻辑,下面给出函数的整体运行步骤,例如对于下方的代码:
It.insert(It.begin(), 5);
函数运行的第一步为首先通过函数获取地址:

在返回时,由于函数的返回类型为自定义类型,因此在返回前会去调用__
_
中的构造函数,来构造一个临时变量作为返回值,即:

再获取返回值后,跳转到函数中,即:
最后根据中编写好的代码的顺序进行运行。
在完成了对于函数的编写后,对于
_
函数可以复用
,从而简化
_
,即:
void push_back(const T& x){insert(_phead, x);}
同理也可以实现头部插入任意元素_
,即:
void push_front(const T& x){insert(_phead->_next, x);}
5. list功能实现:删除任意位置的结点:
在删除任意位置的结点前,首先需要找到这个结点的前结点和后结点的地址,为了方便表达,用表示前结点的地址,用
表示后结点的地址。代码如下:
iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;return next;}
在完成了对于的编写后,可以通过复用
来完成对于头部删除
_
和尾部删除
_
,代码如下:
void pop_back(){erase(_phead->_prev);}void pop_front(){erase(_phead->_next);}
利用下方代码对上述的函数进行测试:
It.pop_back();It.pop_back();It.pop_front();It.pop_front();for (auto e : It){cout << e << ' ';}
运行结果如下:
6. 拷贝构造与赋值重载:
list(const list<T>& s){empty();for (auto e : s){push_back(e);}}void swap(list<T>& s){std::swap(_phead, s._phead);}list<T>& operator=(list<T> s){swap(s);return *this;}
7. list功能实现:clear与析构函数:
对于函数,其功能是用于清理空间中的所有内容,即所有开辟的结点,但是不包括哨兵位头结点。
对于析构函数,则是在函数的基础上,将哨兵位头结点也进行处理。
二者对应代码如下:
void clear(){iterator i2 = begin();while (i2 != end()){i2 = erase(i2);}}~list(){clear();delete _phead;phead = nullptr;}
相关文章:
C++(17)——list的模拟实现
前面的文章中,介绍了,的模拟实现,本篇文章将介绍对于的模拟实现。 目录 1. list的基本结构: 2. list功能实现:尾部插入元素: 3. list迭代器的实现: 4. list功能实现:在任意位置前…...
花瓣网美女图片爬取
爬虫基础案例01 花瓣网美女图片 网站url:https://huaban.com 图片爬取 import requests import json import os res requests.get(url "https://api.huaban.com/search/file?text%E7%BE%8E%E5%A5%B3&sortall&limit40&page1&positionsear…...
Android native层c++调用java层API
在Android开发中,从本地(native)代码调用Java层的接口是一个常见的需求,尤其是在使用JNI(Java Native Interface)进行混合编程时。以下是一个基本的步骤指南,展示如何从C代码调用Java方法&#…...
Docker 集群配置
1、配置 MySQL MySQL 简单安装 docker安装完MySQL并run出容器后,建议请先修改完字符集编码后再新建mysql库-表-插数据 docker run -d -p 2222:3306 --privilegedtrue -e MYSQL_ROOT_PASSWORD123456 \ -v /opt/mysql/log:/var/log/mysql \ -v /opt/mysql/data:/va…...
VUE3+elementPlus 之 Form表单校验器 之 字符长度校验
需求:校验字符长度,超过后仍可输入,error提示录入字符数与限制字符数 校验字符长度: /*** 检验文字输入区的长度* param {*} rule 输入框的rule 对象,field:字段名称* param {*} value …...
【Mysql】数据库架构学习合集
目录 1. Mysql整体架构1-1. 连接层1-2. 服务层1-3. 存储引擎层1-4. 文件系统层 2. 一条sql语句的执行过程2-1. 数据库连接池的作用2-2. 查询sql的执行过程2-1. 写sql的执行过程 1. Mysql整体架构 客户端: 由各种语言编写的程序,负责与Mysql服务端进行网…...
轻型民用无人机驾驶航空器安全操控——理论考试多旋翼部分笔记
今天已经可以在线考取轻型民用无人机驾驶航空器执照了,所以我也在在线观看完视频之后整理了如下的知识点,所有知识点全部来自UOM平台。 目录 航空器知识 (1)多旋翼民用无人驾驶航空器螺旋桨的作用 (2&#x…...
UE4学习笔记 FPS游戏制作3 添加武器
文章目录 章节目标为骨骼添加武器挂载点添加武器 章节目标 本章节为手部添加一个武器挂载点,并挂载一个武器 为骨骼添加武器挂载点 添加挂载点需要以一个动画片段为基础,为骨骼添加挂载点。 首先找到我们需要的动画片段,通常是idle 双击打…...
详解 Prim 算法的实现
一、算法思路 Prim 算法是用来求最小生成树的,它的思想也有点类似于贪心——逐个将离当前集合最近的点加入到集合中,直至发现图不连通或所有点都被加到集合中,算法即宣告终止。它的具体做法是: step 1:初始时…...
Android 使用高德地图
一、获取高德平台key 【1】基于application包名&sha1值在高德控制台获取key值,详情参考: 获取Key-创建工程-开发指南-Android 地图SDK | 高德地图API 【2】在manifest中声明权限 【3】将拿到的key值在manifest中进行声明 <!--允许程序打开网络…...
从redis setnx 来看看分布式锁
什么是分布式锁 分布式锁(多服务共享锁)在分布式的部署环境下,通过锁机制来让多客户端互斥的对共享资源进行访问/操作。 为什么需要分布式锁 在单体应用服务里,不同的客户端操作同一个资源,我们可以通过操作系统提供…...
校园网网络规划与设计——计算机网络实践报告
W...Y的主页 😊 代码仓库分享💕 目录 一、设计目的 二、软硬件环境 三、理论基础 四、设计方案 五、网络配置步骤 六、设计过程中出现的问题及相应解决办法 八、参考资料 一、设计目的 深入理解网络工程的三层层次设计模型; 掌握网络…...
Qt QScrollArea 不显示滚动条 不滚动
使用QScrollArea时,发现添加的控件超出QScrollArea 并没有显示,且没有滚动条效果 原因是 scrollArea指的是scrollArea控件本身的大小,肉眼能看到的外形尺寸。 scrollAreaWidgetContents指的是scrollArea控件内部的显示区域,里面可…...
【SVN在Linux下的常用指令】
windows下的TortoiseSVN是资源管理器的一个插件,以覆盖图标表示文件状态,几乎所以命令都有图形界面支持,比较好用,这里就不多说。主要说说linux下svn的使用,因为linux下大部分的操作都是通过命令行来进行,所…...
2024 高级前端面试题之 Node 「精选篇」
该内容主要整理关于 Node 模块的相关面试题,其他内容面试题请移步至 「最新最全的前端面试题集锦」 查看。 Node模块精选篇 1. package.json版本号规则2. package.json 与 package-lock.json 的关3. npm 模块安装机制4. 模块化的差异 AMD CMD COMMONJS ESMODUL5. No…...
linux麒麟系统安装mongodb7.0
1.mogedb下载 下载的是他tar包 https://fastdl.mongodb.org/linux/mongodb-linux-x86_64-rhel80-7.0.5.tgz wget -o https://fastdl.mongodb.org/linux/mongodb-linux-x86_64-rhel80-7.0.5.tgz 也可以下载rpm包 2.将包上传至服务器并解压 #进入目录 并解压 cd /opt/ tar…...
Spring声明式事务
1.概念 事务就是用户定义的一系列执行SQL语句的操作, 这些操作要么完全地执行,要么完全地都不执行, 它是一个不可分割的工作执行单元 一个使用Mybatis-Spring的主要原因是它允许Mybatis参与到Spring的事务管理中,而不是给Mybatis创建一个新的…...
PyTorch深度学习实战(34)——Pix2Pix详解与实现
PyTorch深度学习实战(34)——Pix2Pix详解与实现 0. 前言1. 模型与数据集1.1 Pix2Pix 基本原理1.2 数据集分析1.3 模型构建策略 2. 实现 Pix2Pix 生成图像小结系列链接 0. 前言 Pix2Pix 是基于生成对抗网络 (Convolutional Generative Adversarial Netwo…...
第96讲:MySQL高可用集群MHA的核心概念以及集群搭建
文章目录 1.MHA高可用数据库集群的核心概念1.1.主从复制架构的演变1.2.MHA简介以及架构1.3.MHA的软件结构1.4.MHA Manager组件的启动过程1.5.MHA高可用集群的原理 2.搭建MHA高可用数据库集群2.1.环境架构简介2.2.搭建基于GTID的主从复制集群2.2.1.在三台服务器中分别搭建MySQL实…...
外星人入侵(python)
前言 代码来源《python编程从入门到实践》Eric Matthes 署 袁国忠 译 使用软件:PyCharm Community Editor 2022 目的:记录一下按照书上敲的代码 alien_invasion.py 游戏的一些初始化设置,调用已经封装好的函数方法,一个函数的…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
