C++：模拟实现list及迭代器类模板优化方法

文章目录

  • 迭代器
  • 模拟实现

本篇模拟实现简单的list和一些其他注意的点

在这里插入图片描述

迭代器

如下所示是利用拷贝构造将一个链表中的数据挪动到另外一个链表中，构造两个相同的链表

list(const list<T>& lt)
{
	emptyinit();
	for (auto e : lt)
	{
		push_back(e);
	}
}

void test_list1()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);

	list<int> l2(lt);
}

lt作为形参，传引用可以提高传参的效率，同时应该加上const修饰来保证不会因为不小心修改了形参导致外部的实参也被修改，这样的结果是不应该的，因此就要加const把这个形参变成一个const对象

而问题又来了，const对象要使用的是const迭代器，而前面没有写const迭代器，因此这里就引入了const迭代器的实现

从vector的模拟实现中，看似似乎只需要在原来的迭代器的基础上加上一个const即可，但事实上：

const迭代器和普通迭代器是两种不同的迭代器，不能直接在普通的迭代器后面加const，原因？

要解决这个问题，先重新回顾一下vector中const迭代器的定义流程：

对比vector的迭代器，vector中的迭代器const版本和非const版本直接在非const版本后面加const使它变成const迭代器即可，这样在调用的时候就可以直接进行调用

在这里插入图片描述

对iterator的定义，const版本就是在指针前面加上const，这样返回的就是const修饰的指针，因此就可以做到通过该迭代器只读，不可修改的作用

在这里插入图片描述

这里的迭代器本质上就是指针在底层进行访问，然后我们定义一个const指针，使得const指针就不能对指针指向的内容进行修改了

下面仿照vector修改的原理修改list

要修改的部分其实就是下面的代码：

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

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

在函数后加const很简单，但是核心是要把返回值也定义为const指针版本，这个过程要如何实现？

由于这里是把iterator封装成了一个类进行的实现，因此需要重新封装一个类进行实现

	template <class T>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef  __list_iterator<T> self;
		// 成员
		Node* _node;

		__list_iterator(Node* node)
			:_node(node)
		{}

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

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

		self operator++(int)
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

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

		T& operator*()
		{
			return _node->_data;
		}

		T* operator->()
		{
			return &_node->_data;
		}

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

		bool operator!=(const self& pos)
		{
			return !(*this == pos);
		}
	};

	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)
		{}

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

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

		self operator++(int)
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

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

		const T& operator*()
		{
			return _node->_data;
		}

		const T* operator->()
		{
			return &_node->_data;
		}

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

		bool operator!=(const self& pos)
		{
			return !(*this == pos);
		}
	};

但事实上，这两份代码只有很少的地方有区别，更多的内容都是相同的，这样是不满足较好的代码风格，因此在stl源码中，使用了模板对这两个类进行了封装

改进版本如下：

	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)
		{}

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

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

		self operator++(int)
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

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

		Ref operator*()
		{
			return _node->_data;
		}

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

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

		bool operator!=(const self& pos)
		{
			return !(*this == pos);
		}
	};

	template <class T>
	class list
	{
		void emptyinit()
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}
	public:
		typedef list_node<T> Node;
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;

		// 构造函数 
		list()
		{
			emptyinit();
		}
		// 拷贝构造
		list(const list<T>& lt)
		{
			emptyinit();
			auto it = lt.begin();
			//*it = 30;
		}

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

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

		// head     tail->prev  tail
		void pop_back()
		{
			erase(--end());
		}

		void pop_front()
		{
			erase(begin());
		}

		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);
		}

		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(x);

			//        newnode
			//   prev         cur
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;

			return iterator(newnode);
		}

		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

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

			return iterator(next);
		}

	private:
		Node* _head;
		size_t _size;
	};

这里引入了类模板的概念，简单来说，当需要调用const类型时就会模板实例化出一个const版本的迭代器，再进行相关的操作，这样的操作可以避免代码冗余，也是模板的强大之处

模拟实现

#pragma once

// 实现的是双向循环链表，链表中应该包含节点类和迭代器类，节点类用于从内存中申请节点，迭代器类用于获取节点指针
namespace mylist
{
	// 把节点进行封装，可以动态获取一个节点
	template <class T>
	struct list_node
	{
		// 成员
		list_node<T>* _next;
		list_node<T>* _prev;
		T _data;

		// 成员函数
		list_node(const T& val = T())
			:_data(val)
			, _next(nullptr)
			, _prev(nullptr)
		{}
	};

	// 对迭代器进行封装，使得外界看到的是迭代器
	// 迭代器当中存储的是某个节点的指针
	// 可以对迭代器进行各项操作
	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)
		{}

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

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

		self operator++(int)
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

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

		Ref operator*()
		{
			return _node->_data;
		}

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

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

		bool operator!=(const self& pos)
		{
			return !(*this == pos);
		}
	};

	// 适配器 -- 复用
	template <class T, class Ref, class Ptr >
	struct __reverse_iterator
	{
		typedef list_node<T> Node;
		typedef  __reverse_iterator<T, Ref, Ptr> self;
		// 成员
		Node* _node;

		__reverse_iterator(Node* node)
			:_node(node)
		{}

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

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

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

		self operator--(int)
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		Ref operator*()
		{
			return _node->_data;
		}

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

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

		bool operator!=(const self& pos)
		{
			return !(*this == pos);
		}
	};


	template <class T>
	class list
	{
		void emptyinit()
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}
	public:
		typedef list_node<T> Node;
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;
		typedef __reverse_iterator<T, T&, T*> reverse_iterator;
		typedef __reverse_iterator<T, const T&, const T*> const_reverse_iterator;

		// 构造函数 
		list()
		{
			emptyinit();
		}
		// 拷贝构造
		list(const list<T>& lt)
		{
			emptyinit();
			auto it = lt.begin();
			//*it = 30;
		}

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

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

		// head     tail->prev  tail
		void pop_back()
		{
			erase(--end());
		}

		void pop_front()
		{
			erase(begin());
		}

		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);
		}

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

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

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

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

		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(x);

			//        newnode
			//   prev         cur
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;

			return iterator(newnode);
		}

		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

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

			return iterator(next);
		}

	private:
		Node* _head;
		size_t _size;
	};


	void test_list1()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);
		
		cout << "正序" << endl;
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		cout << "逆序" << endl;
		auto rit = lt.rbegin();
		while (rit != lt.rend())
		{
			cout << *rit << " ";
			rit++;
		}
		cout << endl;
	}
}

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

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

相关文章

CSS练习

CSS练习

CSS练习 工具代码运行结果 工具 HBuilder X 代码 <!DOCTYPE html> <!-- 做一个表格&#xff0c;6行4列实现隔行换色&#xff08;背景色&#xff09;并且第3列文字红色第一个单元格文字大小30px。最后一个单元格文字加粗--> <html><head><meta ch…
阅读更多...
android app控制ros机器人五（百度地图）

android app控制ros机器人五（百度地图）

半吊子改安卓&#xff0c;新增了标签页&#xff0c;此标签页需要显示百度地图 按照官方教程注册信息&#xff0c;得到访问应用AK&#xff0c;步骤也可以参照下面csdn Android地图SDK | 百度地图API SDK 【Android】实现百度地图显示_宾有为的博客-CSDN博客 本人使用的是aar开…
阅读更多...
【深度学习】NLP中的对抗训练

【深度学习】NLP中的对抗训练

在NLP中&#xff0c;对抗训练往往都是针对嵌入层&#xff08;包括词嵌入&#xff0c;位置嵌入&#xff0c;segment嵌入等等&#xff09;开展的&#xff0c;思想很简单&#xff0c;即针对嵌入层添加干扰&#xff0c;从而提高模型的鲁棒性和泛化能力&#xff0c;下面结合具体代码…
阅读更多...
基于Spring Boot的高校在线考试系统的设计与实现（Java+spring boot+VUE+MySQL）

基于Spring Boot的高校在线考试系统的设计与实现（Java+spring boot+VUE+MySQL）

获取源码或者论文请私信博主 演示视频&#xff1a; 基于Spring Boot的高校在线考试系统的设计与实现&#xff08;Javaspring bootVUEMySQL&#xff09; 使用技术&#xff1a; 前端&#xff1a;html css javascript jQuery ajax thymeleaf 微信小程序 后端&#xff1a;Java s…
阅读更多...
vue或uniapp使用pdf.js预览

vue或uniapp使用pdf.js预览

一、先下载稳定版的pdf.js&#xff0c;可以去官网下载 官网下载地址 或 pdf.js包下载(已配置好&#xff0c;无需修改) 二、下载好的pdf.js文件放在public下静态文件里&#xff0c; uniapp是放在 static下静态文件里 三、使用方式 1. vue项目 注意路径 :src"static/pd…
阅读更多...
Windows CMD 关闭，启动程序

Windows CMD 关闭，启动程序

Windows CMD 关闭&#xff0c;启动程序 1. Windows 通过 CMD 命令行关闭程序 示例&#xff1a;通过 taskkill 命令关闭 QQ 管家&#xff0c;但是这里有个问题&#xff0c;使用命令行关闭 QQ 管家时&#xff0c;会提示“错误: 无法终止 PID 1400 (属于 PID 22116 子进程)的进程…
阅读更多...
wps设置一键标题字体和大小

wps设置一键标题字体和大小

参考 wps设置一键标题字体和大小&#xff1a;https://www.kafan.cn/A/7v5le1op3g.html 统一一键设置
阅读更多...
echarts-convert.js使用

echarts-convert.js使用

echarts-convert.js demo 点击下载 1、本地安装phantom.js插件 点击下载 2、更改文件路径 &#xff08;D:\phantomjs-2.1.1-windows\bin&#xff09;改为本地项目文件路径 3、打开cmd命令行&#xff0c;并格式化语言 运行以下命令 将命令行语言改为中文简体 chcp 65001…
阅读更多...
【Rust】Rust学习 第九章错误处理

【Rust】Rust学习 第九章错误处理

Rust 将错误组合成两个主要类别&#xff1a;可恢复错误&#xff08;recoverable&#xff09;和 不可恢复错误&#xff08;unrecoverable&#xff09;。可恢复错误通常代表向用户报告错误和重试操作是合理的情况&#xff0c;比如未找到文件。不可恢复错误通常是 bug 的同义词&am…
阅读更多...
使用GUI Guider工具在MCU上开发嵌入式GUI应用 (1) - GUI Guider简介及安装

使用GUI Guider工具在MCU上开发嵌入式GUI应用 (1) - GUI Guider简介及安装

使用GUI Guider工具在MCU上开发嵌入式GUI应用 (1) - GUI Guider简介及安装 受限于每篇文章最多只能贴9张图的限制&#xff0c;这个教程被拆分成了多篇文章连载发布&#xff0c;完整目录结构如下图x所示。后续会发布完整教程的pdf文件&#xff0c;敬请期待。 图x 完整教程文档…
阅读更多...
Linux 基础（五）常用命令-文件属性

Linux 基础（五）常用命令-文件属性

文件属性 文件权限文件属性修改文件权限属性 文件所有者 文件权限 文件属性 Linux中文件权限 可以通过文件属性体现&#xff1b; 使用 ll 查看文件列表 最前面的 l d 表示文件类型 1 5 表示硬链接数 或者 子文件夹个数 所属用户 所属用户组 文件大小 创建/更新时间 文件&…
阅读更多...
ComponentOne Studio ASP.NET MVC Crack

ComponentOne Studio ASP.NET MVC Crack

ComponentOne Studio ASP.NET MVC Crack FlexReport增强功能 添加了对在Microsoft Windows上部署Microsoft Azure的支持。 添加了对显示嵌入字体的支持。 .NET标准版的经典C1PDF(Beta版) GrapeCity的经典C1Pdf库现在提供了基于Microsoft.NET标准的版本。在任何.NET应用程序(包括…
阅读更多...
numba 入门示例

numba 入门示例

一维向量求和&#xff1a; C A B 在有nv 近几年gpu的ubuntu 机器上&#xff0c; 环境预备&#xff1a; conda create -name numba_cuda_python3.10 python3.10 conda activate numba_cuda_python3.10conda install numba conda install cudatoolkit conda install -c nvi…
阅读更多...
【Redis实践篇】使用Redisson 优雅实现项目实践过程中的5种场景

【Redis实践篇】使用Redisson 优雅实现项目实践过程中的5种场景

文章目录 1.前言2.使用方式1. 添加Redisson依赖&#xff1a;2. 配置Redis连接信息3. 使用场景3.1. 分布式锁3.2. 限流器&#xff08;Rate Limiter&#xff09;3.3. 可过期的对象&#xff08;Expirable Object&#xff09;3.4. 信号量&#xff08;Semaphore&#xff09;3.5. 分布…
阅读更多...
实践-CNN卷积层

实践-CNN卷积层

实践-CNN卷积层 1 卷积层构造2 整体流程3 BatchNormalization效果4 参数对比5 测试效果 1 卷积层构造 2 整体流程 根据网络结构来写就可以了。 池化 拉平 训练一个网络需要2-3天的时间。用经典网络来&#xff0c;一些细节没有必要去扣。 损失函数&#xff1a; fit模型&…
阅读更多...
【网络基础】应用层协议

【网络基础】应用层协议

【网络基础】应用层协议 文章目录 【网络基础】应用层协议1、协议作用1.1 应用层需求1.2 协议分类 2、HTTP & HTTPS2.1 HTTP/HTTPS 简介2.2 HTTP工作原理2.3 HTTPS工作原理2.4 区别 3、URL3.1 编码解码3.2 URI & URL 4、HTTP 消息结构4.1 HTTP请求方法4.2 HTTP请求头信…
阅读更多...
欧拉函数和最大公约数

欧拉函数和最大公约数

分析&#xff1a;如果两个数的最大公约数是一个质数p&#xff0c;那么这两个数都除以p&#xff0c;得到的两个数的最大公约数一定是1. 反证法&#xff1a;如果得到的两个数的最大公约数不是1&#xff0c;那么把此时的最大公约数乘以上边的最大公约数&#xff0c;得到的一定比上…
阅读更多...
【解读Spikingjelly】使用单层全连接SNN识别MNIST

【解读Spikingjelly】使用单层全连接SNN识别MNIST

原文档&#xff1a;使用单层全连接SNN识别MNIST — spikingjelly alpha 文档 代码地址&#xff1a;完整的代码位于activation_based.examples.lif_fc_mnist.py GitHub - fangwei123456/spikingjelly: SpikingJelly is an open-source deep learning framework for Spiking Neur…
阅读更多...
Java真实面试题，offer已到手

Java真实面试题，offer已到手

关于学习 在黑马程序员刚刚开始的时候学习尽头非常足&#xff0c;到后面逐渐失去了一些兴趣&#xff0c;以至于后面上课会出现走神等问题&#xff0c;但是毕业时后悔晚矣。等到开始学习项目一的时候&#xff0c;思路总会比别人慢一些&#xff0c;不看讲义写不出来代码。 建议…
阅读更多...
Kubuesphere部署Ruoyi：持久化存储配置

Kubuesphere部署Ruoyi：持久化存储配置

按照如下教程配置NFS 先服务器&#xff1a;搭建 NFS 服务器 后客户端&#xff1a;安装 NFS Client 按照链接操作以后&#xff0c;在客户端上面把目录挂载到服务端 rootclient_banana:/# mount 172.25.110.41:/mnt/nfs_share /mnt/client_floder 客户端: mount <server-ip…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站