当前位置: 首页 > news >正文

C++第二十四弹---从零开始模拟STL中的list(上)

个人主页: 熬夜学编程的小林

💗系列专栏: 【C语言详解】 【数据结构详解】【C++详解】

目录

1、基本结构

2、基本函数实现

2.1、默认构造函数

2.2、尾插数据

3、迭代器的封装

3.1、迭代器的基本结构

3.2、迭代器重载函数的实现

4、迭代器与list进行关联

4.1、使用迭代器打印链表数据

4.2、其他相关函数

总结


1、基本结构

namespace lin
{template<class T>struct ListNode//双向循环链表的基本结构{ListNode<T>* _prev;//前驱指针ListNode<T>* _next;//后继指针T _data;//数据值//不传值时使用T()默认值构造,传值则传值构造ListNode(const T& val = T())//默认构造 + 传值构造:_prev(nullptr),_next(nullptr),_data(val){}};template<class T>struct ListIterator//迭代器封装类,成员都会被调用,因此使用struct{typedef ListNode<T> Node;Node* _node;//结点指针}template<class T>class list//链表模板类,成员变量定义及函数封装{typedef ListNode<T> Node;//将链表结构取别名,简化代码public:typedef ListIterator<T> iterator;//迭代器重命名private:Node* _head;//链表头指针size_t size;//链表长度}
}

上述代码实现了双向循环链表的基本结构,其中包含了四个部分:

1.namespace lin,命令空间 lin 是用于封装代码,避免同名类型和函数冲突

2.在命名空间中,定义了模板类ListNode(双向循环链表基本结构),该类包含三个成员变量:

  • _prev : 存储指向前一个结点的指针
  • _next : 存储指向后一个结点的指针
  • _data : 存储数据

ListNode类还实现一个有缺省值(T())的构造函数,如果构造函数没有提供参数,则使用T类型的默认构造来初始化_data,如果传值则使用该值来初始化_data,该构造函数也会将_prev和_next指针指向nullptr。

3.模板类ListIterator(迭代器封装),该类包含一个成员变量,即链表的结点指针:

为什么链表需要封装一个迭代器的类呢???

  1. 链表的物理空间是不连续的,是通过结点的指针依次链接。
  2. 不能像string和vector一样直接解引用去访问其数据
  3. 结点的指针解引用还是结点结点指针++还是结点指针。
  4. 在string和vector的物理空间是连续的,所以这俩不需要实现迭代器类,可以直接使用。

4.模板类list(链表的基本成员变量及其函数接口),该类包含两个成员变量:

  • _head : 链表的头结点指针
  • _size : 链表的长度

2、基本函数实现

注意:我们实现的是带头双向循环链表。

2.1、默认构造函数

list()

默认构造的函数功能是构造一个没有元素的空容器。

思路:我们实现的是带头双向循环链表,因此默认构造时我们需要创建(new)一个头结点,并将链表长度初始化为0。

//构造头结点函数
void empty_init()
{_head = new Node;//创建新结点_head->_next = _head;_head->_prev = _head;_size = 0;
}//默认构造 构造一个头结点
list()
{empty_init();
}

为了后序使用方便,我们将构造头结点封装成了一个函数。 

 2.2、尾插数据

为什么在第二个函数就写尾插呢?因为后面的函数会大量用到尾插函数。

push_back()

思想:

  • 先找到尾结点,即头结点的前一个结点。
  • 然后将尾结点,新结点以及头结点进行链接。
void push_back(const T& val)
{//tail _head->_prevNode* tail = _head->_prev;Node* newnode = new Node(val);//创建一个值为val的新结点//tail newnode _head //链接关系的顺序tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;_size++;//尾插之后长度要++
}

我们尾插完数据之后,想要遍历整个链表怎么遍历呢???

我们在使用链表的时候是通过迭代器进行遍历,如下代码:

void test_list1()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;cout << lt.size() << endl;
}

此时我们就需要对链表的迭代器进行封装!!!

3、迭代器的封装

此时的迭代器是一个结点指针(Node*)。

3.1、迭代器的基本结构

template<class T>
struct ListIterator
{typedef ListNode<T> Node;//类型起别名Node* _node;//成员变量ListIterator(Node* node)//构造函数:_node(node){}
};

但是我们使用迭代器时,是在list内部进行使用的,且类型名称为iterator,因此需要在list内部重命名迭代器类型(公有的,因为我们需要在类外访问)。

template<class T>
class list 
{
public:  typedef ListIterator<T> iterator;//迭代器重命名
};

迭代器实质是一个结点指针,因此类的成员是_node(结点指针),此处我们使用一个结点的指针对其初始化。

typedef ListNode<T> Node;//类型起别名Node* _node;//成员变量ListIterator(Node* node)//构造函数:_node(node){}

3.2、迭代器重载函数的实现

前置++

先++,再使用返回的是++后的结点,用引用返回。

//前置++
typedef ListIterator<T> Self//对返回迭代器类型重命名,因为原类型较长
Self& operator++()
{_node = _node->_next;return *this;
}

后置++

先使用,再++返回的是++前的结点,传值返回。

typedef ListIterator<T> Self
Self operator++(int)
{Self tmp(*this);//构造一个临时变量存储之前的结点_node = _node->_next;return tmp;//返回临时对象
}

注意:前置和后置的区别是,后置需要在形参中传一个占位符,一般使用int类型。

 前置--

先--,再使用返回的是--后的结点,用引用返回。

Self& operator--()
{_node = _node->_prev;return *this;
}

 后置--

先使用,再++返回的是++前的结点,传值返回。

Self operator--(int)
{Self tmp(*this);_node = _node->_prev;return tmp;
}

为什么前置++返回的是类对象引用,而后置++返回的是结点类型呢???

因为在前置++中,我们返回的是类本身,而后置++,我们返回的是一个局部的类对象,局部的类对象出了函数会自动销毁。 

operator*

 对该迭代器位置的数据进行解引用类似与指针解引用。

T& operator*()//遍历及修改
{return _node->_data;//访问链表的data数据
}

 operator!=

重载两个迭代器不相等指针不相等则返回true,相等则返回false。

bool operator!=(const Self& lt)
{return _node != lt._node;//两个迭代器不相等即指针不相等
}	

operator==

bool operator==(const Self& lt)
{return _node == lt._node;
}

 注意:比较迭代器是否相等比较的是的地址。

4、迭代器与list进行关联

4.1、使用迭代器打印链表数据

void test_list1()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;cout << lt.size() << endl;
}

根据打印的测试函数我们可以知道,我们需要获取链表的第一个结点的迭代器(即第一个结点的地址),但是这个地址只有在list类中有,因此我们需要在list类中封装一个获取第一个结点的迭代器(begin),获取end()也是同理。

begin() 

第一个结点的迭代器,即头结点的下一个位置(_head->next)。

iterator begin() 
{return iterator(_head->_next);//调用迭代器类的构造函数//return _head->next;//单参数的隐式类型转换
}

 end()

最后一个结点的下一个位置,即_head位置。

iterator end()
{return iterator(_head);//return _head;
}

封装完迭代器之后我们就可以进行打印了。 

list类代码:

template<class T>
class list
{typedef ListNode<T> Node;
public:typedef ListIterator<T> iterator;iterator begin() //打印链表时,只能访问数据,不能修改内容及指向的内容{return iterator(_head->_next);}iterator end(){return iterator(_head);}
private:Node* _head;//链表头指针size_t _size;//链表大小
};

 测试结果:

4.2、其他相关函数

insert()

在pos位置之前插入val。

思路:

  • 先获取当前结点的地址
  • 然后通过前驱指针找到前面一个结点的地址
  • 再创建一个新的结点
  • 最后将前驱结点,新结点,当前结点构成链接关系
void insert(iterator pos, const T& val)//在pos位置前面插入val
{Node* cur = pos._node;//当前结点指针Node* prev = cur->_prev;Node* newnode = new Node(val);//prev newnode curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;
}

erase()

删除pos位置的值,并返回删除前的下一个结点的地址。

思路:

  • 先获取当前结点的地址
  • 然后通过前驱指针找到前一个结点地址,通过后继指针找到后一个结点的地址
  • 将prev 前驱指针与后继指针建立链接关系
  • 释放当前结点
  • 返回next结点
iterator erase(iterator pos)//删除pos位置值,迭代器失效问题
{Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;//prev nextprev->_next = next;next->_prev = prev;delete cur;_size--;return iterator(next);//返回迭代器中结点指针
}

头插尾插头删尾删

复用insert()函数和erase()函数实现。

void push_back(const T& val)
{insert(end(), val);//end()之前插入
}
void push_front(const T& val)
{insert(begin(),val);//begin()之前插入
}
void pop_back()
{erase(--end());//删除end前面一个结点
}
void pop_front()
{erase(begin());//删除begin位置结点
}

总结


本篇博客就结束啦,谢谢大家的观看,如果公主少年们有好的建议可以留言喔,谢谢大家啦!

相关文章:

C++第二十四弹---从零开始模拟STL中的list(上)

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】【C详解】 目录 1、基本结构 2、基本函数实现 2.1、默认构造函数 2.2、尾插数据 3、迭代器的封装 3.1、迭代器的基本结构 3.2、迭代器重载函数的实现 4、迭…...

大宋咨询(深圳社情民意调查)关于社情民意调查研究的内容

社情民意调查内容&#xff0c;是一项至关重要的社会研究活动&#xff0c;它涵盖了社会生活的方方面面&#xff0c;通过深入了解民众的需求、态度和看法&#xff0c;为决策提供了宝贵的参考依据。 首先&#xff0c;社会经济状况是社情民意调查不可或缺的一部分。这包括了对当地…...

PID算法在电机速度控制上的应用

目录 概述 1 系统硬件框架 1.1 框架介绍 1.2 硬件实物图 2 STM32Cub生成工程 2.1 软件版本信息 2.2 配置参数 ​编辑2.3 生成项目 3 PID算法实现 3.1 概念 3.2 代码实现 4 其他功能实现 4.1 设置电机速度 4.2 PID算法控制电机 4.3 功能函数的调用 5 测试 5.1 …...

埃隆·马斯克 - 从梦想家到改变世界的企业家

埃隆马斯克 - 从梦想家到改变世界的企业家 本文内容是埃隆马斯克传的重点章节精华提炼&#xff0c;介绍了马斯克传奇一生 参考资料内容&#xff1a;埃隆马斯克传&造梦者埃隆马斯克 参考资料在文末获取&#xff0c;关注我&#xff0c;分享优质前沿资料&#xff08;IT、运…...

微信小程序长图片自适应

/*wxss中的代码*/ .image-container { display:flex;width: 100%; /* 或其他需要的宽度 */ /* margin-bottom: 10px; //图片之间的间距 */height: auto; } 核心&#xff1a;要真正自适应&#xff0c;就要在wxml中加入固定宽度style“width:750rpx” /*wxml中的代码*/ &l…...

elasticsearch hanlp 插件安装操作

elasticsearch hanlp 插件安装操作 下载 hanlp 插件上传hanlp插件到elasticsearch服务器安装hanlp插件kibana测试 下载 hanlp 插件 这里大家根据自己对应的 elasticsearch 版本下载匹配版本的 hanlp 插件&#xff0c;由于 hanlp 及 elasticsearch 各个版本之间差别较大&#x…...

为什么进程和线程 ID 总是 4 的倍数?

如果您研究下任务管理器中的的进程 ID (PID)&#xff0c;则你会发现这样一个规律&#xff1a;它们都是 4 的倍数。 基于 Windows NT 内核的操作系统上&#xff0c;不止是进程 ID&#xff0c;实际上&#xff0c;线程 ID (TID) 也遵守这样的规律&#xff1a;也即它们都是 4 的倍…...

LabVIEW版本控制

LabVIEW作为一种流行的图形化编程环境&#xff0c;在软件开发中广泛应用。有效地管理版本控制对于确保软件的可靠性和可维护性至关重要。LabVIEW提供了多种方式来管理VI和应用程序的修订历史&#xff0c;以满足不同规模和复杂度的项目需求。 LabVIEW中的VI修订历史 LabVIEW内置…...

不输Kimi的AI插件——Elmo Chat (免费,无需注册)

&#x1f31a; 前阵子不是写了篇《一分钟上手AI神器——Kimi (附_ 官方提示词)》 嘛&#xff0c;给大伙安利了一波 Kimi Chat 这个AI 神器&#xff0c;不知道是不是用户量上来了&#xff0c;算力一下子跟不上&#xff0c;感觉变笨了不少&#x1f923;。在别的推文看到多轮对话后…...

使用cesiumLab使shp转为3dtlies

过程不做赘述&#xff0c;网上大把&#xff0c;说下注意事项。 1. 存储3DTiles 选项 若是打开则输出的文件为glb格式文件,因为glb文件好储存易传输跨平台。cesium可以使用但无法处理&#xff0c;例如改变颜色&#xff0c;改着色器等。若是不打开则输出的文件为bm3d格式文件,此…...

中科数安 | 透明加密防泄密系统!如何有效防止企业内部核心数据资料外泄?

中科数安提供的透明加密防泄密系统是一种专为企业设计的数据保护解决方案&#xff0c;它通过以下关键特性有效防止企业内部核心数据资料外泄&#xff1a; PC地址&#xff1a;——www.weaem.com 自动智能透明加密&#xff1a;系统能够在操作系统级别无缝集成&#xff0c;对指定类…...

go的反射和断言

在go中对于一个变量&#xff0c;主要包含两个信息变量类型&#xff08;type&#xff09;和变量值&#xff08;value&#xff09; 可以通过reflect包在运行的时候动态获取变量信息&#xff0c;并能够进行操作 对于Type可以通过reflect.TypeOf()获取到变量的类型信息 reflect.Ty…...

打造新引擎,迈向数智金融新未来

数智技术正在全面赋能金融机构转型升级以及促进金融与实体经济的加速融合&#xff0c;已呈现出金融机构数智化经营加速、产业 数字金融深度融合、数字技术驱动绿色金融发展、金融信创成果涌现、金融机构加快数字化组织管理变革等行业趋势。 根据银行业协会调研&#xff0c;78%…...

广东智慧物流2024年端午节放假安排

广东智慧物流2024年端午节放假安排...

Facebook的隐私保护挑战:用户数据安全的新时代

在全球范围内&#xff0c;Facebook已经成为了不可忽视的社交媒体巨头&#xff0c;它连接着超过20亿的活跃用户。然而&#xff0c;随着其影响力的不断扩大&#xff0c;关于用户隐私和数据安全的问题也愈加引人关注。本文将深入探讨Facebook面临的隐私保护挑战&#xff0c;以及它…...

Gradio.NET:一个快速制作演示demo网页的利器

Gradio介绍 Gradio是一个用于创建机器学习模型交互界面的Python库。它允许开发者快速为他们的模型创建一个简单的web界面&#xff0c;以便于非技术用户和其他开发者进行交互和测试。 Gradio的主要优点是易用性和灵活性。你只需要几行代码就可以为你的模型创建一个交互界面。你…...

001 IOC与DI(有点杂)

文章目录 IOC与DI区别联系总结 依赖注入解耦管理对象的生命周期提高配置灵活性三种注入方式不可变对象的设计 构造器注入Setter方法注入字段注入Setter方法注入为什么不破坏封装性字段注入为什么破坏封装性为什么将字段或setter方法设置为private&#xff1f;总结 setter方法注…...

Python语言自学:深入探索四个基础、五个进阶、六个实战及七个挑战

Python语言自学&#xff1a;深入探索四个基础、五个进阶、六个实战及七个挑战 Python&#xff0c;作为一种通用编程语言&#xff0c;其简洁的语法、丰富的库和强大的功能&#xff0c;使得越来越多的人选择自学Python。但自学之路并非坦途&#xff0c;本文将从四个方面、五个方…...

运维开发介绍

目录 1.什么是运维开发 2.作用 3.优点 4.缺点 5.应用场景 5.1.十个应用场景 5.2.网站和Web应用程序 6.案例 7.小结 1.什么是运维开发 运维开发&#xff08;DevOps&#xff09;是一种结合软件开发&#xff08;Development&#xff09;与信息技术运维&#xff08;Opera…...

Mac版的Typora的安装和激活(亲测可用哦~~~)

星光下的赶路人star的个人主页 珍视生活中的苦与乐&#xff0c;悦纳生活的悲伤离合 文章目录 1.下载2.安装3.激活4.注意点 1.下载 直接官网下载即可&#xff01;&#xff01;&#xff01; 官网地址&#xff1a;typora官网 2.安装 直接拖进去安装即可 3.激活 1.利用访达进入…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向

在人工智能技术呈指数级发展的当下&#xff0c;大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性&#xff0c;吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型&#xff0c;成为释放其巨大潜力的关键所在&…...