C++语言·list链表(下)

        还是之前说的,因为要写模板,为了避免链接出现问题,我们将所有内容都写到一个文件中去。首先就是画出链表的框架

                

        链表本身只需要一个头节点就足以找到整条链表,而需要它拼接的节点我们再写一个模板。而我们知道list是一个带头双向循环链表,所以再写节点模板是时候将要表现出来双向,在写链表模板的时候要表现出带头和循环。

        之所以要把ListNode设定成struct而不是class,因为再list中的成员函数中要反复访问节点中的成员变量,所以ListNode中的成员变量和成员函数都要设置成public公有的,所以干脆就直接写成struct了。

        本节的重点也是难点就是链表的迭代器

1. 迭代器

        构造析构还有那些接口我们已经熟的不能再熟了,之后再说,这里我们直接进入重点。

        之前 string 和 vector 的迭代器我们都是直接 typdef 出来的,那list的迭代器可不可以也这样做。

                        

        答案当然是不行,前两者都是因为它们的存储空间是在物理上连续的,所以在 ++iterator的时候可以直接访问到下一块内存,显然链表是不行的,因此我们要给链表的迭代器特别写一个类出来,为了重载iterator的 ++iterator *iterator等行为

        这里不建议把这个迭代器写成list的内部类,因为写成内部类之后迭代器不是list的友元啊,之后操作迭代器就会变得异常麻烦。

        ​​​​​​​        ​​​​​​​

        链表的迭代器我们选择用节点的指针。现在我们将迭代器的结构描绘出来,然后记得在list类中typedef一下,达到容器中迭代器的名称一致。

        下面我们实现迭代器类,主要就是重载迭代器的几种操作方式

        ​​​​​​​        ​​​​​​​

        我们的迭代器是不去支持 + 或 - 的因为这个效率很低,就是在O(N)时间复杂度的遍历链表,拷贝构造,析构和赋值也都不需要写,让编译器自动生成浅拷贝就行,因为迭代器的目的是去访问节点,而不是去修改,也不要释放。当然,解引用访问到某个节点之后进行的修改不是说迭代器在修改节点数据,而是利用迭代器访问到了节点之后,在节点中修改它的数据。

        其实迭代器这个东西就是一种封装,Node*指针无法直接完成下一块空间的访问,因此我们就将Node*封装到迭代器中,并且在迭代器中重载实现访问下一块空间的方法。

1.1 begin() end()

                

        end()取出的迭代器就是那个头节点或者说哨兵位,因为迭代器都是左闭右开的嘛

1.2 const_iterator

        因为迭代器跟指针的效果是类似的,const迭代器起到一个迭代器本身可以修改但是其指向内容不能修改的效果,所以const迭代器我们不能在iterator前面简单加一个const,而是要再写一个专门的ListConstIterator类。

        这个类其实和普通的内容都基本一样,我们只需要在*运算符重载的函数前面加const限制返回值就好了。

        ​​​​​​​        ​​​​​​​        

        不过我更推荐的是将const和非const的迭代器类用模板写在一起

        

        在list类中实例迭代器的时候将它们区分开

        ​​​​​​​

        那个Ptr模板是重载->操作符用的,具体内容可以到最后完整代码中查看

2. 构造 析构 赋值操作符重载

2.1 默认构造

        ​​​​​​​        

        默认构造就是建立出那个头节点,或者说哨兵位。

2.2 析构

                 

        我们先写一个清空容器的函数clear,析构就是把容器清空之后再把头节点哨兵位释放掉。

2.3 拷贝构造

        ​​​​​​​        ​​​​​​​        

2.4 赋值操作符重载

                

2.5 initializer_list构造

                

3. 插入与删除

3.1 随机位置插入

        ​​​​​​​        

        双向链表的插入逻辑我就不讲了,详见数据结构章节的链表讲解

数据结构·双向链表-CSDN博客文章浏览阅读1k次,点赞18次,收藏16次。本节讲解了双向链表的结构,以及实现了一个双向链表及功能,不得不说双向链表比单链表写起来简单多了,没有那么多繁琐的条件判断https://blog.csdn.net/atlanteep/article/details/135880386        这里要说的问题就是链表插入时的迭代器会不会失效,事实上是不会的,因为链表不涉及扩容和数据位置的挪动,所以在插入数据的时候迭代器是不会失效的。

        但是在STL标准中,为了各个容器的一致,链表insert也会返回第一个新插入元素的迭代器

3.2 随机位置的删除

        ​​​​​​​        

        随机位置的删除我们要先断言一下,不能说把哨兵位都给删了。

        删除节点是会造成迭代器失效的,STL标准中要返回被删除的最后一个元素之后那个元素的迭代器。

        

3.3 头插头删、尾插尾删

                

        这个纯白给的,只不过注意一下尾删时,要删除哨兵位的前一个节点,而不是删end()位置的节点。

4. 完整代码

#include<assert.h>namespace atl
{template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& data = T()):_next(nullptr), _prev(nullptr), _data(data){}};template<class T,class Ref,class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;Node* _node;ListIterator() = default;ListIterator(Node* node):_node(node){}//++iteratorSelf& operator++(){_node = _node->_next;return *this;}//iterator++Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}//--iteratorSelf& operator--(){_node = _node->_prev;return *this;}//iterator--Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}//*iteratorRef operator*(){return _node->_data;}//iterator->Ptr operator->(){return &_node->_data;}//iterator!=iteratorbool operator!=(const Self& it){return _node != it._node;}//iterator==iteratorbool operator==(const Self& it){return _node == it._node;}};template<class T>class list{typedef ListNode<T> Node;public://迭代器typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;iterator begin(){return iterator(_head->_next);}const_iterator begin() const{return const_iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator end()const{return const_iterator(_head);}//默认构造list(){_head = new Node();_head->_next = _head;_head->_prev = _head;}//析构void clear(){auto it = begin();while (it != end()){it = erase(it);}}~list(){clear();delete _head;_head = nullptr;}//拷贝构造list(const list<T>& lt){//创建头节点_head = new Node();_head->_next = _head;_head->_prev = _head;for (const auto& e : lt){push_back(e);}}//赋值操作符重载list<T>& operator=(list<T> lt){std::swap(_head, lt._head);return *this;}//initializer_list构造list(initializer_list<T> il){//创建头节点_head = new Node();_head->_next = _head;_head->_prev = _head;for (const auto& e : il){push_back(e);}}//没有迭代器失效//随机位置插入iterator insert(iterator pos,const T& x){Node* cur = pos._node;Node* newnode = new Node(x);newnode->_prev = cur->_prev;newnode->_next = cur;cur->_prev->_next = newnode;cur->_prev = newnode;return iterator(newnode);}//有迭代器失效//随机位置删除iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;//记录将要返回的迭代器iterator it((cur->_next));cur->_next->_prev = cur->_prev;cur->_prev->_next = cur->_next;delete cur;return it;}//尾插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());}private:Node* _head;};
}

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

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

相关文章

微信小程序对接发货功能

注&#xff1a;微信小程序对接发货功能 文档地址&#xff1a;https://developers.weixin.qq.com/miniprogram/dev/platform-capabilities/business-capabilities/order-shipping/order-shipping.html php代码 common.php use think\Config; use think\Db; use fast\Http; us…

OrangePi AIpro 变身 Android 打包机

主板基本信息介绍 OrangePi AIpro&#xff0c;是香橙派联合华为精心打造&#xff0c;建设人工智能新生态而设计的一款开发板&#xff0c;这次为大家分享下我上手的这款 OrangePi AIpro 8GB&#xff08;算力达8TOPS&#xff09; 的一些小小的经验。 基本参数如下&#xff1a; …

【Keil 5】Keil 5下载安装激活到2032年(含MDK、C51、STM32单片机)+附带百度网盘链接

这里写目录标题 安装包、激活文件下载1.双击mdk 514开始安装2.一路点next&#xff0c;信息随便写即可3.激活4.安装STM325.激活c51 安装包、激活文件下载 解压密码&#xff1a;lantongxue 链接&#xff1a;https://pan.baidu.com/s/15Aukt0j1HCFyHBE6whuDeg?pwdsjyh 提取码&…

FreeRtos进阶——中断的内部逻辑

中断与非中断API的区别 BaseType_t xQueueSendToBack(QueueHandle_t xQueue,const void *pvItemToQueue,TickType_t xTicksToWait); BaseType_t xQueueSendToBackFromISR(QueueHandle_t xQueue,const void *pvItemToQueue,BaseType_t *pxHigherPriorityTaskWok…

OceanBase 内存研究(OceanBase 3.2.4.5)

内存结构 从官网的结构图可以看出&#xff0c;一台observer可使用的总内存(memory_limit)包括 系统内存(system_memory) 和 租户内存(sys租户与普通租户) 系统内存 系统内存system_memory 属于 observer 的内部内存&#xff0c;允许其它租户共享使用该内存资源 (root10.0.0.…

丛林生存法则其实就两个字:输出

不管你是在上班&#xff0c;还是在灵活就业&#xff0c;现在的大环境下&#xff0c;你要想活下来&#xff0c;生存下去&#xff0c;一定要记住这两个字&#xff1a;输出。如果你能记住更多的字&#xff0c;那便是持续高水平的输出。 你如果是大厂程序员&#xff0c;你肯定发现…

window安装ffmpeg播放本地摄像头视频

1、安装ffmpeg ffmpeg官方网站&#xff1a;FFmpeg 下载后解压文件夹名为ffmpeg 2、设置环境变量 目录 1、安装ffmpeg 设置环境变量 以F:\software\after\ffmpeg\bin为例 在命令行中输入ffmpeg出现下方代表安装成功 3、通过ffmpeg播放本地电脑摄像头 鼠标右击开始按钮&…

快速排序详讲(两种方法)

目录 原理 实现方式 正常实现 理由 先从右到左&#xff0c;在从左到右 先从左到右&#xff0c;先从右到左 挖坑法 效率 优化 测试 代码 原理 快速排序是将最左侧的数字当作关键数字&#xff0c;将关键数字放在对应位置&#xff0c;且关键数字左侧均大于它&#xff…

Spring Boot 开发 -- 过滤器与拦截器详解

引言 在Web开发中&#xff0c;经常需要对请求进行预处理或在响应后进行后处理&#xff0c;Spring Boot提供了过滤器和拦截器两种机制来实现这一需求。虽然它们都可以用来处理HTTP请求和响应&#xff0c;但在使用场景、执行顺序和配置方式上存在明显的差异。本文将详细讲解Spri…

江苏大信环境科技有限公司:环保领域的开拓者与引领者

2009 年&#xff0c;江苏大信环境科技有限公司在宜兴环保科技工业园成立。自创立之始&#xff0c;该公司便笃定坚守“诚信为本、以质量求生存、以创新谋发展”这一经营理念&#xff0c;全力以赴为客户构建专业的工业有机废气治理整体解决方案&#xff0c;进而成为国家高新技术企…

安全风险 - 组件导出风险

在安全审查中关于组件导出风险是一种常见问题&#xff0c;不同组件都有可能遇到这种问题&#xff0c;而且从一定角度来看的话&#xff0c;如果涉及到三方业务&#xff0c;基本处于无法解决的场景&#xff0c;所以我们需要说明为何无法避免这种风险 组件导出风险能不能规避&…

海康 面阵相机命名规则

海康 面阵相机命名规则 https://www.v-club.com/vCollage/vCollageDetail/516?subjectIdRMse6nPiyo

能不能接受这些坑?买电车前一定要看

图片来源&#xff1a;汽车之家 文 | Auto芯球 作者 | 雷慢 刚有个朋友告诉我&#xff0c;买了电车后感觉被骗了&#xff0c; 很多“坑”都是他买车后才知道的。 不提前研究&#xff0c;不做功课&#xff0c;放着我这个老司机不请教&#xff0c; 这个大冤种他不当谁当&…

Linux系统编程——动静态库

目录 一&#xff0c;关于动静态库 1.1 什么是库&#xff1f; 1.2 认识动静态库 1.3 动静态库特征 二&#xff0c;静态库 2.1 制作静态库 2.2 使用静态库 三&#xff0c;动态库 3.1 制作动态库 3.2 使用动态库一些问题 3.3 正确使用动态库三种方法 3.3.1 方法一&…

ADC数模转换器

一、ADC&#xff08;Analog-Digital Converter&#xff09;模拟-数字转换器 1、ADC可以将引脚上连续变化的模拟电压转换为内存中存储的数字变量&#xff0c;建立模拟电路到数字电路的桥梁 2、12位逐次逼近型ADC&#xff0c;1us转换时间 3、输入电压范围&#xff1a;0~3.3V&a…

Oracle dblink 发现Network 等待事件的分析 enq: KO - fast object checkpoint

所有的sql 通过dblink 查询全部等待中&#xff0c; 同一个SQL 20多个session 在跑&#xff0c;等待事件network&#xff0c;可能怀疑是不是网络断开了&#xff0c;导致没有返回 执行sql 如下&#xff1a; BEGIN Xdblink ; END; 去到dblink 所在的db&#xff0c;发现20多个sql在…

远程继电器模块实现(nodemcu D1 + 继电器)

前言 接下来将实现一个远程继电器&#xff0c;实时远程控制和查询的开关状态。用 5v 直流电控制 220v 交流电。 硬件上&#xff1a; 使用 nodemcu D1 和 JQC-3FF-S-Z 继电器。 软件上&#xff1a; 使用 nodejs 作为服务端&#xff0c;和 html 作为客户端。 在开始之前在电脑…

基于Qt GraphicView 解析 CIM/G 电力接线图文件

本文讲述了如何使用Qt的框架来渲染展示标准的CIM/G格式的图形文件&#xff0c;也就是公用信息模型&#xff08;common information model&#xff0c;CIM&#xff09;中的G文件部分的内容。这是一种电力系统图形的交换规则&#xff0c;用于电网图形交换。 [by amjieker] CIM/G …

⌈ 传知代码 ⌋ 命名实体识别

&#x1f49b;前情提要&#x1f49b; 本文是传知代码平台中的相关前沿知识与技术的分享~ 接下来我们即将进入一个全新的空间&#xff0c;对技术有一个全新的视角~ 本文所涉及所有资源均在传知代码平台可获取 以下的内容一定会让你对AI 赋能时代有一个颠覆性的认识哦&#x…

vue3组件传值---vue组件通过属性,事件和provide,inject进行传值

通过属性传值&#xff08;父传子&#xff09; vue的组件具有props自建属性&#xff08;自定义名称&#xff0c;类似于class&#xff0c;id的属性&#xff09;&#xff0c;通过这个属性&#xff0c;父组件可以向子组件传递参数&#xff0c;从而实现组件之间的信息传递&#xff0…