list 的实现

目录

list

结点类

结点类的构造函数

list的尾插尾删

list的头插头删

迭代器

++运算符重载

--运算符重载

==和!= 运算符重载

* 和 -> 运算符重载

 list 的insert

list的erase

list

list实际上是一个带头双向循环链表,要实现list,则首先需要实现一个结点类,而一个结点需要存储的信息为:数据、前驱指针、后继指针

而对于该结点类的成员函数来说,我们只需实现一个构造函数即可,因为该结点类只需要根据数据来构造一个结点即可,而结点的释放则由list的析构函数来完成,

结点类

结点类的基本结构：

	template<class T>
	struct ListNode
	{
		ListNode<T>* _next;
		ListNode<T>* _prev;
		T _date;

		ListNode(const T& pos = T())
		{
			_next = nullptr;
			_prev = nullptr;
			_date = pos;
		}
	};

这里用struct 的原因是因为ListNode 的 每个成员变量都会被频繁调用。

用struct则不需要封装了。

结点类的构造函数

构造函数直接根据所给数据构造一个结点即可,构造出来的结点的数据域存储的就是所给数据,而前驱指针和后继指针均初始化为空指针即可

		ListNode(const T& pos = T())
		{
			_next = nullptr;
			_prev = nullptr;
			_date = pos;
		}

list的尾插尾删

	template<class T>
	class list
	{
	public:
		typedef ListNode<T> node;	
		list()
			:_head(new node)
		{
			_head->_next = _head;
			_head->_prev = _head;
		}
	    void push_back(const T& x)
		{
			node* head = _head;
			node* tail = _head->_prev;
			node* p = new node(x);
			tail->_next = p;
			p->_prev = tail;
			p->_next = head;
			head->_prev = p;
		}

		void pop_back()
		{
			assert(_head != _head->_next);
			node* head = _head;
			node* tail = head->_prev;
			node* newtail = tail->_prev;
			newtail->_next = head;
			head->_prev = newtail;
			delete[] tail;
		}
	private:
		node* _head;
	};

list的头插头删

	template<class T>
	class list
	{

	public:	
		typedef ListNode<T> node;
		list()
			:_head(new node)
		{
			_head->_next = _head;
			_head->_prev = _head;
		}
		void push_front(const T& x)
		{
			node* newnode = new node(x);
			node* head = _head;
			node* tail = _head->_next;
			head->_next = newnode;
			newnode->_prev = head;
			newnode->_next = tail;
			tail->_prev = newnode;
		}

		void pop_front()
		{
			assert(_head != _head->_next);
			node* head = _head;
			node* tail = _head->_next;
			head->_next = tail->_next;
			tail->_next->_prev = head;
			delete[]tail;
		}
	private:
		node* _head;
	};

迭代器

迭代器有两种实现方式,具体应根据容器底层数据结构实现：

  1. 原生态指针,比如：vector和string ->物理空间是连续的，因为string和vector对象都将其数据存储在了一块连续的内存空间,我们通过指针进行自增、自减以及解引用等操作,就可以对相应位置的数据进行一系列操作,因此string和vector当中的迭代器就是原生指针。
  2. .将原生态指针进行封装,因迭代器使用形式与指针完全相同,因此在自定义的类中必须实现以下方法：

指针可以解引用,迭代器的类中必须重载operator*()
指针可以通过->访问其所指空间成员,迭代器类中必须重载oprator->()
指针可以++向后移动,迭代器类中必须重载operator++()与operator++(int)
至于operator--()/operator--(int) 是否需要重载,根据具体的结构来抉择,双向链表可
以向前 移动,所以需要重载,如果是forward_list就不需要重载–
迭代器需要进行是否相等的比较,因此还需要重载operator==()与operator!=()
但是对于list来说,其各个结点在内存当中的位置是随机的,并不是连续的,我们不能仅通过结点指针的自增、自减以及解引用等操作对相应结点的数据进行操作,

总结：list的迭代器 实际上就是对结点指针进行了封装,对其各种运算符进行了重载,使得结点指针的各种行为看起来和普通指针一样,（例如,对结点指针自增就能指向下一个结点 p = p->next）

	template<class T1, class T2>
	struct Reverse_iterator
	{
		typedef Reverse_iterator<T1, T2> self;
		typedef ListNode<T1> node;

		node* _it;

		Reverse_iterator(node* pos)；
		self& operator++()；
		self operator++(int)；
		self& operator--()；
		self operator--(int)；
		T2& operator*()；
		T2* operator->()；
		bool operator!=(const self& pos)；
		bool operator==(const self& pos)；

    }；

迭代器模板参数说明：

构造函数
迭代器类实际上就是对结点指针进行了封装

其成员变量就是结点指针,所以其构造函数直接根据所给结点指针构造一个迭代器对象即可,

		Reverse_iterator(node* pos)
		{
			_it = pos;
		}

拷贝构造,operator,析构函数我们都不需要写,因为成员变量是内置类型(指针), 用编译器默认生成的就可以。

++运算符重载

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

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

前置++原本的作用是将数据自增,然后返回自增后的数据,

而对于结点迭代器的前置++:应该先让结点指针指向后一个结点.然后再返回“自增”后的结点迭代器即可

后置++,先拷贝构造当前迭代器结点, 然后让当前迭代器结点的指针自增指向下一个结点,最后返回“自增”前的结点迭代器即可,

--运算符重载

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

		self operator--(int)//后置
		{
			self tmp(_it);
			_it = _it->_next;
			return tmp;
		}

前置- -：当前迭代器结点中的指针指向前一个结点,然后再返回“自减”后的结点迭代器即可,

后置--：拷贝构造当前迭代器对象 -> 当前迭代器结点中的指针自减指向前一个结点 ->返回自减前的迭代器。

==和!= 运算符重载

		bool operator!=(const self& pos)
		{
			return _it != pos._it;
		}

		bool operator==(const self& pos)
		{
			return _it == pos._it;
		}

这里注意形参别写错就好了。

* 和 -> 运算符重载

使用解引用操作符时,是想得到该指针指向的数据内容

因此,我们直接返回当前结点指针所指结点的数据即可,这里需要使用引用返回,因为解引用后可能需要对数据进行修改,

		T2& operator*()
		{
			return _it->_date;
		}

->返回当前迭代器结点的指针所指结点的数据的地址

		T2* operator->()
		{
			return &_it->_date;
		}

使用场景：

 list 的insert

insert函数可以在所给迭代器pos之前插入一个新结点,

1.先根据所给迭代器pos得到该位置处的结点指针

2.然后通过该指针找到前一个位置的结点指针last

根据所给数据x构造一个新结点

		iterator insert(iterator pos,const T& x)
		{
			node* newnode = new node(x);
			node* next = pos._node;
			node* last = next->_prev;
			last->_next = newnode;
			newnode->_prev = last;
			newnode->_next = next;
			next->_prev = newnode;
			return iterator(newnode);
		}

list的erase

erase函数可以删除所给迭代器位置的结点,

注意**:pos不可以是哨兵位的迭代器,即不能删除哨兵位 pos迭代器结点中的指针不能为空**

1.根据所给迭代器得到该位置处的结点指针self

2.通过self指针找到前一个位置的结点指针last,以及后一个位置的结点指针next

3.紧接着释放cur结点,最后prev和next结点进行链接

		iterator erase(iterator pos)
		{
			assert(pos._node);
			assert(_head != _head->_next);
			node* self = pos._node;
			node* next = self->_next;
			node* last = self->_prev;
			last->_next = next;
			next->_prev = last;
			delete[] self;
			return iterator(next);
		}

关于insert 和 erase 迭代器失效的问题：

insert不会导致迭代器失效,因为pos迭代器中的节点指针仍然指向原来的节点。

问:erase之后, pos迭代器是否失效：
一定失效,因为此时pos迭代器中的节点指针指向的节点已经被释放了,该指针相当于是野指针。

 最后所有代码如下：
 

namespace bit
{
	template<class T>
	struct ListNode
	{
		ListNode<T>* _next;
		ListNode<T>* _prev;
		T _date;

		ListNode(const T& pos = T())
		{
			_next = nullptr;
			_prev = nullptr;
			_date = pos;
		}
	};

	template<class T1,class T2 = T1>
	struct ListIterator
	{
		typedef ListIterator<T1,T2> iterator;
		typedef ListNode<T1> node;
		node* _node;

		ListIterator(node* pos)
		{
			_node = pos;
		}

		T2& operator*()
		{
			return _node->_date;
		}

		iterator& operator++()
		{
			_node = _node->_next;
			return *this;
		}		

		iterator operator++(int)
		{
			iterator tmp(_node);
			_node = _node->_next;
			return tmp;
		}

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

		T2* operator->()
		{
			return &_node->_date;
		}

		bool operator!=(const iterator& pos)
		{
			return _node != pos._node;
		}

		bool operator==(const iterator& pos)
		{
			return _node == pos._node;
		}
	};

	template<class T1, class T2>
	struct Reverse_iterator
	{
		typedef Reverse_iterator<T1, T2> self;
		typedef ListNode<T1> node;

		node* _it;

		Reverse_iterator(node* pos)
		{
			_it = pos;
		}

		self& operator++()
		{
			_it =_it->_prev;
			return *this;
		}

		self operator++(int)
		{
			self tmp(_it);
			_it = _it->_prev;
			return tmp;
		}

		self& operator--()
		{
			_it = _it->_next;
			return *this;
		}

		self operator--(int)
		{
			self tmp(_it);
			_it = _it->_next;
			return tmp;
		}

		T2& operator*()
		{
			return _it->_date;
		}

		T2* operator->()
		{
			return &_it->_date;
		}

		bool operator!=(const self& pos)
		{
			return _it != pos._it;
		}

		bool operator==(const self& pos)
		{
			return _it == pos._it;
		}
	};

	template<class T>
	class list
	{

	public:
		typedef Reverse_iterator<T, T> reverse_iterator;
		typedef Reverse_iterator<T, const T> const_reverse_iterator;
		typedef ListNode<T> node;
		typedef ListIterator<T> iterator;
		typedef ListIterator<T,const T> const_iterator;
		list()
			:_head(new node)
		{
			_head->_next = _head;
			_head->_prev = _head;
		}

		list(const list& pos)
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
			for (auto e : pos)
			{
				push_back(e);
			}
		}

		list(initializer_list<T> il)
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
			for (auto e : il)
			{
				push_back(e);
			}

		}

		void push_back(const T& x)
		{
			node* head = _head;
			node* tail = _head->_prev;
			node* p = new node(x);
			tail->_next = p;
			p->_prev = tail;
			p->_next = head;
			head->_prev = p;
		}

		void pop_back()
		{
			assert(_head != _head->_next);
			node* head = _head;
			node* tail = head->_prev;
			node* newtail = tail->_prev;
			newtail->_next = head;
			head->_prev = newtail;
			delete[] tail;
		}

		reverse_iterator rbegin()
		{
			return reverse_iterator(_head->_prev);
		}

		reverse_iterator rend()
		{
			return reverse_iterator(_head);
		}

		const_reverse_iterator crbegin()const
		{
			return const_reverse_iterator(_head->_prev);
		}

		const_reverse_iterator crend()const
		{
			return const_reverse_iterator(_head);
		}


		iterator begin()
		{
			return iterator(_head->_next);
		}

		const_iterator begin()const
		{
			return const_iterator(_head->_next);
		}

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

		const_iterator end()const
		{
			return const_iterator(_head);
		}

		void push_front(const T& x)
		{
			node* newnode = new node(x);
			node* head = _head;
			node* tail = _head->_next;
			head->_next = newnode;
			newnode->_prev = head;
			newnode->_next = tail;
			tail->_prev = newnode;
		}

		void pop_front()
		{
			assert(_head != _head->_next);
			node* head = _head;
			node* tail = _head->_next;
			head->_next = tail->_next;
			tail->_next->_prev = head;
			delete[]tail;
		}

		iterator insert(iterator pos,const T& x)
		{
			node* newnode = new node(x);
			node* next = pos._node;
			node* last = next->_prev;
			last->_next = newnode;
			newnode->_prev = last;
			newnode->_next = next;
			next->_prev = newnode;
			return iterator(newnode);
		}

		iterator erase(iterator pos)
		{
			assert(pos._node);
			assert(_head != _head->_next);
			node* self = pos._node;
			node* next = self->_next;
			node* last = self->_prev;
			last->_next = next;
			next->_prev = last;
			delete[] self;
			return iterator(next);
		}

		~list()
		{
			iterator it1 = begin();
			while (it1 != end())
			{
				it1 = erase(it1);
			}
			delete _head;
			_head = nullptr;
		}

	private:
		node* _head;
	};

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

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

相关文章

InnoDB Data Locking - Part 2 “Locks“

InnoDB Data Locking - Part 2 “Locks“

什么是数据库“锁”&#xff1f; 当我熟悉数据库术语时&#xff0c;我发现非常困惑的一件事是“锁【lock】”这个词在数据库中的含义与在编程中的含义不同。 在编程中&#xff0c;如果你有一个“锁”&#xff0c;那么它就是内存中存储在某个地址下的单个对象&#xff0c;然后有…
阅读更多...
【Mac】关于Mac的github配置和本地项目上传

【Mac】关于Mac的github配置和本地项目上传

目录 前言什么是github?有什么用?github个人账户创建Mac的git环境配置生成密钥将密钥添加到github 创建github仓库将本地文件上传至github仓库一些常用的git命令总结 前言 本文主要介绍了Mac的git环境配置&#xff0c;github仓库的创建&#xff0c;本地文件上传到github仓库以…
阅读更多...
分享268款漂亮的3D模型和视觉效果的制作和展示源码

分享268款漂亮的3D模型和视觉效果的制作和展示源码

分享268款漂亮的3D模型和视觉效果的制作和展示源码&#xff0c;总有一款是你需要的&#xff0c;源码演示下载地址如下&#xff1a;https://www.erdangjiade.com/js/178-0-0-0 Html跨年烟花代码&#xff0c;JS实现烟花表白代码 最新程序员表白我爱你玫瑰花代码 纯CSS3实现3D Tw…
阅读更多...
【赠书第26期】AI绘画教程：Midjourney使用方法与技巧从入门到精通

【赠书第26期】AI绘画教程：Midjourney使用方法与技巧从入门到精通

文章目录 前言 1 Midjourney入门指南 1.1 注册与登录 1.2 界面熟悉 1.3 基础操作 2 Midjourney进阶技巧 2.1 描述词优化 2.2 参数调整 2.3 迭代生成 3 Midjourney高级应用 3.1 创意启发 3.2 团队协作 3.3 商业应用 4 总结与展望 5 推荐图书 6 粉丝福利 前言 在…
阅读更多...
Oracle导出clob字段到csv

Oracle导出clob字段到csv

使用UTL_FILE ref: How to Export The Table with a CLOB Column Into a CSV File using UTL_FILE ?(Doc ID 1967617.1) --preapre data CREATE TABLE TESTCLOB(ID NUMBER, MYCLOB1 CLOB, MYCLOB2 CLOB ); INSERT INTO TESTCLOB(ID,MYCLOB1,MYCLOB2) VALUES(1,Sample row 11…
阅读更多...
标准化产品需求文档逻辑思路

标准化产品需求文档逻辑思路

​PRD被公认为产品经理的标准文档&#xff0c;但你写PRD文档时是否做过这些事&#xff1a; 1.下载模版&#xff0c;填入内容&#xff1b; 2.不了解的章节内容&#xff0c;略过或删掉&#xff1b; 3.找己经做好的PRD&#xff0c;做内容替换。 以前我所在的公司&#xff0c;PRD管…
阅读更多...
用Idea 解决Git冲突

用Idea 解决Git冲突

https://intellijidea.com.cn/help/idea/resolving-conflicts.html https://www.jetbrains.com/help/idea/resolve-conflicts.html idea 官方文档 当您在团队中工作时&#xff0c;您可能会遇到这样的情况:有人对您当前正在处理的文件进行更改。如果这些更改没有重叠(也就是说…
阅读更多...
Linux系统使用Docker安装Drupal结合内网穿透实现远程访问管理后台

Linux系统使用Docker安装Drupal结合内网穿透实现远程访问管理后台

目录 前言 1. Docker安装Drupal 2. 本地局域网访问 3 . Linux 安装cpolar 4. 配置Drupal公网访问地址 5. 公网远程访问Drupal 6. 固定Drupal 公网地址 前言 作者简介&#xff1a; 懒大王敲代码&#xff0c;计算机专业应届生 今天给大家聊聊Linux系统使用Docker安装Drupal…
阅读更多...
接口测试工具：Postman的下载安装及使用

接口测试工具：Postman的下载安装及使用

1 Postman 介绍 1.1 Postman 是什么 Postman 是一款功能超级强大的用于发送 HTTP 请求的 测试工具 做 WEB 页面开发和测试的人员常用工具 创建和发送任何的 HTTP 请求(Get/Post/Put/Delete...) 1.2 Postman 相关资源 1.2.1 官方网站&#xff1a;https://www.postman.com/ …
阅读更多...
CCIG 2024：合合信息文档解析技术突破与应用前景

CCIG 2024：合合信息文档解析技术突破与应用前景

目录 背景当前大模型训练和应用面临的问题训练Token耗尽训练语料质量要求高LLM文档问答应用中文档解析不精准 合合信息的文档解析技术1. 具备多文档元素识别能力2. 具备版面分析能力3. 高性能的文档解析4. 高精准、高效率的文档解析文档多板式部分示例 文档解析典型技术难点元素…
阅读更多...
基于Java的KTV点歌系统

基于Java的KTV点歌系统

开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;JSP技术&#xff0c;JAVA&#xff0c;B/S架构 工具&#xff1a;浏览器&#xff08;360浏览器、谷歌浏览器、QQ浏览器等&#xff09;&#xff0c;数据库管理工具&#xff08;MySQL&#xff09; 系统展示 …
阅读更多...
GPT-4o：人工智能技术的新巅峰

GPT-4o：人工智能技术的新巅峰

人不走空 &#x1f308;个人主页&#xff1a;人不走空 &#x1f496;系列专栏&#xff1a;算法专题 ⏰诗词歌赋&#xff1a;斯是陋室&#xff0c;惟吾德馨 目录 &#x1f308;个人主页&#xff1a;人不走空 &#x1f496;系列专栏&#xff1a;算法专题 ⏰诗词歌…
阅读更多...
DBeaver连接Oracle报错：ORA-12514

DBeaver连接Oracle报错：ORA-12514

Listener refused the connection with the following error:ORA-12514, TNS:listener does not currently know of service requested inconnect descriptor ———————————————— 1.报错信息2.配置正确结语 ———————————————— 如果是第一次连接Or…
阅读更多...
IP地址开启HTTPS方法

IP地址开启HTTPS方法

可以使用IP地址申请SSL证书&#xff0c;申请之前必须是公网IP地址&#xff0c;不支持内网IP地址申请。 申请过程需要确定IP地址外网可以访问&#xff0c;这里特别注意只是申请过程中可以访问。访问验证过程必须采取80端口、443端口两者选择1个&#xff0c;不可以用其它端口进行…
阅读更多...
「手把手prompt1」相关介绍

「手把手prompt1」相关介绍

「手把手prompt1」相关介绍 在人工智能领域迅速发展的当下&#xff0c;“prompt” 这个术语正逐渐成为焦点。本文将带您深入了解prompt的本质&#xff0c;以及它如何影响我们与AI系统的互动。您将学习到&#xff0c;通过精确的指令设计&#xff0c;可以引导AI系统产出精确和有…
阅读更多...
使用Minikube+docker+harbor+k8s自动化部署 @by_TWJ

使用Minikube+docker+harbor+k8s自动化部署 @by_TWJ

目录 1. 开始1.1. 环境1.2. 测试的git仓库1.3. 离线文件1.4. 安装docker1.5. 安装docker-compose&#xff08;非必要&#xff09;1.6. 安装Jenkins1.7. 安装harbor1.8. 允许docker通过http访问私有仓库1.9. 修改/etc/hosts&#xff0c;追加自定义域名1.10. 安装Minikube 2. min…
阅读更多...
【JavaScript】ECMAS6（ES6）新特性概览（一）：变量声明let与const、箭头函数、模板字面量全面解析

【JavaScript】ECMAS6（ES6）新特性概览（一）：变量声明let与const、箭头函数、模板字面量全面解析

&#x1f525; 个人主页&#xff1a;空白诗 &#x1f525; 热门专栏&#xff1a;【JavaScript】 文章目录 &#x1f33f; 引言一、 let 和 const - 变量声明的新方式 &#x1f31f;&#x1f4cc; var的问题回顾&#x1f4cc; let的革新&#x1f4cc; const的不变之美 二、 Arro…
阅读更多...
CasaOS玩客云安装全平台高速下载器Gopeed并实现远程访问

CasaOS玩客云安装全平台高速下载器Gopeed并实现远程访问

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…
阅读更多...
Spring-Cloud-CircuitBreaker-Resilience4j （3.1.1）

Spring-Cloud-CircuitBreaker-Resilience4j （3.1.1）

介绍 Resilience4j 是一个专为函数式编程而设计的轻量级容错库。Resilience4j 提供高阶函数&#xff08;装饰器&#xff09;&#xff0c;以增强任何功能接口、lambda 表达式或方法引用&#xff0c;包括断路器、速率限制器、重试或隔板。您可以在任何函数接口、lambda 表达式或…
阅读更多...
每日复盘-20240530

每日复盘-20240530

今日重点关注&#xff1a; 20240530 六日涨幅最大: ------1--------300637--------- 扬帆新材 五日涨幅最大: ------1--------300637--------- 扬帆新材 四日涨幅最大: ------1--------300637--------- 扬帆新材 三日涨幅最大: ------1--------301129--------- 瑞纳智能 二日涨…
阅读更多...
最新文章

Copyright @ 2022~2023