【STL】:list的模拟实现

朋友们、伙计们,我们又见面了,本期来给大家解读一下有关list的模拟实现,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成!

C 语 言 专 栏:C语言:从入门到精通

数据结构专栏:数据结构

个  人  主  页 :stackY、

C + + 专 栏   :C++

Linux 专 栏  :Linux

目录

1. 基本构造

2. 正向迭代器

2.1 非const迭代器

2.2 const迭代器

2.3 正向迭代器的改进优化

3. 修改相关接口

3.1 insert、erase

3.2 尾插、头插、尾删、头删、清理

4. 拷贝构造、赋值重载、析构

5. 完整代码


1. 基本构造

list的底层其实是一个带头双向循环的链表,所以在模拟实现之前可以看一下库里面怎么实现的:

namespace ywh
{
	//链表结构
	template<class T>
	struct list_node
	{
		T _data;                 //节点中的数据
		list_node<T>* _prev;    //指向前一个节点的指针
		list_node<T>* _next;    //指向后一个节点的指针

        //构造
		list_node(const T& x = T())
			:_data(x)
			, _prev(nullptr)
			, _next(nullptr)
		{}

	};

	//list结构
	template<class T>
	class list
	{
	public:
		typedef list_node<T> Node;
	public:
		
		//空初始化
		void empty_init()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _next;
		}
		//构造
		list()
		{
			empty_init();
		}

	private:
		Node* _head;  //链表的头节点
		size_t _size; //节点个数
	};
}

2. 正向迭代器

在使用list的阶段的迭代器使用方法和之前的string、vector一样,但是了解过链表的结构都知道,链表要访问下一个节点就是使用节点中的next指针指向下一个节点,需要访问里面的数据需要找到里面的data,++和解引用并不能访问链表的节点,那么迭代器的使用在底层肯定是封装加运算符重载。

在实现迭代器的时候也需要采用封装和运算符重载,运算符重载需要用到++、--、!=、==、*、->等运算符。迭代器分为const迭代器和非const迭代器,首先先来看看非const迭代器:

2.1 非const迭代器

迭代器的实现一般使用struct来进行封装:

namespace ljm
{
	//链表结构
	template<class T>
	struct list_node
	{
		T _data;                 //节点中的数据
		list_node<T>* _prev;    //指向前一个节点的指针
		list_node<T>* _next;    //指向后一个节点的指针

		//构造
		list_node(const T& x = T())
			:_data(x)
			, _prev(nullptr)
			, _next(nullptr)
		{}

	};

	//非const正向迭代器
	template<class T>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T> self;
		Node* _node;
		//迭代器构造
		__list_iterator(Node* node)
			:_node(node)
		{}
		
		//前置
		//operator++
		self& operator++()
		{
			return _node->_next;
		}
		//operator--
		self& operator--()
		{
			return _node->_prev;
		}

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

		//operator*
		T& operator*()
		{
			return _node->_data;
		}
		//operator->
		T* operator->()
		{
			return &_node->_data;
		}
		//operator!=
		bool operator!=(const self& s)
		{
			return _node != s._node;
		}
		//operator==
		bool operator==(const self& s)
		{
			return _node == s._node;
		}
	};

	//list结构
	template<class T>
	class list
	{
	public:
		typedef list_node<T> Node;
	public:
		
		//空初始化
		void empty_init()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}
		//构造
		list()
		{
			empty_init();
		}
        ///正向迭代器
		iterator begin()
		{
			return iterator(_head->_next); //使用匿名对象进行构造
		}
		iterator end()
		{
			return iterator(_head);
		}

	private:
		Node* _head;  //链表的头节点
		size_t _size; //节点个数
	};
}

2.2 const迭代器

迭代器中涉及到修改的就是*和->,const迭代器的作用是指向的内容不能修改,本身不能修改,所以需要重新进行封装:

namespace ljm
{
	//链表结构
	template<class T>
	struct list_node
	{
		T _data;                 //节点中的数据
		list_node<T>* _prev;    //指向前一个节点的指针
		list_node<T>* _next;    //指向后一个节点的指针

		//构造
		list_node(const T& x = T())
			:_data(x)
			, _prev(nullptr)
			, _next(nullptr)
		{}

	};

	//非const正向迭代器
	//...

	//const正向迭代器
	template<class T>
	struct __list_const_iterator
	{
		typedef list_node<T> Node;
		typedef __list_const_iterator<T> self;
		Node* _node;
		//迭代器构造
		__list_const_iterator(Node* node)
			:_node(node)
		{}

		//前置
		//operator++
		self& operator++()
		{
			_node = _node->_next;
            return *this;
		}
		//operator--
		self& operator--()
		{
			_node = _node->_prev;
            return *this;
		}

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

		//operator*
		const T& operator*()
		{
			return _node->_data;
		}
		//operator->
		const T* operator->()
		{
			return &_node->_data;
		}
		//operator!=
		bool operator!=(const self& s)
		{
			return _node != s._node;
		}
		//operator==
		bool operator==(const self& s)
		{
			return _node == s._node;
		}
	};

	//list结构
	template<class T>
	class list
	{
	public:
		typedef list_node<T> Node;
		typedef __list_iterator<T> iterator;
		typedef __list_const_iterator<T> const_iterator;
	public:
		基本构造///
		//空初始化
		void empty_init()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}
		//构造
		list()
		{
			empty_init();
		}
		///正向迭代器
		iterator begin()
		{
			return iterator(_head->_next); //使用匿名对象进行构造
		}
		iterator end()
		{
			return iterator(_head);
		}
		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}
		const_iterator end() const
		{
			return const_iterator(_head);
		}

	private:
		Node* _head;  //链表的头节点
		size_t _size; //节点个数
	};
}

2.3 正向迭代器的改进优化

上面的这两种写法不难看出有很多代码都是重复出现的,使得代码非常冗余,那么怎么将这些冗余的代码进行合并呢?

我们可以看一下库里面如何实现:

采用泛型编程,使用模板,将这一转化的工作交给编译器,而我们只需传递const参数和非const参数即可:

namespace ywh
{
	//链表结构
	template<class T>
	struct list_node
	{
		T _data;                 //节点中的数据
		list_node<T>* _prev;    //指向前一个节点的指针
		list_node<T>* _next;    //指向后一个节点的指针

		//构造
		list_node(const T& x = T())
			:_data(x)
			, _prev(nullptr)
			, _next(nullptr)
		{}

	};

	//非const正向迭代器
	//   类型模板参数   传递引用      传递指针
	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)
		{}
		
		//前置
		//operator++
		self& operator++()
		{
			_node = _node->_next;
            return *this;
		}
		//operator--
		self& operator--()
		{
			_node = _node->_prev;
            return *this;
		}

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

		//operator*
		Ref operator*()
		{
			return _node->_data;
		}
		//operator->
		Ptr operator->()
		{
			return &_node->_data;
		}
		//operator!=
		bool operator!=(const self& s)
		{
			return _node != s._node;
		}
		//operator==
		bool operator==(const self& s)
		{
			return _node == s._node;
		}
	};

	//list结构
	template<class T>
	class list
	{
	public:
		typedef list_node<T> Node;
		typedef __list_iterator<T, T&, T*> iterator;   //非const迭代器
		typedef __list_iterator<T, const T&, const T*> const_iterator;  //const迭代器
	public:
		基本构造///
		//空初始化
		void empty_init()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}
		//构造
		list()
		{
			empty_init();
		}
		///正向迭代器
		iterator begin()
		{
			return iterator(_head->_next); //使用匿名对象进行构造
		}
		iterator end()
		{
			return iterator(_head);
		}
		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}
		const_iterator end() const
		{
			return const_iterator(_head);
		}

	private:
		Node* _head;  //链表的头节点
		size_t _size; //节点个数
	};
}

3. 修改相关接口

3.1 insert、erase

在pos位置进行插入删除比较简单,需要进行链接新节点,改变节点中指针的指向即可,库里面对于插入和删除都带有返回值,那么我们在实现的时候也加上返回值:

///修改相关接口
		//在pos位置插入节点
		iterator insert(iterator pos, const T& x)
		{
			//创建新新节点
			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;
			//更新节点个数
			++_size;
			//返回新节点的位置
			return iterator(newnode);
		}
		//删掉pos位置的节点
		iterator erase(iterator pos)
		{
			//保存相对位置
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			//链接节点
			delete cur;
			prev->_next = next;
			next->_prev = prev;
			//更新节点个数
			--_size;
			//返回pos的下一个位置
			return iterator(next);
		}

在进行insert之后可以看到迭代器是不会失效的,但是在erase之后pos位置会被释放,因此erase之后迭代器会失效,在使用前先更新迭代器。

3.2 尾插、头插、尾删、头删、清理

当实现了insert和erase之后,实现这些接口直接复用即可:

        //尾插
		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);
			}
		}

4. 拷贝构造、赋值重载、析构

在这里我们都是采用现代写法:

 拷贝构造直接使用迭代器依次遍历进行尾插。

//拷贝构造
		list(const list<T>& lt)
		{
			//先创建空节点
			empty_init();
			//依次尾插即可
			for (auto e : lt)
			{
				push_back(e);
			}
		}
		//operator=
		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}
		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}
		//析构
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
			_size = 0;
		}

5. 完整代码

 头文件:List.h

#pragma once

namespace ywh
{
	//链表结构
	template<class T>
	struct list_node
	{
		T _data;                 //节点中的数据
		list_node<T>* _prev;    //指向前一个节点的指针
		list_node<T>* _next;    //指向后一个节点的指针

		//构造
		list_node(const T& x = T())
			:_data(x)
			, _prev(nullptr)
			, _next(nullptr)
		{}

	};

	//非const正向迭代器
	//   类型模板参数   传递引用      传递指针
	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)
		{}
		
		//前置
		//operator++
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//operator--
		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

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

		//operator*
		Ref operator*()
		{
			return _node->_data;
		}
		//operator->
		Ptr operator->()
		{
			return &_node->_data;
		}
		//operator!=
		bool operator!=(const self& s)
		{
			return _node != s._node;
		}
		//operator==
		bool operator==(const self& s)
		{
			return _node == s._node;
		}
	};

	//list结构
	template<class T>
	class list
	{
	public:
		typedef list_node<T> Node;
		typedef __list_iterator<T, T&, T*> iterator;   //非const迭代器
		typedef __list_iterator<T, const T&, const T*> const_iterator;  //const迭代器
	public:
		基本构造///
		//空初始化
		void empty_init()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}
		//构造
		list()
		{
			empty_init();
		}
		//拷贝构造
		list(const list<T>& lt)
		{
			//先创建空节点
			empty_init();
			//依次尾插即可
			for (auto e : lt)
			{
				push_back(e);
			}
		}
		//operator=
		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}
		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}
		//析构
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
			_size = 0;
		}
		///正向迭代器
		iterator begin()
		{
			return iterator(_head->_next); //使用匿名对象进行构造
		}
		iterator end()
		{
			return iterator(_head);
		}
		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}
		const_iterator end() const
		{
			return const_iterator(_head);
		}
		///修改相关接口
		//在pos位置插入节点
		iterator insert(iterator pos, const T& x)
		{
			//创建新新节点
			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;
			//更新节点个数
			++_size;
			//返回新节点的位置
			return iterator(newnode);
		}
		//删掉pos位置的节点
		iterator erase(iterator pos)
		{
			//保存相对位置
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			//链接节点
			delete cur;
			prev->_next = next;
			next->_prev = prev;
			//更新节点个数
			--_size;
			//返回pos的下一个位置
			return iterator(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);
			}
		}
		//节点个数
		size_t size()
		{
			return _size;
		}
	private:
		Node* _head;  //链表的头节点
		size_t _size; //节点个数
	};
}

朋友们、伙计们,美好的时光总是短暂的,我们本期的的分享就到此结束,欲知后事如何,请听下回分解~,最后看完别忘了留下你们弥足珍贵的三连喔,感谢大家的支持!  

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

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

相关文章

asp.net docker-compose添加volume配置

打开docker-compose.override.yml下面添加 volumes:killsb-one-sqldata:external: false 服务下面添加volume配置 volumes:- "./dapr/config/social-client.json:/app/OidcSettings.json" 添加volume配置成功

图片复制上传,拖拽输入框上传,el-upload自定义上传方法(上传和备注框强关联)

1. 效果图&#xff1a; 2. 复制图片使用的方法&#xff1a; 1.通过监听paste方法&#xff0c;获取复制内容2.获取复制内容中的clipboardData3.获取file文件进行上传 <input paste.native"handlePaste" />handlePaste(value){let files value.clipboardData…

网络基础扫盲-初识网络

博客内容&#xff1a;初识网络 文章目录 一、OSI七层网络模型二、TCP/IP四层模型1、MAC地址与IP地址 前言 在以前网络不够发之前&#xff0c;各个实验室进行一些研究时需要进行数据的交流&#xff0c;但是那时车马很慢&#xff0c;一生只够跑几次&#xff0c;所以就有人研究了网…

Java医院HIS系统源码

Java医院HIS系统源码 项目描述 该项目是用springbootlayuishiro写的医院管理系统&#xff0c;该系统的业务比较复杂&#xff0c;数据库一共有36张表。项目的视频业务参考文档&#xff0c;都在百度云盘中。可以先看看视频和参考文档。 运行环境 jdk8mysqlIntelliJ IDEAmaven…

IntelliJ IDEA 2023 最新版如何试用?IntelliJ IDEA 2023最新版试用方法及验证ja-netfilter配置成功提示

&#x1f337;&#x1f341; 博主猫头虎 带您 Go to New World.✨&#x1f341; &#x1f984; 博客首页——猫头虎的博客&#x1f390; &#x1f433;《面试题大全专栏》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33a; &a…

SOEM源码解析——ec_init(初始化单网卡主站)

0 工具准备 1.SOEM-master-1.4.0源码1 ec_init总览 /** Initialise lib in single NIC mode:初始化库在单网卡模式* param[in] ifname Dev name, f.e. "eth0" 设备名* return >0 if OK* see ecx_init*/ int ec_init(const char * ifname) {return ecx_init(&…

要讨个公道,要分辨真假

这里写自定义目录标题 欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题&#xff0c;有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants 创建一个自定义列表如何创建一个…

【redis面试题】数据持久化

文章目录 前言一、RDB 的概述RDB 的执行原理 二、AOF 的概述AOF 的特点 三、RDB 与 AOF 的区别 前言 跟着B站的黑马程序员学习面试题&#xff0c;目前是redis的第五个内容——数据持久化 课程传送门&#xff1a;redis——数据持久化 在 Redis 中&#xff0c;提供了两种数据持久…

windows mysql安装

1、首先去官网下载mysql安装包&#xff0c;官网地址&#xff1a;MySQL :: Download MySQL Community Server 2&#xff1a;把安装包放到你安装mysql的地方&#xff0c;然后进行解压缩&#xff0c;注意&#xff0c;解压后的mysql没有配置文件&#xff0c;我们需要创建配置文件 配…

C++17中std::any的使用

类sdk:any提供类型安全的容器来存储任何类型的单个值。通俗地说&#xff0c;std::any是一个容器&#xff0c;可以在其中存储任何值(或用户数据)&#xff0c;而无需担心类型安全。void*的功能有限&#xff0c;仅存储指针类型&#xff0c;被视为不安全模式。std::any可以被视为vo…

计算机组成与结构-计算机体系结构

计算机体系结构 指令系统 Flynn分类法 SISD&#xff08;单指令流单数据流&#xff09; 结构 控制部分&#xff1a;一个处理器&#xff1a;一个主存模块&#xff1a;一个 代表 单处理器系统 SIMD&#xff08;单指令流多数据流&#xff09; 结构 控制部分&#xff1a;一个处理…

【LeetCode刷题-链表】--876.链表的中间结点

876.链表的中间结点 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*…

linux笔记总结-基本命令

参考&#xff1a; 1.Linux 和Windows比 比较 &#xff08;了解&#xff09; 1. 记住一句经典的话&#xff1a;在 Linux 世界里&#xff0c;一切皆文件 2. Linux目录结构 /lib • 系统开机所需要最基本的动态连接共享库&#xff0c;其作用类似于Windows里的DLL文件。几 乎所有…

项目实战:通过axios加载水果库存系统的首页数据

1、创建静态页面 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</title><link rel"stylesheet" href"style/index.css"><script src"script/axios.mi…

手把手创建Android应用程序·案例程序分析

目录 1. Activity 组件 MainActivity 类 2.布局文件activity_main. xml 3.应用程序配置文件 AndroidManifest.xml 4. Android的应用程序组件 4.1 Activity——活动 4.2 Service——服务 4.3 Broadcast receiver——广播接收器 4.4 Content provider——内容提供者…

React 项目结构小结

React 项目结构小结 简单的记录一下目前 React 项目用的依赖和实现 摸索了大半年了大概构建一套用起来还算轻松的体系……&#xff1f;基本上应该是说可以应对大部分的项目了 使用的依赖 目前项目还在 refactoring 的阶段&#xff0c;所以乱得很&#xff0c;这里是新建一个…

【使用Python编写游戏辅助工具】第一篇:概述

引言 欢迎阅读本系列文章&#xff0c;本系列将带领读者朋友们使用Python来实现一个简单而有趣的游戏辅助工具。 写这个系列的缘由源自笔者玩了一款游戏。正巧&#xff0c;笔者对Python编程算是有一定的熟悉&#xff0c;且Python语言具备实现各种有趣功能的能力&#xff0c;因…

基于单片机的可穿戴个人健康监测仪-智能手环

收藏和点赞&#xff0c;您的关注是我创作的动力 文章目录 概要 一、方案的设计与论证2.1设计任务及要求2.2 模块技术和方法综述2.3 设计可能遇到的困难 二、 系统总体框架3.1 硬件设计 三 软件部分4.1 主程序流程框 四、 结论五、 文章目录 概要 近几年智能化的不断发展&#…

3000 台 Apache ActiveMQ 服务器易受 RCE 攻击

超过三千个暴露在互联网上的 Apache ActiveMQ 服务器容易受到最近披露的关键远程代码执行 (RCE) 漏洞的影响。 Apache ActiveMQ 是一个可扩展的开源消息代理&#xff0c;可促进客户端和服务器之间的通信&#xff0c;支持 Java 和各种跨语言客户端以及许多协议&#xff0c;包括…

HiveSQL中last_value函数的应用

一、背景 在以下数据中如何实现对每一个列按照更新时间取最新的非null值&#xff1f; 1 a a null 202301 202301 1 b b null null 202302 1 null c null null 202303 1 d null null null 202304如何实现…