【C++】模拟list
list的模拟真的很震撼,第一次学习时给我幼小的心灵留下了极大地冲击
接下来我们一起看看list模拟究竟是怎样一回事
目录
- 节点的封装:
- list类的实现:
- 私有成员变量:
- 构造函数:
- push_back && pop_back:
- 迭代器类的实现:
- begin && end(不可被const对象调用):
- begin && end(可被const对象调用):
- 继续list类的实现:
- insert && erase:
- 带参构造函数:
- 迭代器区间构造:
- 拷贝构造:
- 赋值运算符重载:
- 析构函数:
节点的封装:
我们在之前没用CPP实现list时,是定义了一个struct node的结构体
typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;
那我们现在当然也需要定义一个结构体
template<class T>struct list_node{T _val;list_node<T>* _prev;list_node<T>* _next;list_node(const T& data = T()){_val = data;_prev = _next = nullptr;}};
但是要写一个默认构造函数,因为未来我们会new
节点,就像我们在C阶段malloc
的一样。
那么为什么要使用sruct
而不是class
呢,因为我们希望这个节点结构体
有了他的地址可以直接访问成员变量,而设置为class
时除非进行public
否则不是很方便。
list类的实现:
私有成员变量:
由于我们会使用模版,因此在写类型是比较不方便,于是可以define一下typedef list_node<T> node;
private:node* _head;
注意:我们的stl库中的list是有哨兵位的,故私有成员设为_head。
构造函数:
list(){empty_init();}
为什么要先写个空初始化呢?因为后边的成员函数有一些也需要进行初始化,因此写成一个函数进行复用。
void empty_init(){_head = new node();_head->_next = _head;_head->_prev = _head;}
push_back && pop_back:
我们先搭一个架子出来,随后在进行细节的填补。
push_back():
void push_back(const T& val){node* newnode = new node(val);node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;}
pop_back:
void pop_back(){node* prev = (it._node)->_prev;node* next = (it._node)->_next;delete it._node;prev->_next = next;next->_prev = prev;}
有了节点之后我们怎样进行访问?
没错就是使用迭代器。
迭代器类的实现:
我们的list的迭代器为什么要封装成一个类?
因为在vector那种底层虚拟地址是连续的,当我们有一个指定位置的指针,直接对指针进行++
、--
、*
…都是没问题的,因为我们的迭代器本质就是一个模仿指针行为的一个东西
但是我们的链表节点
的底层并不是连续的,是一个一个new
出来的,并不能保证底层虚拟地址的连续性,所以要对链表节点的指针
进行封装
,进行重载操作符进而可以模拟指针的行为!!
template<class T>struct list_iterator{typedef list_node<T> node;typedef list_iterator<T> self;node* _node;list_iterator(node* Node){_node = Node;}self& operator++(){_node = _node->_next;return *this;}self operator--(int){self tmp = *this;_node = _node->_prev;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator++(int){self tmp = *this;_node = _node->_next;return tmp;}bool operator!=(self it){return it._node != _node;}T& operator*(){return _node->_val;}};
对需要进行相关运算符重载的都进行一遍。
如此我们一个最简单的list框架就已经搭建成功了。
不要忘记在list类中进行将list_iterator
typedef为iterator
,因为这样我们的代码才具有跨平台性。
同时要在list类中写上begin与end这两个获取迭代器的函数。
begin && end(不可被const对象调用):
iterator begin(){return _head->_next;}iterator end(){return _head;}
我们为啥可以这么写?_head的类型不是node*
?原生的类型显示为list_node<T>*
,可是迭代器的类型是list_iterator ,完全不一样啊,这是因为我们C++支持单参数的构造函数隐式类型转换,直接对_head这个指针利用iterator的构造函数构造成迭代器
但是我们这个list目前对于const对象是很难遍历的,所以当然要实现const迭代器。
我们有两种方式,第一种是将普通迭代器的复制一份改为const迭代器,对*
这个操作符重载返回const对象,这样就不怕const对象被修改了。
但是这样的代码是在是冗余,不要忘记我们还有模版的存在!
我们如果将迭代器的模版参数多设计一个T的引用
,在list类中将这个迭代器类进行typedef
!
typedef list_iterator<T, T&> iterator;
typedef list_iterator<T, const T&> const_iterator;
那么我们这样就可以很好解决当前代码重复度高,比较冗余的缺点。
template<class T, class Ref>//多传递的模版参数struct list_iterator{typedef list_node<T> node;typedef list_iterator<T, Ref> self;node* _node;list_iterator(node* Node){_node = Node;}self& operator++(){_node = _node->_next;return *this;}self operator--(int){self tmp = *this;_node = _node->_prev;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator++(int){self tmp = *this;_node = _node->_next;return tmp;}bool operator!=(self it){return it._node != _node;}Ref operator*(){return _node->_val;}};
这样就可以根据是否为const对象而生成不同的迭代器类了!
begin && end(可被const对象调用):
iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}
继续list类的实现:
有了迭代器我们就可以写insert,erase等等函数,进而对push_back/front…等等函数的复用:
insert && erase:
void insert(iterator pos, const T& val){node* newnode = new node(val);node* prev = pos._node->_prev;node* cur = pos._node;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;}iterator erase(iterator pos){node* prev = pos._node->_prev;node* next = pos._node->_next;delete pos._node;prev->_next = next;next->_prev = prev;return next;}
带参构造函数:
list(int n, const T& val = T()){empty_init();while (n--){push_back(val);}}
直接复用push_back
迭代器区间构造:
template <class Iterator>list(Iterator first, Iterator last){empty_init();while (first != last){push_back(*first);first++;}}
拷贝构造:
list(const list<T>& lt){empty_init();list<T>::const_iterator it = lt.begin();while (it != lt.end()){push_back(*it);it++;}}
赋值运算符重载:
void swap(list<T> lt){std::swap(_head, lt._head);}list<T>& operator=(list<T> lt){swap(lt);return *this;}
析构函数:
~list(){clear();delete _head;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}
由此list类就模拟完毕,如果有不明白的地方可以尽管来找博主
相关文章:
【C++】模拟list
list的模拟真的很震撼,第一次学习时给我幼小的心灵留下了极大地冲击 接下来我们一起看看list模拟究竟是怎样一回事 目录 节点的封装:list类的实现:私有成员变量:构造函数:push_back && pop_back: 迭代器类的实…...

SAP项目任务一览表
根据SAP Activate项目管理方法论的主要精神,浓缩到一些主要的团队和任务。 主要的团队有: 项目管理(办公室)Project Management(office):项目经理团队,包括项目办公室。负责项目整体运行和监控,项目办公室负责项目的…...
130个学术网站和26个科研工具
我们平时可以见到不少学术资源,但是很多信息里会有一些重叠网站、无效网站,导致我们虽然收藏了很多网址,但是却并不都能用,学妹特地整合了130个学术资源网站和26个科研工具,每一个都是亲自试过有效的,希望能…...

《一键搞定!揭秘微信公众号文章批量下载的终极神器》
大家好!今天我要给大家介绍一个超级好用的小工具,能帮你轻松批量下载微信公众号的文章,还不需要安装任何证书哦!无论你是学生还是普通爱好者,只要你想保存一些精彩的公众号内容,这个工具都能帮到你。 概览 …...

鸿蒙入门02-首次安装和配置
注:还没有安装编辑器( deveco studio )的小伙伴请看鸿蒙入门01-下载和安装-CSDN博客 首次安装配置 编辑器( deveco studio )安装完毕以后需要进入配置界面进行相关配置配置完毕以后才可以正常使用 环境配置…...

软件工程 考研复试常考知识点总结
软件工程 什么是软件工程,这门课讲的什么? 软件工程就是把软件的开发、运行、维护的各个阶段进行系统化和规范化的过程,也就是把工程化的方法运用在软件技术之中,以构建和维护高质量的软件。 进一步,什么是工程化思想…...

Docker+Uwsgi+Nginx部署Django项目保姆式教程
之前,我和大家分享了在docker中使用uwsgi部署django项目的教程。这次,为大家带来的是使用DockerUwsgiNginx部署Django项目。废话不多说,我们开干。 步骤1:使用命令创建一个django项目 我这里python版本使用的是3.9.x 首先&#…...

[openGL] 高级光照-Gamma矫正
目录 一 Gamma是什么? 二 感知光度和物理光度 2.1 与Gamma的关系 2.3 存在问题和弊端? 三 Gamma矫正(逆Gamma) 3.1 Gamma矫正的两种方法 3.2 sRGB空间 3.3 重复校正 3.3.1 在着色器中处理重复校正 3.3.2 在加载纹理时就重复校正 3.3.3 校正前后效果 本章节Qt源码点…...

Prometheus+Grafana监控K8S集群(基于K8S环境部署)
目录 一.环境信息二.部署提前工作三.部署Prometheus监控系统四.部署Node_exporter组件五.部署Kube_state_metrics组件六.部署Grafana可视化平台七.Grafana接入Prometheus数据八.Grafana添加监控模板九.拓展 一.环境信息 1.服务器及k8s版本信息 IP地址主机名称角色版本192.168…...

[opencv]VideoWriter写出fourcc格式
fourcc支持的格式 fourcc全名Four-Character Codes,四字符代码,该编码由四个字符组成 cv2.VideoWriter_fourcc(O,O,O,O) cv2.VideoWriter_fourcc(*OOOO) 通常写法有上述两种形式,O代表一个字符,通常有 支持avi格式的有&#…...
软考中级网络工程师-网络技术
下列命令片段含义是( )。 system-view [HUAWEI] observe-port 1 interface gigabitethernet 0/0/1 [HUAWEI] interface gigabitethernet 0/0/2 [HUAWEI-GigabitEthernet0/0/2] port-mirroring to observe-port 1 inbound A 配置端口镜像 B 配置链路聚合 C 配置逻辑接口 D 配置访…...
cmake基础教程(12)函数和宏用法
参考: https://cmake.org/cmake/help/latest/command/function.html https://cmake.org/cmake/help/latest/command/macro.html#command:macro 文章目录 函数宏在CMake中,宏(macro)和函数(function)命令用于封装重复的任务,这些任务可能分散在你的CMakeLists文件中。一…...

SQLite的PRAGMA 声明(二十三)
返回:SQLite—系列文章目录 上一篇:SQLite从出生到现在(发布历史记录)(二十二) 下一篇:用于 SQLite 的异步 I/O 模块(二十四) PRAGMA 语句是特定于 SQLite 的 SQL 扩…...
Qt 实战(1)Qt 概述
一、Qt概述 1、什么是Qt? Qt(官方发音 [kju:t],音同 cute)是一个跨平台的 C 开发库,主要用来开发图形用户界面(Graphical User Interface,GUI)程序,也可以开发不带界面的…...

【练习】二分查找
1、704 (1)题目描述 (2)代码实现 package com.hh.practice.leetcode.array.demo_02;public class BinarySearch_704 {public int search(int[] nums, int target) {int i 0,j nums.length -1;while (i < j){int mid (ij) &…...

FactoryTalk View 上位机画面版本升级,还原和备份
FactoryTalk View 上位机画面版本升级,还原和备份 1 归档文件(尾缀.apa)升级2 画面文件(尾缀.sed)升级3 提示“目标工程中包含旧的HMI标签报警,FT View 10.0是最后一个......” 解决方法1 归档文件(尾缀.apa)升级 案例是FTVIEW5.0升级到FT VIEW12,需要用FT VIEW 6过渡升…...

【微信小程序】分包
整个小程序所有分包大小不超过 20M(开通虚拟支付后的小游戏不超过30M) 单个分包/主包大小不能超过 2M在小程序启动时,默认会下载主包并启动主包内页面,当用户进入分包内某个页面时,客户端会把对应分包下载下来…...
Golang教程六(单元测试,反射,网络编程,部署)
目录 一、单元测试 单元测试 子测试 TestMain 二、反射 类型判断 通过反射获取值 通过反射修改值 结构体反射 利用tag修改结构体的某些值 调用结构体方法 orm的一个小案例 对反射的一些建议 三、网络编程 socket编程 websocket编程 四、部署 打包命令 交叉编译…...

mybatis进阶篇-执行CRUD操作-typeAliases别名-接口绑定
目录结构 1.创建数据表(book) # 创建book表 create table book(id int auto_increment primary key,name varchar(255) ,price double ,num int );2.mybatis.xml配置文件 <?xml version"1.0" encoding"UTF-8" ?> <!DOC…...
C#面:泛型的主要约束和次要约束是什么
在 C# 中,泛型的约束是用来限制泛型类型参数的行为和能力的。 主要约束和次要约束是两种不同的约束方式。 主要约束(Primary Constraint): 主要约束指定了泛型类型参数必须满足的最基本的条件,它可以是一个类、一个接…...

SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...

地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...

HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...

免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...