list全部功能模拟实现

news/2024/3/29 3:33:03/文章来源:https://blog.csdn.net/qq_61342044/article/details/127253714

目录:

list的深度剖析及模拟实现

list底层是双向循环链表 ------而实现list最重要的就是迭代器类的实现 下面我们会重点学习迭代器

list整体接口函数罗列

//模拟实现list底层---全部功能
namespace std
{//结点类模拟实现template<class T>struct list_node{//构造函数list_node(cosnt T& value = T()):_val(value), _prev(nullptr), _next(nullptr){}//成员变量list_node<T>* _prev;//前驱指针list_node<T>* _next;//后继指针T _val;};//模拟实现list迭代器template<class T,class Ref,class Ptr>class _list_iterator{typedef list_node<T> Node;typedef _list_iterator<T, Ref, Ptr> self;_list_iterator(Node* pnode);//构造函数//各种运算符重载self operator++();//前++self operator--();self operator++(int);//后置++self operator--(int);bool operator==(const self& s)const;bool operator!=(const self& s)const;Ref operator*();//返回的是引用Ptr operator->();//返回的是指针//成员变量Node* _pnode;};//模拟实现listtemplate<class T>class list{public:typedef list_node<T> Node;typedef _list_iterator<T, T&, T*> iterator;typedef _list_iterator<T, const T&, const T*> const_iterator;//默认成员函数list();list(const list<T>& lt);//拷贝构造函数list<T>& operator=(const list<T>& lt);~list();//有关迭代器相关函数iterator begin();iterator end();const_iterator begin()const;const_iterator end()const;//访问相关容器T& front();T& back();const T& front()const;const T& back()const;//对容器操作函数void insert(iterator pos, const T& x);void push_back(const T& x);void pop_back();void push_front(const T& x);void pop_front();iterator erase(iterator pos);//删除pos位置的迭代器,返回pos->next迭代器//其他操作void clear();bool empty()const ;size_t size()const;void resize(size_t n, const T& value = T());void swap(list<T>& lt);private:Node* _head;};
}

其他操作与vector和string的实现基本相似,我们重点学习iterator迭代器类

迭代器类的模拟实现

迭代器类存在的意义

之前模拟实现string和vector的时候为什么就没有实现迭代器类呢,为什么要在list中实现迭代器类呢?
1.因为在string和vector对象都是将数据存储在了一块连续的内存空间中,我们通过指针进行自增,自减以及解引用等操作,就可以对相应位置的数据进行一系列的操作,string和vector中的迭代器都是原生指针。

1.但是对于list来说,list的底层实现是链表,**我们都知道链表中各个节点在内存中的位置都是随机的,不是连续的,**所以我们不能仅仅通过节点指针的自增、自减以及解引用等等操作来对相应的节点进行操作。
2.所以迭代器的意义是,让使用者可以不必关心容器的底层实现,可以用简单统一的方式对容器内的数据进行访问。
3.C++中最厉害的是什么,就是封装和对各种操作符进行重载。重载之后呢,使得结点指针的各种操作就和普通指针一样了。
在这里插入图片描述
1、为什么模板参数那里是三个参数呢?为什么不是一个呢
在这里插入图片描述
然后在list的模拟实现中,我们typedef了两个迭代器类型,分别是普通迭代器和const迭代器
在这里插入图片描述
这里我们就可以看出Ref是T&类型,Ptr是T*类型
当我们使用迭代器的时候,编译器就会实例化出一个迭代器对象,根据需要分为普通迭代器对象和const迭代器对象。
如果该迭代器类不设计三个模板参数的话,就不能很好的区分普通迭代器和const迭代器了。

构造函数

在这里插入图片描述

迭代器就是对结点指针进行封装,所以成员变量只有一个,那就是结点指针,构造函数就是根据结点指针来构造出一个迭代器对象的。

++运算符的重载

在这里插入图片描述
++运算符分为前置++和后置++
1.前置++ 就是 将内部指针往后面移动一位,再返回
2.后置++ 就是 将内部指针先拷贝一份–tmp,然后
内部指针再往后移动一位,返回的是tmp指针

– --运算符重载

在这里插入图片描述
实现跟++相同

==运算符重载

在这里插入图片描述

==运算符比较两个迭代器时候,我们实际上是想知道的是这两个迭代器是否是同一个位置的迭代器,所以呢,我们直接比较两个迭代器的指针指向即可。

!=运算符重载

在这里插入图片描述
!=运算符比较两个结点指针的指向即可.

*运算符重载

在这里插入图片描述
*运算符 实际上是解引用结点指针的数据

->运算符重载

在这里插入图片描述
->运算符,我们要返回的是结点所储存数据的地址

list与vector的对比

在这里插入图片描述

list模拟实现代码:

//模拟实现list底层---全部功能
namespace std
{//结点类模拟实现template<class T>struct list_node{//构造函数list_node(cosnt T& value = T()):_val(value), _prev(nullptr), _next(nullptr){}//成员变量list_node<T>* _prev;//前驱指针list_node<T>* _next;//后继指针T _val;};//模拟实现list迭代器template<class T,class Ref,class Ptr>class _list_iterator{typedef list_node<T> Node;typedef _list_iterator<T, Ref, Ptr> self;_list_iterator(Node* pnode)//构造函数:_pnode(node){}//各种运算符重载self operator++()//前++{_pnode = _pnode->next;return *this;}self operator++(int)//后置++{self tmp(*this);_pnode = _pnode->next;return tmp;}self operator--()//前置{_pnode = _pnode->prev;return *this;}self operator--(int)//后置{self tmp(*this);_pnode = _pnode->prev;return tmp;}bool operator==(const self& s)const{return _pnode == s._pnode;}bool operator!=(const self& s)const{return _pnode != s._pnode;}Ref operator*()//返回的是引用{return _pnode->_val;}Ptr operator->()//返回的是指针{return &_pnode->_val;}//成员变量Node* _pnode;};//模拟实现listtemplate<class T>class list{public:typedef list_node<T> Node;typedef _list_iterator<T, T&, T*> iterator;typedef _list_iterator<T, const T&, const T*> const_iterator;//默认成员函数list(){_head = new Node;_head->prev = _head;_head->next = _head;}list(const list<T>& lt)//拷贝构造函数{_head = new Node;_head->prev = _head;_head->next = _head;for (const auto& e : lt){push_back(e);}}//=运算符重载list<T>& operator=(const list<T>& lt){if (this != &lt)//避免给自己自赋值{clear();for (auto& e : lt){push_back(e);//将lt中的每个数据放push}}return *this;}~list(){clear();//全部清空delete _head;//删掉头结点_head = nullptr;}//有关迭代器相关函数iterator begin(){return iterator(_head->next);}iterator end(){return iterator(_head);}const_iterator begin()const{return const_iterator(_head->next);}const_iterator end()const{return const_iterator(_head);}//访问相关容器T& front(){return *begin();}T& back(){return *(--end());}const T& front()const{return *begin();}const T& back()const{return *(--end());}//对容器操作函数void insert(iterator pos, const T& x){assert(pos);//先检查pos迭代器是否合理//插入 只要知道前一个指针就行prevNode* cur = pos._pnode;//迭代器pos处的结点指针Node* prev = cur->prev;//相当于pos前一个结点指针Node* newNode = new Node(x);//创建结点//插入结点操作newNode->next = cur;cur->prev = newNode;newNode->prev = prev;prev->next = newNode;}iterator erase(iterator pos)//删除pos位置的迭代器,返回pos->next迭代器{assert(pos);//检测pos迭代器的合理性//删除一个结点,必须知道该节点的前后两个结点Node* move = pos._pnode;Node* prev = move->prev;Node* next = move->next;delete move;//删除move结点//建立prev与next之间的双向关系prev->next = next;next->prev = prev;return iterator(next);//返回pos的下一个迭代器}void push_back(const T& x){insert(end(), x);}void pop_back(){erase(--end());//删除头结点的前一个结点}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}//其他操作void clear(){//遍历每一个结点然后删除iterator ir = begin();while (ir != end())//逐个删除结点  只保留头结点{ir = erase(ir);}}bool empty()const{return begin() == end();//判断是否只有头结点}size_t size()const{size_t sz = 0;iterator it = begin();while (it != end()){sz++;it++;}return sz;}void resize(size_t n, const T& value = T()){size_t len = size();//比较n和len的值if (len <= n){while (n - len){push_back(value);len++;}}else //(len>n){while (len-n){pop_back();len--;}}}void swap(list<T>& lt){::swap(_head,lt._head);//交换两个容器当中的头指针即可}private:Node* _head;};
}

如果错误,多多指教!

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

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

相关文章

java数据结构-------栈和队列

文章目录1、栈(Stack)1、什么是栈2、栈中常使用的方法3、栈的应用场景1、逆序打印链表2、有效的括号2、队列(Queue)1、什么是队列2、队列的使用3、循环队列目标&#xff1a;1、 栈的概念及使用&#xff0c;2、 队列的概念及使用&#xff0c;3.、相关OJ题1、栈(Stack) 1、什么是…

FISCO BCOS(十五)——— Windows下的go环境配置及beego环境配置并解决bee run报错问题

1、下载地址 https://golang.google.cn/dl/2、双击打开下载的文件&#xff0c;一路按照默认点击下一步&#xff0c;&#xff08;安装位置可选&#xff0c;默认安装在c盘&#xff09; 3、go环境配置&#xff08;很重要的&#xff09; 在系统变量名中新建变量名&#xff1a;GOP…

Java如何生成花里胡哨的二维码

目录一、序言二、找资料1、寻觅文档2、寻觅代码三、代码示例1、简单的二维码2、带颜色的二维码3、带logo的二维码四、工具类封装一、序言 之前在做头马演讲俱乐部哼哈官可视化汇报报告时&#xff0c;为了方便大家移动端查看可视化报告&#xff0c;而不是通过点击链接这种生硬的…

Android 面试java知识小结

1.-1的二进制是多少&#xff0c;怎么算出来的&#xff1f; 1111 1111 在计算机里是以补码的形式存在的&#xff0c;那为什么要使用补码呢&#xff1f; 计算机中的有符号数有三种表示方法&#xff0c;即原码、反码和补码。三种表示方法均有符号位和数值位两部分&#xff0c;符号…

如何使用界面控件DevExpress WinForms自带的UI模板?其实很简单

DevExpress WinForm拥有180组件和UI库&#xff0c;能为Windows Forms平台创建具有影响力的业务解决方案。DevExpress WinForms能完美构建流畅、美观且易于使用的应用程序&#xff0c;无论是Office风格的界面&#xff0c;还是分析处理大批量的业务数据&#xff0c;它都能轻松胜任…

科研工具总结

科研工具总结 1、论文检索网站2、自己收集数据集----并构建数据集2.1数据集来演方式:3种3、怎么进行一个算法的调研?泛读论文:精读论文:1、论文检索网站 Connected papers:一个基于知识图谱的论文检索网站 特点:圆圈的半径越大表示论文越经典,引用数量比较多; 论文的新…

python与人工智能:KNN近邻法识别手写数字

机器学习分类&#xff1f; 1 特征&#xff08;feature&#xff09; 数据是区分事物和事物的关键。 举例&#xff1a;不同类型的书&#xff0c;我们用书的内容来对它进行分类 2 标签&#xff08;label&#xff09; 数据的标签&#xff0c;显示的分类结果。 举例&#xff1a;书属…

每日面试题2道、算法两道

目录 一、 面试题 i、i的自增问题 写一个Singleton实例 二、数组 算法 寻找数组的中心索引 搜索插入位置 一、 面试题 i、i的自增问题 /*** packageName: com.sofwin.mianshi* user: wentao* date: 2022/10/10 14:31* email 1660420659qq.com* description: i、i的 面…

(附源码)计算机毕业设计SSM志愿者活动管理平台

项目运行 环境配置&#xff1a; Jdk1.8 Tomcat7.0 Mysql HBuilderX&#xff08;Webstorm也行&#xff09; Eclispe&#xff08;IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持&#xff09;。 项目技术&#xff1a; SSM mybatis Maven Vue 等等组成&#xff0c;B/S模式 M…

pytorch:本地使用tensorboard可视化

摘要&#xff1a; tensorboard是tensorflow用来可视化训练和测试过程的模块&#xff0c;而pytorch并没有可视化模块&#xff0c;但是pytoch1.2.0版本以上开始支持tensorboard。 目录一、 安装tensorboard二、 使用tensorboard1、首先导入模块&#xff1a;2、初始化&#xff1a;…

深度神经网络怎么用

深度学习 对硬件的要求 之前热衷于学习理论知识&#xff0c;目前想跑代码了发现不知道从何下手&#xff0c;自己电脑上搭建的平台基本就是个摆设&#xff0c;因为跑不起来呀。今天我们就来看看想做深度学习应该怎么下手。 首先了解下基础知识&#xff1a;1、深度学习用cpu训练…

2.Jenkins项目创建

Jenkins项目创建1.新建项目 2.创建一个freestyle的项目 3.填写描述信息 4.可以选择丢弃旧的构建 每次构建都会产生一个任务&#xff0c;这个任务想保留多少天&#xff0c;可以设置保留构建的天数 保留最大的个数&#xff1a;例如设置为10个&#xff0c;当任务达到了10个之…

Spring Rest Docs使用

今天给大家分享一个能通过代码自动生成文档技术&#xff0c;Spring Rest Doc过在单元测试中额外添加 API 信息描述&#xff0c;从而自动生成对应的文档片段。 下面通过一个简单的例子演示下如何快速上手的。在Spring Boot项目中添加maven 依赖 <dependency><groupId&g…

Android 使用Jenkins 自动化多渠道打包并且分发到蒲公英、下发到钉钉通知【即拿即用】

前言 一、tomcat 安装启动 二、jenkins war 包下载并安装 三、jenkins 配置教程 四、jenkins items 工程配置 五、android gradle 脚本编码 六、分发到蒲公英脚本编码以及七、通知钉钉逻辑编码 前言 Android 在每个版本测试阶段&#xff0c;通常会因为修复BUG 去验证&#x…

理解vue中的.sync和.$emit

首先来说一下 .sync 修饰符的作用 第一步&#xff1a;先用一句话解释 .sync修饰符可以实现子组件与父组件的双向绑定&#xff0c;并且可以实现子组件同步修改父组件的值。 第二步&#xff1a;具体解释 一般情况下&#xff0c;想要实现父子组件间值的传递&#xff0c;通常使用…

英文论文要怎么查重?

英文论文查重和中文查重一样&#xff0c;只是在渠道选择方面会有些许差别。今天就具体聊聊英文论文怎么查重&#xff0c;并向大家推荐几个比较常用的英文论文查重工具。 英文论文怎么查重&#xff1a; 1、论文为什么要查重 2、论文查重的原理 3、英文论文怎么查重 4、选择…

柳州楼顶种植水稻 国稻种芯·中国水稻节:广西12万亩米飘香

柳州楼顶种植水稻 国稻种芯中国水稻节&#xff1a;广西12万亩米飘香 广西新闻网-南国今报柳江讯&#xff08;记者钟华 通讯员梁睿&#xff09;新闻中国采编网 中国新闻采编网 谋定研究中国智库网 中国农民丰收节国际贸易促进会 国稻种芯中国水稻节 中国三农智库网-功能性农业农…

RabbitMQ常用消息模式

目录 1、RabitMQ工作队列 2、交换机 3、RabbitMQ Fanout 发布订阅--- Fanout exchange(扇型交换机) 3.1、创建连接代码 3.1、生产者代码 3.2、消费者代码 4、Direct路由模式 4.1、生产者代码 4.2、消费者代码 5、Topic主题模式 5.1、生产者代码 5.2、消费者代码 1、…

分享两套企业级进销存管理系统源码

▶▶▶▶1&#xff1a;SpringBoot企业级进销存ERP管理系统源码 00189 本系统采用企业级开发标准&#xff0c;使用SpringBoot架构&#xff0c;数据访问层采用Spring Data Jpa&#xff0c;业务控制层采用SpringMvc&#xff0c;安全框架采用Shiro&#xff0c;实现了完整权限系…

风控模型别只会KS、AUC了,来看看其他衡量模型好坏的一些重要指标吧|含实操

当我们训练好一个机器学习模型之后&#xff0c;必然会对模型的综合性能进行评估&#xff0c;针对分类、回归、聚类等不同类型的算法模型&#xff0c;可以采用相关的评价指标&#xff0c;例如分类模型的Accuracy、KS等&#xff1b;回归模型的MAE、MSE等&#xff1b;聚类模型的SS…