【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;
		}
		//后置--
		//后置--需要利用一个临时变量来表示原来的值，首先传参传给来的是对象的地址，即this
		Self 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;//将节点类重命名为Node
	typedef ListIterator<T> iterator;//将迭代器类重命名为iterator
	typedef 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;
		}
		//后置--
		//后置--需要利用一个临时变量来表示原来的值，首先传参传给来的是对象的地址，即this
		Self 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;//将节点类重命名为Node
		typedef ListIterator<T> iterator;//将迭代器类重命名为iterator
		typedef 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  cur
			prev->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 3
   for (auto e : l2) {
        std::cout << e << " ";
    }
    return 0;
}

💕8.完结 

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

SpringUI Web高端动态交互元件库

SpringUI Web高端动态交互元件库

Axure Web高端动态交互元件库是一个专为Web设计与开发领域设计的高质量资源集合&#xff0c;旨在加速原型设计和开发流程。以下是关于这个元件库的详细介绍&#xff1a; 一、概述 Axure Web高端动态交互元件库是一个集成了多种预制、高质量交互组件的工具集合。这些组件经过精…
阅读更多...
02、NodeJS学习笔记，第二节：express与中间件

02、NodeJS学习笔记，第二节：express与中间件

express与中间件 中文官网&#xff1a;https://www.expressjs.com.cn/nodemon工具 nodemon这个工具&#xff0c;能够监听项目文件的变动。 当代码被修改后&#xff0c;nodemon会帮我们自动重启项目&#xff0c;极大的方便了开发和调试##安装 npm i -g nodemon##使用 之前启动…
阅读更多...
通向AGI之路：人工通用智能的技术演进与人类未来

通向AGI之路：人工通用智能的技术演进与人类未来

文章目录 引言：当机器开始思考一、AGI的本质定义与技术演进1.1 从专用到通用：智能形态的范式转移1.2 AGI发展路线图二、突破AGI的五大技术路径2.1 神经符号整合（Neuro-Symbolic AI）2.2 世界模型架构（World Models）2.3 具身认知理论（Embodied Cognition）三、AGI安全：价…
阅读更多...
结合深度学习、自然语言处理（NLP）与多准则决策的三阶段技术框架，旨在实现从消费者情感分析到个性化决策

结合深度学习、自然语言处理（NLP）与多准则决策的三阶段技术框架，旨在实现从消费者情感分析到个性化决策

针对电商个性化推荐场景的集成机器学习和稳健优化三阶段方案。 第一阶段:在线评论数据处理&#xff0c;利用深度学习和自然语言处理技术进行特征挖掘&#xff0c;进而进行消费者情感分析&#xff0c;得到消费者偏好 在第一阶段&#xff0c;我们主要关注如何通过深度学习和自然语…
阅读更多...
哪些专业跟FPGA有关？

哪些专业跟FPGA有关？

FPGA产业作为近几年新兴的技术领域&#xff0c;薪资高、待遇好&#xff0c;吸引了大量的求职者。特别是对于毕业生&#xff0c;FPGA领域的岗位需求供不应求。那么&#xff0c;哪些专业和FPGA相关呢&#xff1f; 哪些专业跟FPGA有关&#xff1f; 微电子学与固体电子学、微电子科…
阅读更多...
STM32 LED呼吸灯

STM32 LED呼吸灯

接线图&#xff1a; 这里将正极接到PA0引脚上&#xff0c;负极接到GND&#xff0c;这样就高电平点亮LED&#xff0c;低电平熄灭。 占空比越大&#xff0c;LED越亮&#xff0c;占空比越小&#xff0c;LED越暗 PWM初始化配置 输出比较函数介绍&#xff1a; 用这四个函数配置输…
阅读更多...
记录一次-Rancher通过UI-Create Custom- RKE2的BUG

记录一次-Rancher通过UI-Create Custom- RKE2的BUG

一、下游集群 当你的下游集群使用Mysql外部数据库时&#xff0c;会报错&#xff1a; **他会检查ETCD。 但因为用的是Mysql外部数据库&#xff0c;这个就太奇怪了&#xff0c;而且这个检测不过&#xff0c;集群是咩办法被管理的。 二、如果不选择etcd,就选择控制面。 在rke2-…
阅读更多...
数据库物理备份：保障数据完整性和业务连续性的关键策略

数据库物理备份：保障数据完整性和业务连续性的关键策略

title: 数据库物理备份：保障数据完整性和业务连续性的关键策略 date: 2025/1/29 updated: 2025/1/29 author: cmdragon excerpt: 在现代企业中，数据被视为最重要的资产之一。因此，确保数据的安全性、完整性和可用性是每个数据库管理员（DBA）的首要任务。在数据管理的过程…
阅读更多...
【3分钟极速部署】在本地快速部署deepseek

【3分钟极速部署】在本地快速部署deepseek

第一步&#xff0c;找到网站&#xff0c;下载&#xff1a; 首先找到Ollama &#xff0c; 根据自己的电脑下载对应的版本 。 我个人用的是Windows 我就先尝试用Windows版本了 &#xff0c;文件不是很大&#xff0c;下载也比较的快 第二部就是安装了 &#xff1a; 安装完成后提示…
阅读更多...
Deepseek v3R1 学习笔记

Deepseek v3R1 学习笔记

o1 o1 模型在训练过程中混合了多种奖励函数的设计方法&#xff0c;并且尝试从结果监督转向过程监督&#xff0c;在中间过程进行打分 使用的搜索策略&#xff1a;基于树的搜索和基于顺序修改的搜索 R1 R1-Zero 是从基础模型开始&#xff0c;完全由强化学习驱动&#xff0c;不…
阅读更多...
4.PPT：日月潭景点介绍【18】

4.PPT：日月潭景点介绍【18】

目录 NO1、2、3、4​ NO5、6、7、8 ​ ​NO9、10、11、12 ​ 表居中或者水平/垂直居中单元格内容居中或者水平/垂直居中 NO1、2、3、4 新建一个空白演示文稿&#xff0c;命名为“PPT.pptx”&#xff08;“.pptx”为扩展名&#xff09;新建幻灯片 开始→版式“PPT_素材.doc…
阅读更多...
国防科大：双目标优化防止LLM灾难性遗忘

国防科大：双目标优化防止LLM灾难性遗忘

&#x1f4d6;标题&#xff1a;How to Complete Domain Tuning while Keeping General Ability in LLM: Adaptive Layer-wise and Element-wise Regularization &#x1f310;来源&#xff1a;arXiv, 2501.13669 &#x1f31f;摘要 &#x1f538;大型语言模型&#xff08;LLM…
阅读更多...
【C++】多态详细讲解

【C++】多态详细讲解

本篇来聊聊C面向对象的第三大特性-多态。 1.多态的概念 多态通俗来说就是多种形态。多态分为编译时多态(静态多态)和运⾏时多态(动态多态)。 编译时多态&#xff1a;主要就是我们前⾯讲的函数重载和函数模板&#xff0c;他们传不同类型的参数就可以调⽤不同的函数&#xff0c;通…
阅读更多...
java进阶1——JVM

java进阶1——JVM

java进阶——JVM 1、JVM概述 作用 Java 虚拟机就是二进制字节码的运行环境&#xff0c;负责装载字节码到其内部&#xff0c;解释/编译为对 应平台上的机器码指令行&#xff0c;每一条 java 指令&#xff0c;java 虚拟机中都有详细定义&#xff0c;如怎么取操 作数&#xff0c…
阅读更多...
DeepSeek各版本说明与优缺点分析

DeepSeek各版本说明与优缺点分析

DeepSeek各版本说明与优缺点分析 DeepSeek是最近人工智能领域备受瞩目的一个语言模型系列&#xff0c;其在不同版本的发布过程中&#xff0c;逐步加强了对多种任务的处理能力。本文将详细介绍DeepSeek的各版本&#xff0c;从版本的发布时间、特点、优势以及不足之处&#xff0…
阅读更多...
视频融合平台EasyCVR无人机场景视频压缩及录像方案

视频融合平台EasyCVR无人机场景视频压缩及录像方案

安防监控视频汇聚EasyCVR平台在无人机场景中发挥着重要的作用&#xff0c;通过高效整合视频流接入、处理与分发等功能&#xff0c;为无人机视频数据的实时监控、存储与分析提供了全面支持&#xff0c;广泛应用于安防监控、应急救援、电力巡检、交通管理等领域。 EasyCVR支持GB…
阅读更多...
【力扣】240.搜索二维矩阵 II

【力扣】240.搜索二维矩阵 II

题目 我的代码 class Solution { public:bool searchMatrix(vector<vector<int>>& matrix, int target) {for(int i0;i<matrix.size();i){for(int j0;j<matrix[0].size();j){if(targetmatrix[i][j]){return true;}else if(target<matrix[i][j]){brea…
阅读更多...
数据库备份、主从、集群等配置

数据库备份、主从、集群等配置

数据库备份、主从、集群等配置 1 MySQL1.1 docker安装MySQL1.2 主从复制1.2.1 主节点配置1.2.2 从节点配置1.2.3 创建用于主从同步的用户1.2.4 开启主从同步1.2.4 主从同步验证 1.3 主从切换1.3.1 主节点设置只读&#xff08;在192.168.1.151上操作&#xff09;1.3.2 检查主从数…
阅读更多...
intra-mart实现简易登录页面笔记

intra-mart实现简易登录页面笔记

一、前言 最近在学习intra-mart框架&#xff0c;在此总结下笔记。 intra-mart是一个前后端不分离的框架&#xff0c;开发时主要用的就是xml、html、js这几个文件&#xff1b; xml文件当做配置文件&#xff0c;html当做前端页面文件&#xff0c;js当做后端文件&#xff08;js里…
阅读更多...
Beans模块之工厂模块注解模块CustomAutowireConfigurer

Beans模块之工厂模块注解模块CustomAutowireConfigurer

博主介绍&#xff1a;✌全网粉丝5W&#xff0c;全栈开发工程师&#xff0c;从事多年软件开发&#xff0c;在大厂呆过。持有软件中级、六级等证书。可提供微服务项目搭建与毕业项目实战&#xff0c;博主也曾写过优秀论文&#xff0c;查重率极低&#xff0c;在这方面有丰富的经验…
阅读更多...
最新文章

Copyright @ 2022~2023