【C++】STL——list底层实现
目录
💕1.list的三个类介绍
💕2.list——节点类 (ListNode)
💕3.list——链表类 (List)
💕4.list——迭代器类(重点思考)(ListIterator)
💕5. list遍历(迭代器,const迭代器)
💕6.整体代码
💕7.测试用例
💕8.完结
一个人的坚持到底有多难
声明:此文内容基于此文章->:【C++】STL——list的使用
💕1.list的三个类介绍
在list中存在着三个类,而我们使用的list就是这三个类相辅相成形成的功能
它们分别是节点类,链表类,迭代器类
节点类用来代表每一个节点的内容
迭代器类用来实现链表的遍历,成员为单个节点的地址
而链表类就是用来实现各种链表功能,成员为头结点
💕2.list——节点类 (ListNode)
节点类是每一个节点的内容,因此需要有前一个节点的地址,后一个节点的地址,以及数据
但因为它的内容需要频繁运用,因此最好用struct,struct中所有都为public,因此很方便,当然class也没有问题,只不过需要显示public
因此需要这样写->:
template<class T> struct ListNode {ListNode* prev;ListNode* next;T data;//1.T& x可以让形参不开辟新的空间,时间和空间上都有节省//2.const保护引用不被修改//3.T()是因为节点内容不一定是什么类型,而T()可以更好地初始化//例:int(),自动初始化为0,double(),string()ListNode(const T& x = T()):data(x),prev(nullptr),next(nullptr){} };
💕3.list——链表类 (List)
链表类的实现主要是具体功能,而我们知道链表是有一个头结点的,因此可以在链表类中实现
template<class T>class List{typedef ListNode<T> Node;//将节点类重命名为Node//创建头节点,让其指向自己List(){phead = new Node();phead->next = phead;phead->prev = phead;}private:Node* phead;};
💕4.list——迭代器类(重点思考)(ListIterator)
迭代器类需要实现的是链表的遍历,想要实现遍历,必不可少的就是begin()函数,正常来说,begin()函数的返回类型应该是节点的地址,但是仔细思考一下,如果返回的是节点的地址,那这个节点的地址++后,不一定是下一个节点的地址,因此,begiin()函数不应该使用节点的地址作为返回值
新的思路:我们可以利用对象进行遍历,什么意思?
我们在进行遍历时,每一次begin()返回的是一个对象,通过访问这个对象中的节点地址,加上运算符重载,来进行遍历,因为利用这个对象中的节点地址,就进而可以通过这个节点地址访问到节点的数值
因此可以这样写->:
template<class T>struct ListIterator{typedef ListNode<T> Node;Node* node;//单个节点的地址};
为什么是结构体?先不要在意,请看后面
💕5. list遍历(迭代器,const迭代器)
我们的思路是,通过对象进行遍历,因此我们需要实现对象的++,--运算符重载,来一个一个的遍历每一个节点对象
template<class T>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T> Self;ListIterator(Node* x){node = x;}//前置++,作用是遍历,不可以返回节点地址,因为无法进行下一次++,不一定会指向下一个节点//利用对象进行遍历,因此返回的应该是一个对象,迭代器类的对象,因为要用迭代器类中的单个节点的地址来遍历Self& operator++(){node = node->next;return *this;}Self& operator--(){node = node->prev;return *this;}//后置--//后置--需要利用一个临时变量来表示原来的值,首先传参传给来的是对象的地址,即thisSelf operator--(int){//Self* tep = this;//这种写法不可取,因为两块地址一样,任意一个修改全修改了所以没区别Self tep(*this);//拷贝构造函数创建临时对象,但是需要注意区分,这个对象的地址和*this的地址是不一样的,但是它们里面的node地址是一样的node = node->prev;return tep;//后置的返回值不可以用引用,因为临时变量tep出了函数就销毁了,用引用会导致空引用}Self operator++(int){//Self* tep = this;//这种写法不可取,因为两块地址一样,任意一个修改全修改了所以没区别Self tep(*this);//拷贝构造函数创建临时对象,但是需要注意区分,这个对象的地址和*this的地址是不一样的,但是它们里面的node地址是一样的node = node->next;return tep;}T& operator*(){return this->node->data;}bool operator!=(const Self& it){return this->node != it.node;}bool operator==(const Self& it){return this->node == it.node;}Node* node;//单个节点的地址};
接下来是begin函数与end函数,写在List类中iterator begin(){//phead->next的类型是Node*类型,而返回类型需要是iterator类型,也就是对象//利用匿名对象,将phead->next传给ListIterator的构造函数,使它变为一个匿名对象,再return回去return iterator(phead->next);}iterator end(){return iterator(phead);}
如何实现const迭代器?
我们可以新建一个const的迭代器类,通过const修饰constIterator类中的成员变量,进而实现const迭代器的效果
具体实现如下->:
// 新增 const 迭代器 template<class T> struct ListConstIterator {typedef const ListNode<T> Node;typedef ListConstIterator<T> Self;ListConstIterator(Node* x):node(x){}// 前置++Self& operator++(){node = node->next;return *this;}Self& operator--(){node = node->prev;return *this;}// 后置++Self operator++(int){Self tep(*this);node = node->next;return tep;}Self operator--(int){Self tep(*this);node = node->prev;return tep;}const T& operator*() const{return node->data;}bool operator!=(const Self& it) const{return node != it.node;}bool operator==(const Self& it) const{return node == it.node;}//把节点定义为const类,因为const迭代器要实现的是const T* ,限制的是解引用const Node* node; };
template<class T> class List {public:typedef ListNode<T> Node;//将节点类重命名为Nodetypedef ListIterator<T> iterator;//将迭代器类重命名为iteratortypedef ListConstIterator<T> const_iterator; // 新增 const_iterator//创建头节点,让其指向自己const_iterator begin() const{return const_iterator(phead->next);}const_iterator end() const{return const_iterator(phead);} };
至此难点就全部完成了,剩下的就只剩拷贝构造等,看看整体代码即可
💕6.整体代码
#pragma #include<assert.h> namespace yzq {template<class T>struct ListNode{ListNode* prev;ListNode* next;T data;//1.T& x可以让形参不开辟新的空间,时间和空间上都有节省//2.const保护引用不被修改//3.T()是因为节点内容不一定是什么类型,而T()可以更好地初始化//例:int(),自动初始化为0,double(),string()ListNode(const T& x = T()):data(x),prev(nullptr),next(nullptr){}};template<class T>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T> Self;ListIterator(Node* x){node = x;}//前置++,作用是遍历,不可以返回节点地址,因为无法进行下一次++,不一定会指向下一个节点//利用对象进行遍历,因此返回的应该是一个对象,迭代器类的对象,因为要用迭代器类中的单个节点的地址来遍历Self& operator++(){node = node->next;return *this;}Self& operator--(){node = node->prev;return *this;}//后置--//后置--需要利用一个临时变量来表示原来的值,首先传参传给来的是对象的地址,即thisSelf operator--(int){//Self* tep = this;//这种写法不可取,因为两块地址一样,任意一个修改全修改了所以没区别Self tep(*this);//拷贝构造函数创建临时对象,但是需要注意区分,这个对象的地址和*this的地址是不一样的,但是它们里面的node地址是一样的node = node->prev;return tep;//后置的返回值不可以用引用,因为临时变量tep出了函数就销毁了,用引用会导致空引用}Self operator++(int){//Self* tep = this;//这种写法不可取,因为两块地址一样,任意一个修改全修改了所以没区别Self tep(*this);//拷贝构造函数创建临时对象,但是需要注意区分,这个对象的地址和*this的地址是不一样的,但是它们里面的node地址是一样的node = node->next;return tep;}T& operator*(){return this->node->data;}bool operator!=(const Self& it){return this->node != it.node;}bool operator==(const Self& it){return this->node == it.node;}Node* node;//单个节点的地址};// 新增 const 迭代器template<class T>struct ListConstIterator{typedef const ListNode<T> Node;typedef ListConstIterator<T> Self;ListConstIterator(Node* x):node(x){}// 前置++Self& operator++(){node = node->next;return *this;}Self& operator--(){node = node->prev;return *this;}// 后置++Self operator++(int){Self tep(*this);node = node->next;return tep;}Self operator--(int){Self tep(*this);node = node->prev;return tep;}const T& operator*() const{return node->data;}bool operator!=(const Self& it) const{return node != it.node;}bool operator==(const Self& it) const{return node == it.node;}//把节点定义为const类,因为const迭代器要实现的是const T* ,限制的是解引用const Node* node;};template<class T>class List{public:typedef ListNode<T> Node;//将节点类重命名为Nodetypedef ListIterator<T> iterator;//将迭代器类重命名为iteratortypedef ListConstIterator<T> const_iterator; // 新增 const_iterator//创建头节点,让其指向自己const_iterator begin() const{return const_iterator(phead->next);}const_iterator end() const{return const_iterator(phead);}List(){phead = new Node();phead->next = phead;phead->prev = phead;}//拷贝构造函数,可以开辟新空间然后直接尾插//因为l2是const类型的,所以auto时需要const类型的迭代器//遍历 const 对象需要 const 迭代器List(const List<T>& l2){phead = new Node();phead->next = phead;phead->prev = phead;for (const auto& e : l2){push_back(e);}}//赋值运算符重载//直接更改头结点,后面的访问就全更改了List<T>& operator=(List<T> lt){swap(phead, lt.phead);return *this;}//析构函数~List(){clear();delete phead;phead = nullptr;}//全部遍历一遍s释放void clear(){auto it = begin();while (it != end()){it = erase(it);}}//头删void pop_back(){erase(--end());}//头插void push_front(const T& x){insert(begin(), x);}//头删void pop_front(){erase(begin());}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;}iterator begin(){//phead->next的类型是Node*类型,而返回类型需要是iterator类型,也就是对象//利用匿名对象,将phead->next传给ListIterator的构造函数,使它变为一个匿名对象,再return回去return iterator(phead->next);}iterator end(){return iterator(phead);}iterator insert(iterator pos, const T& x){Node* cur = pos.node;Node* newnode = new Node(x);Node* prev = cur->prev;// prev newnode curprev->next = newnode;newnode->prev = prev;newnode->next = cur;cur->prev = newnode;return iterator(newnode);}// erase 后 pos失效了,pos指向节点被释放了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 iterator(next);}private:Node* phead;}; }
💕7.测试用例
#define _CRT_SECURE_NO_WARNINGS #include <iostream> using namespace std; #include"list.h" int main() {yzq::List<int> l1;l1.push_back(2);l1.push_back(3);l1.insert(l1.begin(), 5);l1.erase(l1.begin());yzq::List<int> l2(l1);//遍历输出: 2 3for (auto e : l2) {std::cout << e << " ";}return 0; }
💕8.完结
相关文章:

【C++】STL——list底层实现
目录 💕1.list的三个类介绍 💕2.list——节点类 (ListNode) 💕3.list——链表类 (List) 💕4.list——迭代器类(重点思考)(ListIterator) 💕5…...

Java 进阶day14XML Dom4j 工厂模式 Base64
目录 知识点1、XML 概念XML约束 知识点2、XML解析 Dom4j(Dom for java)XPath 知识点3、工厂模式知识点4、Base64 知识点1、XML 概念 XML的全称为(eXtensible Markup Language),是一种可扩展的标记语言。 XML的作用&…...
100.6 AI量化面试题:如何评估AI量化模型的过拟合风险?
目录 0. 承前1. 解题思路1.1 性能验证维度1.2 统计检验维度1.3 实践验证维度 2. 样本内外性能对比2.1 基础性能指标计算2.2 策略收益对比 3. 参数敏感性分析3.1 参数网格搜索3.2 稳定性评估 4. 白噪声测试4.1 随机数据测试 5. Deflated Sharpe Ratio5.1 DSR计算 6. 交易成本敏感…...

C++模板:泛型编程的魔法钥匙
前言 本篇博客将详细介绍C的模板 💖 个人主页:熬夜写代码的小蔡 🖥 文章专栏:C 若有问题 评论区见 🎉欢迎大家点赞👍收藏⭐文章 一:引言:为什么需要模板? 1.复杂代码…...

unordered_map/set的哈希封装
【C笔记】unordered_map/set的哈希封装 🔥个人主页:大白的编程日记 🔥专栏:C笔记 文章目录 【C笔记】unordered_map/set的哈希封装前言一. 源码及框架分析二.迭代器三.operator[]四.使用哈希表封装unordered_map/set后言 前言 哈…...

机器学习专业毕设选题推荐合集 人工智能
目录 前言 毕设选题 开题指导建议 更多精选选题 选题帮助 最后 前言 大家好,这里是海浪学长毕设专题! 大四是整个大学期间最忙碌的时光,一边要忙着准备考研、考公、考教资或者实习为毕业后面临的升学就业做准备,一边要为毕业设计耗费大量精力。学长给大家整理…...

软件工程导论三级项目报告--《软件工程》课程网站
《软件工程》课程网站 摘要 本文详细介绍了《软件工程》课程网站的设计与实现方案,包括可行性分析、需求分析、总体设计、详细设计、测试用例。首先,通过可行性分析从各方面确认了该工程的可实现性,接着需求分析明确了系统的目标用户群和功能…...

物联网领域的MQTT协议,优势和应用场景
MQTT(Message Queuing Telemetry Transport)作为轻量级发布/订阅协议,凭借其低带宽消耗、低功耗与高扩展性,已成为物联网通信的事实标准。其核心优势包括:基于TCP/IP的异步通信机制、支持QoS(服务质量&…...
缓存类为啥使用 unordered_map 而不是 map
性能考虑: std::unordered_map 是基于哈希表实现的,而 std::map 是基于红黑树实现的。对于查找操作,std::unordered_map 的平均查找时间复杂度是 O ( 1 ) O(1) O(1),而 std::map 的查找时间复杂度是 O ( l o g n ) O(log n) O(l…...

产品经理的人工智能课 02 - 自然语言处理
产品经理的人工智能课 02 - 自然语言处理 1 自然语言处理是什么2 一个 NLP 算法的例子——n-gram 模型3 预处理与重要概念3.1 分词 Token3.2 词向量化表示与 Word2Vec 4 与大语言模型的交互过程参考链接 大语言模型(Large Language Models, LLMs)是自然语…...

2024年MySQL 下载、安装及启动停止教程(非常详细),涉及命令行net start mysql80提示发生系统错误5的解决方案
一、安装包下载 官方网址: https://www.mysql.com/ MySQL 官方提供了两种不同的版本: 1.社区版本( MySQL Community Server ) :免费, 但MySQL 不提供任何技术支持 2.商业版本( MySQL Enterp…...

19.[前端开发]Day19-王者荣项目耀实战(二)
01_(掌握)王者荣耀-main-banner展示实现 完整代码 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewpor…...

lmk内存压力测试工具mem-pressure源码剖析
背景: android系统开发过程中,经常会遇到一些low memory kill的问题,在分析这些系统低内存导致被杀问题时候,经常因为不好复现而成为一个比较烦恼的阻碍。因为这种低内存问题本身就不属于一种功能操作类型的问题,属于…...
企业四要素如何用Java进行调用
一、什么是企业四要素? 企业四要素是在企业三要素(企业名称、统一社会信用代码、法定代表人姓名)的基础上,增加了一个关键要素,通常是企业注册号或企业银行账户信息。这种接口主要用于更全面的企业信息验证,…...
修剪二叉搜索树(力扣669)
这道题还是比较复杂,在递归上与之前写过的二叉树的题目都有所不同。如果当前递归到的子树的父节点不在范围中,我们根据节点数值的大小选择进行左递归还是右递归。为什么找到了不满足要求的节点之后,还要进行递归呢?因为该不满足要…...

一款由 .NET 官方团队开源的电子商务系统 - eShop
项目介绍 eShop是一款由.NET官方开源的,基于.NET Aspire构建的用于参考学习的服务架构电子商务系统,旨在展示如何利用.NET框架及其相关技术栈构建一个现代化的电子商务网站。该项目采用服务架构,将应用程序分解为多个独立的服务,…...
论最新技术编程类有什么,值得关注的点有什么呢?
在2025年的编程领域,新技术层出不穷。编程语言方面,Zig作为新一代系统级编程语言,凭借无隐藏控制流、出色的优化性能以及良好的C语言兼容性,被视作C语言强有力的替代者;Rust的应用范围不断拓展,在系统开发和Web后端开发中表现亮眼,其“零成本抽象”特性在保障内存安全的…...

Java入门进阶
文章目录 1、常用API 1.1、Math1.2、System1.3、Object1.4、Arrays1.5、基本类型包装类 1.5.1、基本类型包装类概述1.5.2、Integer1.5.3、int和String相互转换1.5.4、自动装箱和拆箱 1.6、日期类 1.6.1、Date类1.6.2、SimpleDateFormat类 1.6.2.1、格式化(从Date到…...

Java并发编程面试题:ThreadLocal(8题)
🧑 博主简介:CSDN博客专家,历代文学网(PC端可以访问:https://literature.sinhy.com/#/?__c1000,移动端可微信小程序搜索“历代文学”)总架构师,15年工作经验,精通Java编…...

Zabbix7.0安装(Ubuntu24.04+LNMP)
1.选择版本 下载Zabbix 2.安装虚拟机 这里选择在Ubuntu24.04上安装Zabbix. 安装链接https://blog.csdn.net/weixin_58189050/article/details/145446065 配置源 vim /etc/apt/sources.list deb https://mirrors.aliyun.com/ubuntu/ noble main restricted universe multive…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...

Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...

算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...

基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...

基于Springboot+Vue的办公管理系统
角色: 管理员、员工 技术: 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能: 该办公管理系统是一个综合性的企业内部管理平台,旨在提升企业运营效率和员工管理水…...