19 反向迭代器

反向迭代器和正向迭代器相反，比如一个数组内容是1,2,3,4,5。正向迭代器就是按顺序输出，反向迭代器是5,4,3,2,1，顺序倒着。想要第一个输出5，需要反向迭代器rbegin在5的位置,判断输出完的条件,rend在头节点的位置就行，只需要将指针相加重载为取前一个数据，这就需要和正向迭代器一样封装一个反向迭代器的类

先用链表的迭代器做示范
在这里插入图片描述

template <class T, class Ref, class Ptr>
struct __list_reverse_iterator
{
	typedef __list_node<T> node;
	typedef __list_reverse_iterator<T, Ref, Ptr> self;

	__list_reverse_iterator(node* it_node)
	{
		node_iterator = it_node;
	}

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

	Ptr operator->()
	{
		//return &node_iterator->_data;
		return &(operator*());
	}

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

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

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

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

	bool operator!=(const self& x)
	{
		return node_iterator != x.node_iterator;
	}

	bool operator==(const self& x)
	{
		return node_iterator == x.node_iterator;
	}

	node* node_iterator;
};

reverse_iterator rbegin()
{
	reverse_iterator tmp(_head._prev);
	return tmp;
}

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

和正向迭代器唯一不一样的地方就是++返回的是节点前一个位置,–返回后一个位置
rbegin返回最后一个数据的位置,rend一样返回头节点

看看标准库中怎么实现的
在这里插入图片描述在这里插入图片描述

库里用了迭代器萃取，意思是总结出了反向迭代器的特性，以至于这个类的迭代器可以适用于其他数据结构。对于链表我们可以重载它的++，因为将指针封装成了类，而vector的迭代器就是原生指针的重命名，当然，也可以封装为类就可以实现反向迭代器，不过过于麻烦。用这样一个反向迭代器的类，可以实现其他所有数据的反向迭代器，只需要传入对应数据类型的正向迭代器就能构造反向迭代器，这是如何实现的

在这里插入图片描述

它的取内容实际上是取的正向迭代器–后的内容，这是为什么

在这里插入图片描述

反向迭代器的rbegin用正向的rend构造，说明刚好两个迭代器的位置是相反的
在这里插入图片描述

这样反向迭代器取当前内容就需要取前一个节点的值，rbegin在2的位置是，输出的是值1。这样迭代器的构造也只需要传入正向迭代器的begin就行，对称了

迭代器萃取比较麻烦，我们先用加两个模板参数的方法实现，和正向迭代器类似，不同的是不需要传入数据类型，需要传入正向迭代器

template <class Iterator, class Ref, class Ptr>
struct __list_reverse_iterator
{
	typedef __list_reverse_iterator<Iterator, Ref, Ptr> self;

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

	Ref operator*()
	{
		Iterator tmp = _cur;
		tmp--;
		return *tmp;
	}

	Ptr operator->()
	{
		return &(operator*());
	}

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

	self operator++(int)
	{
		self tmp(*this);
		_cur--;
		return tmp;;
	}

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

	self operator--(int)
	{
		self tmp(_cur.node_iterator._next);
		_cur++;
		return tmp;
	}

	bool operator!=(const self& x)
	{
		return _cur != x._cur;
	}

	bool operator==(const self& x)
	{
		return _cur == x._cur;
	}

	Iterator _cur;
};

typedef  __list_reverse_iterator<iterator, T&, T*> reverse_iterator;
reverse_iterator rbegin()
{
	reverse_iterator tmp(end());
	return tmp;
}

reverse_iterator rend()
{
	reverse_iterator tmp(begin());
	return tmp;
}

这里*取正向迭代器–后的内容，会自动调用正向迭代器的重载函数。++就–，和正向相反，比较的时候本质是指针的比较

将这个类放到vector同样也可以使用，代码不需要改变，这样就做到了多用

list全代码

#pragma once
#include <assert.h>

namespace mylist
{
	template <typename T>
	struct __list_node
	{
		__list_node(const T& x = T())
			: _prev(nullptr)
			, _next(nullptr)
			, _data(x)
		{}

		__list_node<T>* _prev;
		__list_node<T>* _next;
		T _data;
	};

	//迭代器
	template <class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef __list_node<T> node;
		typedef __list_iterator<T, Ref, Ptr> self;

		__list_iterator(node* it_node)
		{
			node_iterator = it_node;
		}

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

		Ptr operator->()
		{
			//return &node_iterator->_data;
			return &(operator*());
		}

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

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

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

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

		bool operator!=(const self& x)
		{
			return node_iterator != x.node_iterator;
		}

		bool operator==(const self& x)
		{
			return node_iterator == x.node_iterator;
		}

		node* node_iterator;
	};

	//反向迭代器
	//template <class T, class Ref, class Ptr>
	//struct __list_reverse_iterator
	//{
	//	typedef __list_node<T> node;
	//	typedef __list_reverse_iterator<T, Ref, Ptr> self;

	//	__list_reverse_iterator(node* it_node)
	//	{
	//		node_iterator = it_node;
	//	}

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

	//	Ptr operator->()
	//	{
	//		//return &node_iterator->_data;
	//		return &(operator*());
	//	}

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

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

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

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

	//	bool operator!=(const self& x)
	//	{
	//		return node_iterator != x.node_iterator;
	//	}

	//	bool operator==(const self& x)
	//	{
	//		return node_iterator == x.node_iterator;
	//	}

	//	node* node_iterator;
	//};

	//反向迭代器库写法
	template <class Iterator, class Ref, class Ptr>
	struct __list_reverse_iterator
	{
		typedef __list_reverse_iterator<Iterator, Ref, Ptr> self;

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

		Ref operator*()
		{
			Iterator tmp = _cur;
			tmp--;
			return *tmp;
		}

		Ptr operator->()
		{
			return &(operator*());
		}

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

		self operator++(int)
		{
			self tmp(*this);
			_cur--;
			return tmp;;
		}

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

		self operator--(int)
		{
			self tmp(_cur.node_iterator._next);
			_cur++;
			return tmp;;
		}

		bool operator!=(const self& x)
		{
			return _cur != x._cur;
		}

		bool operator==(const self& x)
		{
			return _cur == x._cur;
		}

		Iterator _cur;
	};

	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;

		typedef  __list_reverse_iterator<iterator, T&, T*> reverse_iterator;
		

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

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

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

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


		reverse_iterator rbegin()
		{
			reverse_iterator tmp(end());
			return tmp;
		}

		reverse_iterator rend()
		{
			reverse_iterator tmp(begin());
			return tmp;
		}

		
		//构造
		void empyt_init()
		{
			_head = new node;
			_head->_prev = _head->_next = _head;
		}

		list()
		{
			empyt_init();
		}

		template <class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			empyt_init();

			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}

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

		list(const list<T>& x)
		{
			empyt_init();

			list<T> tmp(x.begin(), x.end());
			swap(tmp);
			/*const_iterator it = x.begin();
			while (it != x.end())
			{
				push_back(*it);
				it++;
			}*/

			/*for (auto e : x)
			{
				push_back(e);
			}*/
		}

		list<T>& operator=(list<T> x)
		{
			swap(x);

			return *this;
		}

		//add
		void push_front(const T& x)
		{
			Insert(begin(), x);
		}

		void push_back(const T& x)
		{
			node* new_node = new node(x);

			_head->_prev->_next = new_node;
			new_node->_prev = _head->_prev;

			_head->_prev = new_node;
			new_node->_next = _head;
		}

		void Insert(iterator pos, const T& x)
		{
			node* new_node = new node(x);
			//记录前后节点
			node* pre = pos.node_iterator->_prev;
			node* cur = pos.node_iterator;
			//连接
			pre->_next = new_node;
			new_node->_prev = pre;

			new_node->_next = cur;
			cur->_prev = new_node;

		}

		//de
		void pop_front()
		{
			Erase(begin());
		}

		void pop_back()
		{
			Erase(--end());
		}
		iterator Erase(iterator pos)
		{
			//头节点不能删
			assert(pos != end());

			node* prev = pos.node_iterator->_prev;
			node* next = pos.node_iterator->_next;

			prev->_next = next;
			next->_prev = prev;
			delete pos.node_iterator;

			return iterator(next);
		}

		//析构
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				Erase(it++);
			}
		}

		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}


	private:
		node* _head;
	};

}

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

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

相关文章

【go从入门到精通】select条件控制

【go从入门到精通】select条件控制

作者简介&#xff1a; 高科&#xff0c;先后在 IBM PlatformComputing从事网格计算&#xff0c;淘米网&#xff0c;网易从事游戏服务器开发&#xff0c;拥有丰富的C&#xff0c;go等语言开发经验&#xff0c;mysql&#xff0c;mongo&#xff0c;redis等数据库&#xff0c;设计模…
阅读更多...
【八股】ThreadLocal原理

【八股】ThreadLocal原理

1. Thread.java 我们首先打开Thread.java源码&#xff0c;看到里面有一个ThreadLocalMap类型的变量threadLocals 2. ThreadLocal.java -> getMap(thread t) 然后ThreadLocal.java里面有一个getMap函数&#xff0c;传入的是线程&#xff0c;返回的是线程里面的ThreadLoca…
阅读更多...
mysql无法看到3306端口监听

mysql无法看到3306端口监听

参考:https://blog.csdn.net/shumeigang/article/details/103902459 mysql> show global variables like ‘port’; 是0 原因是我的my.cnf有话&#xff1a; skip-network 或 注释掉&#xff0c;然后重新启动下数据库&#xff0c;运行netstat -an|grep 3306 就可以看到了
阅读更多...
学习笔记Day13：Linux进阶

学习笔记Day13：Linux进阶

Linux进阶 Vim——Linux自带的文本编辑器 功能强大 命令模式 使用 vim <file>进入后的默认模式可以上下左右移动光标 方向键/hjkl快速到所在行的开头^/末尾$向下移动30行30j&#xff08;上左右同&#xff09;上下翻页Ctrlf向上&#xff0c;Ctrlb向下翻页快速回到文件第…
阅读更多...
docker 进入容器内部命令

docker 进入容器内部命令

docker容器运行了&#xff0c;怎么进入容器内部查看内部的文件情况呢&#xff1f; 答&#xff1a;可以通过docker exec 的命令查看。 docker exec --help 可以查看命令介绍 &#xff1a; docker exec -it XXX /bin/bash XX为容器ID 进入容器内部 /bin/bash是需要添加的 不…
阅读更多...
MT管理器 使用手册

MT管理器 使用手册

MT管理器 论坛&#xff1a;https://bbs.binmt.cc/ 使用技巧系列教程&#xff1a;https://www.52pojie.cn/thread-1259872-1-1.html MT管理器 使用手册 &#xff1a;https://mt2.cn/guide/&#xff1a;https://www.bookstack.cn/read/mt-manual/80b8084f6be128c0.md&#xff…
阅读更多...
vue学习日记15：普通组件的注册使用

vue学习日记15：普通组件的注册使用

一、概念 &#xff08;1&#xff09;局部注册 &#xff08;2&#xff09;全局注册 二、实践 1.局部注册 &#xff08;1&#xff09;代码 步骤&#xff1a;创建组件 导入 注册 使用 src文件夹下面仅仅保留这两个即可 其他两个文件夹可以删除 在src下面建立components文件夹…
阅读更多...
刷题DAY30 | LeetCode 332-重新安排行程 51-N皇后 37-解数独

刷题DAY30 | LeetCode 332-重新安排行程 51-N皇后 37-解数独

332 重新安排行程&#xff08;hard&#xff09; 给你一份航线列表 tickets &#xff0c;其中 tickets[i] [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。 所有这些机票都属于一个从 JFK&#xff08;肯尼迪国际机场&#xff09;出发的先生&…
阅读更多...
Qt 不同数据类型转换

Qt 不同数据类型转换

一.不同类型数据转换示例&#xff1a; #include <QGuiApplication> #include <QQmlApplicationEngine> #include <QJsonDocument> #include <QJsonObject> #include <QDebug>int main(int argc, char *argv[]) {QCoreApplication::setAttribute…
阅读更多...
【C语言】linux内核pci_enable_device函数和_PCI_NOP宏

【C语言】linux内核pci_enable_device函数和_PCI_NOP宏

pci_enable_device 一、注释 static int pci_enable_device_flags(struct pci_dev *dev, unsigned long flags) {struct pci_dev *bridge;int err;int i, bars 0;/** 此时电源状态可能是未知的&#xff0c;可能是由于新启动或者设备移除调用。* 因此获取当前的电源状态&…
阅读更多...
【Flask】Flask项目结构初识

【Flask】Flask项目结构初识

1.前提准备 Python版本 # python 3.8.0 # 查看Python版本 python --version 安装第三方 Flask pip install flask # 如果安装失败&#xff0c;可以使用 -i&#xff0c;指定使用国内镜像源 # 清华镜像源&#xff1a;https://pypi.tuna.tsinghua.edu.cn/simple/ 检查 Flask 是…
阅读更多...
网络: 网络层

网络: 网络层

IP地址: 分为网络号和主机号. 用来标识主机 IP协议 IP协议报文 4位版本号(version): 指定IP协议的版本, 对于IPv4来说, 就是4.4位头部长度(header length): IP头部的长度是多少个32bit, 也就是 length * 4 的字节数. 4bit表示最大的数字是15, 因此IP头部最大长度是60字节. 8…
阅读更多...
传输介质介绍，数据链路层，MAC地址的构成和作用

传输介质介绍，数据链路层，MAC地址的构成和作用

简单网络 1.网卡 2.物理介质 3.协议栈 双绞线&#xff1a; UTP 非屏蔽双绞线 屏蔽式双绞线 水晶头 串口电缆&#xff1a;连接运营商 广域网一个用户接入到广域网&#xff0c;早期来讲&#xff0c;光纤 物理层&#xff1a;本质是通信&#xff0c;数据传输&#xff0c;介质产…
阅读更多...
数据结构02：线性表 链表习题01[C++]

数据结构02：线性表 链表习题01[C++]

考研笔记整理~&#x1f95d;&#x1f95d; 之前的博文链接在此&#xff1a;数据结构02&#xff1a;线性表[顺序表链表]_线性链表-CSDN博客~&#x1f95d;&#x1f95d; 本篇作为链表的代码补充&#xff0c;供小伙伴们参考~&#x1f95d;&#x1f95d; 第1版&#xff1a;王道…
阅读更多...
3.21小题总结

3.21小题总结

第一题&#xff1a;生日蛋糕 题解&#xff1a;这题是蛋糕结构是一层一层的&#xff0c;估计很多人很快就能想到是dfs&#xff0c;但是这题的难想的点在于 你每层的状态该怎么去确定&#xff0c;你怎么来确定每层的半径和高度是多少&#xff0c;一开始我也不知很理解&#xff0…
阅读更多...
计算结构体的大小（结构体的内存对齐）

计算结构体的大小（结构体的内存对齐）

一&#xff1a;问题 问题所在&#xff1a;两个结构体应该都是6个字节大小&#xff0c;为什么一个12&#xff0c;一个6&#xff1f;&#xff1f;&#xff1f; 二&#xff1a;如何正确的计算结构体大小&#xff1f; 首先得掌握结构体的对齐规则&#xff1a; 第一&#xff1a; 第一…
阅读更多...
Leetcode 994. 腐烂的橘子

Leetcode 994. 腐烂的橘子

心路历程&#xff1a; 一开始以为和刚做过的岛屿问题很像&#xff0c;只不过是把岛屿问题换成BFS去做&#xff0c;然后再加上一些计数的规则。结果做完后发现只能通过一半左右的测试用例&#xff0c;发现有一个逻辑错误在于&#xff0c;当腐烂的橘子位于两端时&#xff0c;可以…
阅读更多...
约数（因数）问题（ACwing算法笔记）

约数（因数）问题（ACwing算法笔记）

869.试除法求约数 注意点&#xff1a; 1.试除法就是让i遍历的最大值到a/i。 2.约数成对存在&#xff0c;只遍历前一部分即可。 代码&#xff1a; #include<iostream> #include<queue> #include<algorithm> #include<cstring> #include<cmath>…
阅读更多...
Go语言学习04~05 函数和面向对象编程

Go语言学习04~05 函数和面向对象编程

Go语言学习04-函数 函数是一等公民 <font color"Blue">与其他主要编程语言的差异</font> 可以有多个返回值所有参数都是值传递: slice, map, channel 会有传引用的错觉函数可以作为变量的值函数可以作为参数和返回值 学习函数式编程 可变参数 func s…
阅读更多...
刷题28-30（力扣0322/0078/0221）

刷题28-30（力扣0322/0078/0221）

0322. 零钱兑换 题目&#xff1a; 给你一个整数数组 coins &#xff0c;表示不同面额的硬币&#xff1b;以及一个整数 amount &#xff0c;表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额&#xff0c;返回 -1 。你可以…
阅读更多...
最新文章

Copyright @ 2022~2023