【C++初阶】list的模拟实现 附源码

一.list介绍

list底层是一个双向带头循环链表,这个我们以前用C语言模拟实现过,->双向带头循环链表

下面是list的文档介绍: list文档介绍

我们会根据 list 的文档来模拟实现 list 的增删查改及其它接口。


 

二.list模拟实现思路

既然是用C++模拟实现的,那么一定要封装在类里

为了适合各种类型的数据,会使用模板

节点 Node

了解双向循环带头链表的都知道,我们需要一个节点 (Node),之前用C语言实现的时候,我们写了一个叫做 BuynewNode 的函数来获取节点,而在C++里我们用类封装一个,注意这个用 struct 封装比较好,因为 struct 默认是公有的,这样方便我们访问,所以可以写一个类:

    struct  list_node

迭代器  iterator

我们知道,C++提供了一种统一的方式来访问容器,这就是迭代器,string 和 vector 的迭代器模拟实现很简单,因为 string 和 vector 底层是用数组实现的,数组是一段连续的物理空间,支持随机访问,所以它是天然的迭代器

但是链表不一样,它不是一段连续的物理空间,不支持随机访问,所以想让 list 的迭代器在表面上和 string,vector 的迭代器用起来没有区别,我们在底层上就需要用类封装迭代器,然后再迭代器类的内部,重载  ++  --  *  ->  !=  ==  这些迭代器会用到的运算符

所以创建一个迭代器类:

   struct  list_iterator

const 迭代器  const_iterator

实现的普通的迭代器,还有 const 迭代器,const 迭代器的意思是让指针指向的内容不变,而指针本身可以改变,例如指针++,指针-- 这种操作,所以 const 迭代器与普通迭代器的不同只有 重载 * 运算符的返回值不同,它是 const  T&  (T是模板参数),重写一个const 迭代器类又显得太冗余,代码的可读性就降低了;

前面在学习模板时,我们知道不同的模板参数,编译器会生成不同的函数,所以我们选择加一个模板参数 :Ref 。这样只要在显示实例化模板参数时:

              普通迭代器就传 T&

              const 迭代器就传 const T&

-> 运算符重载

看下面这段代码:

using namespace std;

struct A
{
	A(int a1,int a2)
		:_a1(a1)
		,_a2(a2)
	{}

	int _a1;
	int _a2;
};

void test_list()
{
	list<A> lt;   //实例化自定义类型
	lt.push_back(A(1, 1));
	lt.push_back(A(2, 2));
	lt.push_back(A(3, 3));
	lt.push_back(A(4, 4));

	list<A>::iterator it = lt.begin();

	while (it != lt.end())
	{
		cout << it->_a1 << " " << it->_a2 << endl;  //像指针一样访问自定义类型里的成员变量
		it++;
	}	
}

int main()
{
	test_list();

	return 0;
}

有时候,实例化的模板参数是自定义类型,我们想要像指针一样访问访问自定义类型力的成员变量,这样显得更通俗易懂,所以就要重载 -> 运算符,它的返回值是 T* ,但是正常来说这里应该是这样访问的: it -> -> _a1

因为迭代器指向的是 整个自定义类型,要想再访问其内部成员应该再使用一次 -> (这个->就不是重载的 -> ,就是普通的 -> ),但是上面的代码为什么就写了一个 -> ,这个是C++语法把这里特殊化了。

那该怎么在迭代器类里重载 -> 运算符呢?

和const 迭代器一样,只需要再加一个模板参数 :Ptr

显示实例化的时候传 T* 就行了。 

迭代器类 模拟实现源码: struct list_iterator

以上的都算 list 模拟实现的难点,其他的像 重载 ++ 什么的,对于学过数据结构的小伙伴们是非常简单的,就不赘述了,没学过的可以看看这篇文章:双向带头循环链表

template<class T,class Ref,class Ptr>   //三个模板参数
	struct list_iterator   //封装迭代器
	{
		typedef list_node<T> Node;  //重命名节点
		typedef list_iterator<T, Ref, Ptr> self;  //重命名迭代器类型
		Node* _node;

		list_iterator(Node*node)   //构造函数,单参数的构造函数支持隐式类型转换
			:_node(node)
		{}

		//重载 * ++ -- != == ->
		Ref operator*() const
		{
			return _node->_val;
		}

		Ptr operator->() const
		{
			return &_node->_val;
		}

		self& operator++()   //前置++
		{
			_node = _node->_next;

			return *this;
		}

		self operator++(int)  //后置++
		{
			self tmp = *this;
			_node = _node->_next;

			return tmp;
		}

		self& operator--()   //前置--
		{
			_node = _node->_prev;

			return *this;
		}

		self operator--(int)  //后置--
		{
			self tmp = *this;
			_node = _node->_prev;

			return tmp;
		}

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

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

	};

list

我们在用C语言实现双向带头循环链表时,会先初始化链表的头(head),即让它的 前驱指针(prev)和后继指针(next)都指向自己

在C++的模拟实现 list 中,我们会创建一个类 list  来管理链表的节点并实现增删查改及其它接口,所以 list  的构建函数就是初始化 头(head)节点


三.源码

list.h

 

我们可以模拟实现以上接口,具体函数的逻辑可以查阅文档,实现起来都是很简单的。

namespace nagi   //把模拟实现list的类都放在一个命名空间里封装起来
{
	template<class T>
	struct list_node   //创建节点
	{
		list_node<T>* _prev;
		list_node<T>* _next;
		T _val;

		list_node(const T& val = T())  //构造函数,初始化节点
			:_prev(nullptr)
			,_next(nullptr)
			,_val(val)
		{}

	};

	template<class T,class Ref,class Ptr>   //三个模板参数
	struct list_iterator   //封装迭代器
	{
		typedef list_node<T> Node;
		typedef list_iterator<T, Ref, Ptr> self;
		Node* _node;

		list_iterator(Node*node)   //构造函数,单参数的构造函数支持隐式类型转换
			:_node(node)
		{}

		//重载 * ++ -- != == ->
		Ref operator*() const
		{
			return _node->_val;
		}

		Ptr operator->() const
		{
			return &_node->_val;
		}

		self& operator++()   //前置++
		{
			_node = _node->_next;

			return *this;
		}

		self operator++(int)  //后置++
		{
			self tmp = *this;
			_node = _node->_next;

			return tmp;
		}

		self& operator--()   //前置--
		{
			_node = _node->_prev;

			return *this;
		}

		self operator--(int)  //后置--
		{
			self tmp = *this;
			_node = _node->_prev;

			return tmp;
		}

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

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

	};

	template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		typedef list_iterator<T, T&, T*> iterator;  //重命名普通迭代器
		typedef list_iterator<T, const T&, const T*> const_iterator;  //重命名const迭代器

		void empty_init()  //因为构造函数和拷贝构造都会初始化头节点,所以就写成一个函数了
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
			_sz = 0;
		}

		list()  //构造函数
		{
			empty_init();
		}
		//普通迭代器
		iterator begin()
		{
			return _head->_next;
		}

		iterator end()
		{
			return _head;
		}
		//const迭代器
		const_iterator begin() const
		{
			return _head->_next;
		}

		const_iterator end() const
		{
			return _head;
		}

		iterator insert(iterator pos, const T& x)  //在pos之前插入
		{
			Node* newnode = new Node(x);
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			_sz++;

			return newnode;
		}

		iterator erase(iterator pos)   //删除pos位置,注意删除的时候不能把头节点也删了,所以要做pos检查
		{
			assert(pos != end());

			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			prev->_next = next;
			next->_prev = prev;

			delete cur;
			_sz--;

			return next;   //库里规定返回删除节点的下一个节点
		}

		void push_back(const T& x)  //尾插
		{
			insert(end(), x);
		}

		void push_front(const T& x)  //头插
		{
			insert(begin(), x);
		}

		void pop_back()  //尾删
		{
			erase(--end());
		}

		void pop_front()  //头删
		{
			erase(begin());
		}

		void clear()  //清楚除了头节点以外的所有节点
		{
			iterator it = begin();
			while (it != end())
			{
				it=erase(it);
				
			}
			_sz = 0;
		}

		~list()  //析构函数
		{
			clear();

			delete _head;
			_head = nullptr;
		}

		list(const list<T>& lt)   //拷贝构造
		{
			empty_init();

			for (auto& e : lt)
			{
				push_back(e);
			}
			
		}

		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_sz, lt._sz);
		}

		list<T>& operator=(list<T> lt)  //赋值重载
		{
			swap(lt);

			return *this;
		}

	private:
		Node* _head;  //头节点
		size_t _sz;   //记录链表的长度
	};

}

🐬🤖本篇文章到此就结束了, 若有错误或是建议的话,欢迎小伙伴们指出;🕊️👻

😄😆希望小伙伴们能支持支持博主啊,你们的支持对我很重要哦;🥰🤩

😍😁谢谢你的阅读。😸😼

 

 

 

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

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

相关文章

HDFS Hadoop分布式文件存储系统整体概述

HDFS 整体概述举例&#xff1a; 包括机架 rack1、rack2 包括5个Datanode,一个Namenode(主角色)带领5个Datanode(从角色)&#xff0c;每一个rack中包含不同的block模块文件为分块存储模式。块与块之间通过replication进行副本备份&#xff0c;进行冗余存储&#xff0c;Namenode…

基于Nonconvex规划的配电网重构研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

数仓学习---8、数仓开发之ODS层

星光下的赶路人star的个人主页 大鹏一日同风起&#xff0c;扶摇直上九万里 文章目录 一、数仓开发之ODS层1.1 日志表1.2 业务表1.2.1 活动信息表&#xff08;全量表&#xff09;1.2.2 活动规则表&#xff08;全量表&#xff09;1.2.3 一级品类表&#xff08;全量表&#xff09;…

Docker基础(二)

1、Docker工作原理 Docker是一个Clinet-Server结构的系统&#xff0c;Docker守护进程运行在主机上&#xff0c;然后通过Socket连接从客户端访问&#xff0c;守护进程从客户端接受命令并管理运行在主机上的容器。 容器&#xff0c;是一个运行时环境&#xff0c;就是我们前面说的…

Linux6.1 Docker 基本管理

文章目录 计算机系统5G云计算第四章 LINUX Docker 基本管理一、Docker 概述1.概述2.Docker与虚拟机的区别3.容器在内核中支持2种重要技术4.Docker核心概念1&#xff09;镜像2&#xff09;容器3&#xff09;仓库 二、安装 Docker三、Docker 镜像操作四、Docker 容器操作 计算机系…

【软件测试面试】腾讯数据平台笔试题-接口-自动化-数据库

数据库题 答案&#xff1a; Python编程题 答案&#xff1a; 接口参数化题 答案&#xff1a; 接口自动化题 答案&#xff1a; 以下是我收集到的比较好的学习教程资源&#xff0c;虽然不是什么很值钱的东西&#xff0c;如果你刚好需要&#xff0c;可以评论区&#…

家政小程序开发-H5+小程序

移动互联网的发展&#xff0c;微信小程序逐渐成为商家拓展线上业务的重要手段。家政服务作为日常生活中不可或缺的一部分&#xff0c;也开始尝试通过小程序来提高服务质量和效率。 下面是一篇关于家政小程序开发的H5小程序的文章&#xff0c;希望对您有所帮助。 家政服…

Spring Cloud 远程接口调用OpenFeign负载均衡实现原理详解

环境&#xff1a;Spring Cloud 2021.0.7 Spring Boot 2.7.12 配置依赖 maven依赖 <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-openfeign</artifactId> </dependency> <dependency&…

未来Mac下载站怎么打不开了

重要公告&#xff1a; 未来软件园因业务需要现更换域名 原域名&#xff1a;Mac.orsoon.com 更为新域名&#xff1a;未来mac下载-Mac软件-mac软件下载-mac软件大全 程序已全面转移&#xff0c;请访问新域名

tauri自定义窗口window并实现拖拽和阴影效果

需求说明 由于官方提供的窗口标题并不能实现我的需求&#xff0c;不能很好的实现主题切换的功能&#xff0c;所以根据官方文档实现了一个自定义的窗口&#xff0c;官方文档地址&#xff1a;Window Customization | Tauri Apps 但是实现之后&#xff0c; 没有了窗体拖拽移动的…

第四章Shell编程之正则表达式与文本处理器

文本处理有三剑客&#xff1a;grep sed awk 通配符&#xff1a;只能匹配文件名与目录名&#xff0c;不能匹配文件的内容 *匹配任意一个或者多个字符 &#xff1f;匹配任意一个字符&#xff08;就是匹配单个字符&#xff09; [ ] 匹配范围内的任意单个字符 正则表达式&…

ONNX 推理,精度下降

先看代码&#xff1a; img cv2.imread("65.jpg") img1 img.copy() img2 img.copy() img1 - 112 img1 img1.astype(np.float32) img2 np.float32(img2) img2 - 112 现象&#xff1a;在使用 img1 这种处理方式时&#xff0c;推理结果异常&#xff0c;起码掉点…

AUTOSAR CP标准的RTE和BSW各模块的设计及开发工作

AUTOSAR&#xff08;Automotive Open System Architecture&#xff09;是一种开放的汽车电子系统架构标准&#xff0c;旨在提供一种统一的软件架构&#xff0c;以实现汽车电子系统的模块化和可重用性。 AUTOSAR标准中的两个重要模块是RTE&#xff08;Runtime Environment&…

智能优化算法——灰狼优化算法(PythonMatlab实现)

目录 1 灰狼优化算法基本思想 2 灰狼捕食猎物过程 2.1 社会等级分层 2.2 包围猎物 2.3 狩猎 2.4 攻击猎物 2.5 寻找猎物 3 实现步骤及程序框图 3.1 步骤 3.2 程序框图 4 Python代码实现 5 Matlab实现 1 灰狼优化算法基本思想 灰狼优化算法是一种群智能优化算法&#xff0c;它的…

【已解决】ModuleNotFoundError: No module named ‘timm.models.layers.helpers‘

文章目录 错误信息原因解决方法专栏&#xff1a;神经网络精讲与实战AlexNetVGGNetGoogLeNetInception V2——V4ResNetDenseNet 错误信息 在使用timm库的时候出现了ModuleNotFoundError: No module named timm.models.layers.helpers’的错误&#xff0c;详情如下&#xff1a; …

大语言模型举例和相关论文推荐

大语言模型如火如荼。甚至已经爆发了“百模大战” 2023年&#xff0c;“百模大战”&#xff0c;一触即发。 因为工作需要&#xff0c;我除了参加行业、企业、研究机构的发布会和闭门会&#xff0c;还需要基于自身的业务&#xff0c;不断了解最新的AI大模型和AIGC应用。 2024…

JavaScript——基础知识及使用

初识 JavaScript JavaScript (简称 JS) 是世界上最流行的编程语言之一.一个脚本语言, 通过解释器运行.主要在客户端(浏览器)上运行, 现在也可以基于 node.js 在服务器端运行. JavaScript 的能做的事情: 网页开发(更复杂的特效和用户交互)网页游戏开发服务器开发(node.js)桌…

Ceph的安装部署

文章目录 一、存储基础1.1 单机存储设备1.2 单机存储的问题1.3分布式存储&#xff08;软件定义的存储 SDS&#xff09; 二、Ceph 简介2.1 Ceph 优势2.2 Ceph 架构2.3 Ceph 核心组件2.4 Pool、PG 和 OSD 的关系&#xff1a;2.5 OSD 存储后端2.6 Ceph 数据的存储过程2.7 Ceph 版本…

手写Spring框架---MVC实现

目录 预备 自研框架MVC的实现 MVC架构草图&#xff1a; 大致流程 实现思路 自定义注解 JavaBean 请求的拦截-建立DispatcherServlet 责任链处理请求 RequestProcessor矩阵 Render矩阵 预备 在DispatcherServlet&#xff1a; 解析请求路径和请求方法依赖容器&#xf…

前端学习记录~2023.7.17~CSS杂记 Day9

前言一、浮动1、使盒子浮动起来2、清除浮动3、清除浮动元素周围的盒子&#xff08;1&#xff09;clearfix 小技巧&#xff08;2&#xff09;使用 overflow&#xff08;3&#xff09;display: flow-root 二、定位1、定位有哪些2、top、bottom、left 和 right3、定位上下文4、介绍…