[C++]反向迭代器

目录

前言:

1 对反向迭代器的构造思想

2 实现反向迭代器

3 完整代码


前言:

        本篇文章主要介绍了STL容器当中的反向迭代器,可能有朋友会说:“反向迭代器有什么好学的?不一样还是迭代器吗,我正向能写出来,还写不出反向?”有这种想法的朋友那你可得好好的看看咯,相信这对你有很大的帮助。

1 对反向迭代器的构造思想

        以同类逻辑去考虑迭代器,我们反向迭代器应该与正向迭代器构造思想相同,正向迭代器的begin指向第一个数据,end指向最后一个数据的后一位,那么我们的反向迭代器也应该是rbegin指向倒数第一个数据,rend指向第一个数据的前一位,如下图:

         我相信大多数人对于第一次遇到反向迭代器的想法都是这样的,包括博主自己,这也没有任何的问题,同样是能够实现反向迭代器的功能,但是这不是重点,我们实现这个思想时,多数会向下方代码那样,我以list举例,以这样的想法我们就会构建出这样的反向迭代器。

template<class T, class Ref, class Ptr>
struct __list_reverse_iterator
{
	typedef list_node<T> node;
	typedef __list_reverse_iterator<T, Ref, Ptr> self;
	node* _node;

	__list_reverse_iterator(node* n)
		:_node(n)
	{}

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

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

	self& operator++()
	{
		_node = _node->_prev;

		return *this;
	}

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

		return tmp;
	}

	self& operator--()
	{
		_node = _node->_next;

		return *this;
	}

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

		return tmp;
	}

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

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

        上述代码没有任何问题,博主也测试过能够实现反向迭代器的功能,但是呢看着这个代码是不是觉得很不爽啊,因为这反向迭代器通过这种另外封装一个类的方式,然后实现了一个与正向迭代器相互冗余的功能,这代码相似度太高了,写出来都觉得代码很挫,不好意思说出去是自己写的。

        基于此,请看看大佬是如何设计的吧。

         大佬干了啥,直接将正向迭代器作为反向迭代器的模板类型,在反向迭代器中重定义操作符,然后使用正向迭代器的功能,当然这个方式也是需要重新封装一个类,大伙还是看不出来有啥牛逼的,请继续往下看。

2 实现反向迭代器

代码:

template<class iterator, class Ref, class Ptr>
struct __list_reverse_iterator
{
	typedef __list_reverse_iterator<iterator, Ref, Ptr> Self;
	iterator _cur;

	__list_reverse_iterator(iterator it)
		:_cur(it)
	{}

	Ref operator*()
	{
		iterator temp = _cur;
		return *(--temp);
	}

	Self& operator++()
	{
		--_cur;
		return *this;
	}

	Self& operator--()
	{
		++_cur;
		return *this;
	}

	bool operator!=(const Self& ss)
	{
		return _cur != ss._cur;
	}
};

        看到我们的代码,因为反向迭代器的类型是正向迭代器,所以我们需要在里面放置一个正向迭代器类型变量供使用。

        但是看到我们的反向迭代器构造了吗?我们对_cur变量赋初值等于iterator类型的it,但是it是怎么出来的?我们在使用反向迭代器的时候难道不是vv.rbegin();这种方式吗?我们有传递任何的数据吗?更何况还是一个正向迭代器类型的变量。

        此时就需要看到我们的rbegin函数了。

reverse_iterator rbegin()
{
	return reverse_iterator(end());
}
reverse_iterator rend()
{
	return reverse_iterator(begin());
}

        这样看可能不是很清楚,那我换一种方式表示:

reverse_iterator rbegin()
{
    return reverse_iterator(iterator(_head));
}

reverse_iterator rend()
{
    return reverse_iterator(iterator(_head->next));
}

        我们调用rbegin时,会实例化一个反向迭代器类,它通过正向迭代器去构造,正向迭代器通过结点指针构造。

        大家有注意到吗?这种实现方式的rbegin和rend指向我们数据的那个位置?和我们开头的思想相同吗?很明显不同,它的头指向了最后一个数据的下一个位置,它的尾指向了第一个位置,如下图。

         可是这样做的好处是什么?甚至我没有看到好处只看到了我之后*迭代器得到的数据都不对了,第一个数据都取不到了,但事实真的时是这样吗?回到代码中看:

Ref operator*()
{
     iterator temp = _cur;
     return *(--temp);
}

        我们在反向迭代器当中重定义*操作符函数下干了啥?我们创建了一个临时对象,将临时对象--在解引用,那么这样我们不就获取到了正确的数据了吗?所以这种构造思想没有错误。

        但是上面的道理大家都明白,好处在哪里?好了,重点到了!!

        看到上图,我们的begin对应的是rend,end对应的是rbegin,那么我们可以做一件什么事情呢?那就是反向迭代器类的参数传递可以通过正向迭代器的begin()、end()函数构建。也就是下方代码。

reverse_iterator rbegin()
{
    return reverse_iterator(end());
}
reverse_iterator rend()
{
    return reverse_iterator(begin());
}

         这也不是最重要的,最重要的是,我们将这份反向迭代器直接原封不动的放到vector当中,会有什么效果?你一定想不到,我们vector的反向迭代器也实现了!!

        如下:

namespace boqi
{
	template<class iterator, class Ref, class Ptr>
	struct __list_reverse_iterator
	{
		typedef __list_reverse_iterator<iterator, Ref, Ptr> Self;
		iterator _cur;

		__list_reverse_iterator(iterator it)
			:_cur(it)
		{}

		Ref operator*()
		{
			iterator temp = _cur;
			return *(--temp);
		}

		Self& operator++()
		{
			--_cur;
			return *this;
		}

		Self& operator--()
		{
			++_cur;
			return *this;
		}

		bool operator!=(const Self& ss)
		{
			return _cur != ss._cur;
		}
	};

	template<class T>
	class vector
	{
	public:
		//迭代器定义
		typedef T* iterator;
		typedef const T* const_iterator;
		typedef struct __list_reverse_iterator<iterator, T&, T*> reverse_iterator;
		typedef struct __list_reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;

		iterator begin()
		{
			return _start;
		}
		iterator end()
		{
			return _finish;
		}
        reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}
		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}

    private:
		//三个迭代器表示一个开辟空间数组的3个位置
		iterator _start;
		iterator _finish;
		iterator _end_of_storage;
	};
}

        看到,博主甚至连名字都没有更换,再看它是否能用。

测试代码:

void test9()
{
	yf::vector<int> vv;
	vv.push_back(1);
	vv.push_back(2);
	vv.push_back(3);
	vv.push_back(4);
	yf::vector<int>::reverse_iterator rit = vv.rbegin();
	while (rit != vv.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;
}

输出:

         看到了吗?我们的vector的反向迭代器直接就能用了,我们都知道vector和list的底层完全不同,通过大佬的这种方式实现,却将两个完全不同的迭代器完美的联系起来了,并且共用一份代码!而且不只是这两个容器可以用,任何由迭代器的容器都可以使用,因为只要你有迭代器,那一定支持++和--,而且它不关心你的正向迭代器是怎么实现的。对此我只能膜拜,大佬不愧是大佬。

3 完整代码

#pragma once

#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
#include<assert.h>

namespace yf
{
	template<class T>
	struct node
	{
		//结点类在list创建时分配数据
		node(const T& val = T())
			:next(nullptr)
			, prev(nullptr)
			, data(val)
		{}

		//前结点、后结点、T类型数据
		struct node<T>* next;
		struct node<T>* prev;
		T data;
	};

	//迭代器类
	//Ref和Ptr分别是T&,和T*,目的是为了不让代码冗余,const T&,const T*
	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef struct node<T> Node;
		typedef struct __list_iterator<T, Ref, Ptr> self;
		
		//浅拷贝传入过来的结点指针,不需要去开辟新空间
		//因为我们要的就是原本的结点
		struct __list_iterator(Node* node)
			:Pos(node)
		{}

		//*迭代器返回结点内部的数据
		Ref operator*()
		{
			return Pos->data;
		}

		//到下一个结点,而不是结点指针的下一个位置
		self& operator++()
		{
			Pos = Pos->next;
			return *this;
		}

		self operator++(int)
		{
			self temp = *this;
			Pos = Pos->next;
			return temp;
		}

		self& operator--()
		{
			Pos = Pos->prev;
			return *this;
		}

		self operator--(int)
		{
			self temp = *this;
			Pos = Pos->prev;
			return temp;
		}

		//返回节点数据的地址
		Ptr operator->()
		{
			//Pos已经是结点了,但是如果需要访问的数据也是一个结构体
			//那么获取到了它的地址,就能用->去访问了
			return &Pos->data;
		}

		bool operator==(const self& val)
		{
			return Pos == val.Pos;
		}

		bool operator!=(const self& val)
		{
			return Pos != val.Pos;
		}

		Node* Pos;
	};
    

    //反向迭代器
	template<class iterator, class Ref, class Ptr>
	struct __list_reverse_iterator
	{
		typedef __list_reverse_iterator<iterator, Ref, Ptr> Self;
		iterator _cur;

		__list_reverse_iterator(iterator it)
			:_cur(it)
		{}

		Ref operator*()
		{
			iterator temp = _cur;
			return *(--temp);
		}

		Self& operator++()
		{
			--_cur;
			return *this;
		}

		Self& operator--()
		{
			++_cur;
			return *this;
		}

		bool operator!=(const Self& ss)
		{
			return _cur != ss._cur;
		}
	};

	//带头双向循环链表
	template<class T>
	class list
	{
	public:
		typedef struct node<T> Node;
		typedef struct __list_iterator<T, T&, T*> iterator;
		typedef struct __list_iterator<T,const T&, const T*> const_iterator;

		typedef struct __list_reverse_iterator<iterator, T&, T*> reverse_iterator;
		typedef struct __list_reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;

		iterator begin()
		{
			//进入迭代器类当中去,然后传入起始值的数据初始化
			return iterator(_head->next);
		}
		iterator end()
		{
			//_head相当于循环里的迭代器最后一个数据的下一个
			//所以初始化就用_head去初始化
			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(end());
		}
		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}

		const_reverse_iterator rbegin() const
		{
			return const_reverse_iterator(end());
		}
		const_reverse_iterator rend() const
		{
			return const_reverse_iterator(begin());
		}

		//构造时,有的对象是没有头结点的,所以需要帮忙开辟
		void Init_head()
		{
			_head = new Node;
			_head->next = _head;
			_head->prev = _head;
		}

		//无参
		list()
		{
			Init_head();
		}

		//拷贝
		list(const list<T>& val)
		{
			Init_head();
			list<T> temp(val.begin(), val.end());
			std::swap(_head, temp._head);
		}

		//赋值重载
		list<T>& operator=(list<T> val) 
		{
			std::swap(_head, val._head);
			return *this;
		}

		//迭代器区间构造
		template<class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			Init_head();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}


		//插入
		void insert(iterator pos, const T& val)
		{
			Node* cur = pos.Pos;

			Node* NewNode = new Node(val);

			cur->prev->next = NewNode;
			NewNode->prev = cur->prev;
			NewNode->next = cur;
			cur->prev = NewNode;
		}

		//尾插
		void push_back(const T& val)
		{
			iterator it = end();
			insert(it,val);
		}

		//头插
		void push_front(const T& val)
		{
			iterator it = begin();
			insert(it,val);
		}	

		//删除
		void erase(iterator pos)
		{
			assert(pos != end());

			Node* cur = pos.Pos;

			cur->prev->next = cur->next;
			cur->next->prev = cur->prev;

			delete cur;
		}

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

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

		//判空
		bool empty()
		{
			return _head->next == _head;
		}

		//清空除头结点之外的所有结点
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				erase(it++);
			}
		}

		//析构
		~list()
		{
			clear();
			delete _head;
		}

	private:
		Node* _head;
	};
}

        以上就是我对反向迭代器的全部理解,谢谢大家观看。

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

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

相关文章

【js逆向】hook大全

▒ 目录 ▒&#x1f6eb; 导读需求1️⃣ 普通函数2️⃣ 对象方法&#xff08;Class.prototype&#xff09;3️⃣ 对象属性&#xff08;Object.defineProperty&#xff09;4️⃣ Proxy5️⃣ 批量hook示例&#x1f6ec; 文章小结&#x1f4d6; 参考资料&#x1f6eb; 导读 需求 …

【面试题系列】K8S常见面试题

目录 序言 问题 1. 简单说一下k8s集群内外网络如何互通的吧 2.描述一下pod的创建过程 3. 描述一下k8s pod的终止过程 4.Kubernetes 中的自动伸缩有哪些方式&#xff1f; 5.Kubernetes 中的故障检测有哪些方式&#xff1f; 6.Kubernetes 中的资源调度有哪些方式&#xff…

如何优雅的用POI导入Excel文件

在企业级项目开发中&#xff0c;要经常涉及excel文件和程序之间导入导出的业务要求&#xff0c;那么今天来讲一讲excel文件导入的实现。java实现对excel的操作有很多种方式&#xff0c;例如EasyExcel等&#xff0c;今天我们使用的是POI技术实现excel文件的导入。POI技术简介1.P…

全连接神经网络

目录 1.全连接神经网络简介 2.MLP分类模型 2.1 数据准备与探索 2.2 搭建网络并可视化 2.3 使用未预处理的数据训练模型 2.4 使用预处理后的数据进行模型训练 3. MLP回归模型 3.1 数据准备 3.2 搭建回归预测网络 1.全连接神经网络简介 全连接神经网络(Multi-Layer Percep…

基于Vue3和element-plus实现一个完整的登录功能

先看一下最终要实现的效果:登录页面:注册页面:(1)引入element-plus组件库引入组件库的方式有好多种,在这里我就在main.js全局引入了.npm i element-plus -Smain.js中代码:import { createApp } from "vue"; //element-plus import ElementPlus from "element-pl…

双指针 -876. 链表的中间结点-leetcode

开始一个专栏&#xff0c;写自己的博客 双指针&#xff0c;也算是作为自己的笔记吧&#xff01; 双指针从广义上来说&#xff0c;是指用两个变量在线性结构上遍历而解决的问题。狭义上说&#xff0c; 对于数组&#xff0c;指两个变量在数组上相向移动解决的问题&#xff1b;对…

「SAP ABAP」OPEN SQL(四)【FROM语句】

&#x1f482;作者简介&#xff1a; THUNDER王&#xff0c;一名热爱财税和SAP ABAP编程以及热爱分享的博主。目前于江西师范大学会计学专业大二本科在读&#xff0c;同时任汉硕云&#xff08;广东&#xff09;科技有限公司ABAP开发顾问。在学习工作中&#xff0c;我通常使用偏后…

女子举重问题

一、问题的描述 问题及要求 1、搜集各个级别世界女子举重比赛的实际数据。分别建立女子举重比赛总成绩的线性模型、幂函数模型、幂函数改进模型&#xff0c;并最终建立总冠军评选模型。 应用以上模型对最近举行的一届奥运会女子举重比赛总成绩进行排名&#xff0c;并对模型及…

【2023-03-10】JS逆向之美团滑块

提示&#xff1a;文章仅供参考&#xff0c;禁止用于非法途径 前言 目标网站:aHR0cHM6Ly9wYXNzcG9ydC5tZWl0dWFuLmNvbS9hY2NvdW50L3VuaXRpdmVsb2dpbg 页面分析 接口流程 1.https://passport.meituan.com/account/unitivelogin主页接口&#xff1a;需获取下面的参数&#xff0…

力扣刷题---初始链表1

&#x1f388;个人主页:&#x1f388; :✨✨✨初阶牛✨✨✨ &#x1f43b;推荐专栏: &#x1f354;&#x1f35f;&#x1f32f; c语言初阶 &#x1f511;个人信条: &#x1f335;知行合一 &#x1f349;本篇简介:>:讲解初始数据结构链表的三个力扣题 1.移除链表元素. 2.反转…

Visual Studio Code 1.76 发布

欢迎使用 Visual Studio Code 2023 年 2 月版&#xff0c;其中一些亮点包括&#xff1a; 配置文件 - 活动配置文件徽章&#xff0c;通过命令面板快速切换配置文件。辅助功能改进 - 新的音频提示&#xff0c;改进的终端屏幕阅读器模式。可移动的 Explorer 视图- 将资源管理器放…

JavaWeb——Request(请求)和Response(响应)介绍

在写servlet时需要实现5个方法&#xff0c;在一个service方法里面有两个参数request和response。 浏览器向服务器发送请求会发送HTTP的请求数据——字符串&#xff0c;这些字符串会被Tomcat所解析&#xff0c;然后这些请求数据会被放到一个对象(request)里面保存。 相应的Tom…

有图解有案例,我终于把 Condition 的原理讲透彻了

哈喽大家好&#xff0c;我是阿Q&#xff01; 20张图图解ReentrantLock加锁解锁原理文章一发&#xff0c;便引发了大家激烈的讨论&#xff0c;更有小伙伴前来弹窗&#xff1a;平时加解锁都是直接使用Synchronized关键字来实现的&#xff0c;简单好用&#xff0c;为啥还要引用Re…

React面向组件编程(理解与使用+state+props+refs与事件处理)

1 基本理解与使用 函数式组件 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"…

开发板与ubantu文件传送

接下来的所以实验都通过下面这种方式发送APP文件到开发板运行 目录 1、在ubantu配置 ①在虚拟机上添加一个桥接模式的虚拟网卡 ②设定网卡 ③在网卡上配置静态地址 2、开发板设置 ①查看网卡 ②配置网卡静态ip 3、 测试 ①ping ②文件传送 传送报错情况 配置环境&#…

Java Web 实战 14 - 计算机网络之初识计算机网络

初识计算机网络一 . 网络发展史二 . 局域网 VS 广域网2.1 交换机与路由器2.2 集线器三 . 网络通信基础3.1 协议3.1.1 OSI 七层模型3.1.2 TCP / IP 五层模型3.2 交换机和路由器的区别3.3 封装和分用大家好 , 这篇文章给大家分享的是计算机网络的一些基础知识 , 我们会给大家分享…

钉钉,下沉进农田

在这个古老的产业里&#xff0c;数字化没有被放到更高的位置&#xff0c;但难点依旧存在。钉钉恰是基于它足够柔性的产品特性和普惠的服务模式&#xff0c;真正帮助农食产业中的人和企业解决着过去一直没有解决的问题&#xff0c;让这个产业中的人和环节都向数字化潮水迈进了一…

linux目录——文件管理

个人简介&#xff1a;云计算网络运维专业人员&#xff0c;了解运维知识&#xff0c;掌握TCP/IP协议&#xff0c;每天分享网络运维知识与技能。座右铭&#xff1a;海不辞水&#xff0c;故能成其大&#xff1b;山不辞石&#xff0c;故能成其高。个人主页&#xff1a;小李会科技的…

CGAL 点云上采样

目录一、算法原理1、主要函数2、参数解析二、代码实现三、结果展示一、算法原理 该方法对点集进行逐步上采样&#xff0c;同时根据法向量信息来检测边缘点&#xff0c;需要输入点云具有法线信息。在点云空洞填充和稀疏表面重建中具有较好的应用。 1、主要函数 头文件 #inclu…

最强分布式锁工具:Redisson

1 Redisson概述1.1 什么是Redisson&#xff1f;Redisson是一个在Redis的基础上实现的Java驻内存数据网格&#xff08;In-Memory Data Grid&#xff09;。它不仅提供了一系列的分布式的Java常用对象&#xff0c;还提供了许多分布式服务。其中包括(BitSet, Set, Multimap, Sorted…
最新文章