[ C++ ] STL---反向迭代器的模拟实现

目录

前言：

反向迭代器简介

list反向迭代器的模拟实现

 反向迭代器的模拟实现(适配器模式)

SGI版本STL反向迭代器源码

STL库中解引用操作与出口设计

适配list的反向迭代器

适配vector的反向迭代器

前言：

反向迭代器是一种特殊类型的迭代器，它可以逆向遍历容器中的元素，与正向迭代器相比，反向迭代器从容器的末尾开始，向前遍历到容器的起始位置，反向迭代器提供了一种方便的方式来反向访问容器中的元素，特别适用于需要逆序处理数据的场景；

在C++标准库中，反向迭代器通常通过rbegin()和rend()成员函数来获取，一般情况下，rbegin()返回指向容器最后一个元素的迭代器，而rend()返回指向容器起始位置前一个元素的迭器；

反向迭代器简介

#include <iostream>
#include <list>
using namespace std;
int main()
{
	list<int> lt;
	lt.push_back(10);
	lt.push_back(20);
	lt.push_back(30);
	lt.push_back(40);
	lt.push_back(50);

	//正向遍历
	list<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	//反向遍历
	list<int>::reverse_iterator rit = lt.rbegin();
	while (rit != lt.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;
	return 0;
}

运行结果：

list反向迭代器的模拟实现

思考一： 

从行为方式上，反向迭代器与正向迭代器的区别是什么?

正向迭代器与反向迭代器的除了++、- -等接口外毫无区别；

若只实现链表的反向迭代器，如何实现？

链表普通迭代器实现入口：[ C++ ] STL---list的模拟实现-CSDN博客

链表反向迭代器实现步骤：

  1. 拷贝普通迭代器，类名修改为__List_reverse_iterator；
  2. 修改前置++、后置++、前置--、后置-- 接口；
  3. list类中重定义reverse_iterator与const_reverse_iterator；
//list反向迭代器实现代码
template<class T, class Ref, class Ptr>
struct __List_reverse_iterator//修改类名
{
	typedef ListNode<T> Node;
	Node* _node;
	__List_reverse_iterator(Node* node)
		:_node(node)
	{}
	typedef __List_reverse_iterator<T> self;

	//修改++/--接口的指向
	self& operator++()
	{
		_node = _node->_prev;
		return *this;
	}
	//it++
	self operator++(int)
	{
		self tmp(*this);
		_node = _node->_prev;
		return tmp;
	}
	//--it
	self& operator--()
	{
		_node = _node->_next;
		return *this;
	}
	//it--
	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;
	}
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
};

template<class T>
class list
{
	typedef ListNode<T> Node;
public:
    //list类中重定义
	typedef __List_reverse_iterator<T, T&, T*> reverse_iterator;//重命名反向迭代器
	typedef __List_reverse_iterator<T, const T&, const T*> const_reverse_iterator;//重命名const反向迭代器

	//......

private:
	Node* _head;
};

 反向迭代器的模拟实现(适配器模式)

上述实现list反向迭代器的方式会在同一份文件中，存在普通迭代器与反向迭代器两个类并且两个类中仅有个别接口略有差异，代码冗余，导致可读性变差，更好的实现方案是什么?

解决方案：

vector/list/二叉树等容器均要面临反向迭代器的实现问题，如此便采用适配器模式，即链表的正向迭代器适配（改造）出链表的反向迭代器，vector的正向迭代器适配（改造）出vector的反向迭代器；

SGI版本STL反向迭代器源码

//stl_iterator.h文件
template <class _Iterator>
class reverse_iterator 
{
protected:
  _Iterator current;
public:
  typedef typename iterator_traits<_Iterator>::iterator_category
          iterator_category;
  typedef typename iterator_traits<_Iterator>::value_type
          value_type;
  typedef typename iterator_traits<_Iterator>::difference_type
          difference_type;
  typedef typename iterator_traits<_Iterator>::pointer
          pointer;
  typedef typename iterator_traits<_Iterator>::reference
          reference;

  typedef _Iterator iterator_type;
  typedef reverse_iterator<_Iterator> _Self;

public:
  reverse_iterator() {}
  explicit reverse_iterator(iterator_type __x) : current(__x) {}

  reverse_iterator(const _Self& __x) : current(__x.current) {}
#ifdef __STL_MEMBER_TEMPLATES
  template <class _Iter>
  reverse_iterator(const reverse_iterator<_Iter>& __x)
    : current(__x.base()) {}
#endif /* __STL_MEMBER_TEMPLATES */
    
  iterator_type base() const { return current; }
  reference operator*() const {
    _Iterator __tmp = current;
    return *--__tmp;
  }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
  pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */

  _Self& operator++() {
    --current;
    return *this;
  }
  _Self operator++(int) {
    _Self __tmp = *this;
    --current;
    return __tmp;
  }
  _Self& operator--() {
    ++current;
    return *this;
  }
  _Self operator--(int) {
    _Self __tmp = *this;
    ++current;
    return __tmp;
  }

  _Self operator+(difference_type __n) const {
    return _Self(current - __n);
  }
  _Self& operator+=(difference_type __n) {
    current -= __n;
    return *this;
  }
  _Self operator-(difference_type __n) const {
    return _Self(current + __n);
  }
  _Self& operator-=(difference_type __n) {
    current += __n;
    return *this;
  }
  reference operator[](difference_type __n) const { return *(*this + __n); }  
}; 
//stl_list.h文件
reverse_iterator rbegin() 
{ 
return reverse_iterator(end()); 
}
const_reverse_iterator rbegin() const 
{ 
return const_reverse_iterator(end()); 
}

reverse_iterator rend()
{ 
return reverse_iterator(begin()); 
}
const_reverse_iterator rend() const
{ 
return const_reverse_iterator(begin()); 
}

STL库中解引用操作与出口设计

STL库中设计了一种对称结构，正向迭代器的开始位置为反向迭代器的结束位置，反向迭代器的开始位置即正向迭代器的结束位置；

适配list的反向迭代器

实现思路：

将正向迭代器作为模板参数传递给反向迭代器的成员变量cur，如此反向迭代器就可以自动匹配容器，反向迭代器就可以统一实现复用了：

//ReverseIterator.h文件
//第一个模版参数为正向迭代器,利用正向迭代器改造反向迭代器;
//第二个模版参数Ref定义反向迭代器的数据类型，数据类型分为const类型/非const类型;
//第三个模版参数Ptr定义自定义类型指针所指向的数据的的读写属性;
template<class Iterator,class Ref,class Ptr>
struct ReverseIterator
{
	//成员变量cur,cur为正向迭代器类所定义的对象
	Iterator cur;
	//ReverseIterator<Iterator,Ref,Ptr> operator++()
	typedef ReverseIterator<Iterator, Ref, Ptr> Self;
	Self& operator++()
	{
		--cur;//调用cur对象所属类的operator--()函数
		return *this;
	}
	Self operator++(int)
	{
		Self tmp(cur);
		--cur;
		return tmp;
	}
	Self& operator--()
	{
		++cur;//调用cur对象所属类的operator++()函数
		return *this;
	}
	Self operator--(int)
	{
		Self tmp(cur);
		++cur;
		return tmp;
	}
	// !=/== 本质比较正向迭代器也即结点的指针
	bool operator!=(const Self& s)
	{
		return cur != s.cur;
	}
	bool operator==(const Self& s)
	{
		return cur == s.cur;
	}
	//构造函数(正向迭代器构造反向迭代器)
	ReverseIterator(Iterator it)
		:cur(it)
	{}
	Ref operator*()
	{
		Iterator tmp = cur;
		--tmp;
		return *tmp;
	}
	//需要对象指针即对象地址，所以先解引用再取&
	Ptr operator->()
	{
		return &(operator*());
	}
};
list类中统一名称并且需要提供出口； 
//list.h文件代码节选
template<class T>
class list
{
typedef ListNode<T> Node;
public:
typedef __List_iterator<T, T&, T*> iterator;
typedef __List_iterator<T, const T&, const T*> const_iterator;

//list类中统一名称
typedef  ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef  ReverseIterator<iterator, const T&, const T*> const_reverse_iterator;

//搭配出口,list类中实现rbegin()、rend()
reverse_iterator rbegin()
{
	return reverse_iterator(end());
}
reverse_iterator rend()
{
	return reverse_iterator(begin());
}
//......
}

适配vector的反向迭代器

//vector.h文件代码节选
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;

//vector中统一名称
typedef  ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef  ReverseIterator<iterator, const T&, const T*> const_reverse_iterator;


//搭配出口,vector中实现rbegin()、rend()
reverse_iterator rbegin()
{
	return reverse_iterator(end());
}
reverse_iterator rend()
{
	return reverse_iterator(begin());
}
//......
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};

欢迎大家批评指正，博主会持续输出优质内容，谢谢大家观看，码字画图不易，希望大家给个一键三连支持~ 你的支持是我创作的不竭动力~

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

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

相关文章

微信小程序 - picker-viewer实现省市选择器

微信小程序 - picker-viewer实现省市选择器

简介 本文会基于微信小程序picker viewer组件实现省市选择器的功能。 实现效果 实现代码 布局 <picker-view value"{{value}}" bindchange"bindChange" indicator-style"height: 50px;" style"width: 100%; height: 300px;" &…
阅读更多...
车道线检测论文:《Ultra Fast Structure-aware Deep Lane Detection》

车道线检测论文:《Ultra Fast Structure-aware Deep Lane Detection》

该论文标题为《Ultra Fast Structure-aware Deep Lane Detection》&#xff0c;作者是浙江大学计算机科学与技术学院的Zequn Qin、Huanyu Wang和Xi Li。论文提出了一种新颖的、简单而有效的车道检测方法&#xff0c;旨在解决具有挑战性场景下的车道检测问题&#xff0c;并实现极…
阅读更多...
java数据结构与算法刷题-----LeetCode451. 根据字符出现频率排序

java数据结构与算法刷题-----LeetCode451. 根据字符出现频率排序

java数据结构与算法刷题目录&#xff08;剑指Offer、LeetCode、ACM&#xff09;-----主目录-----持续更新(进不去说明我没写完)&#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 1. hash统计出现次数后排序2. 桶排序 1. hash统计出现次数后排序…
阅读更多...
基于Springboot的牙科就诊管理系统（有报告）。Javaee项目，springboot项目。

基于Springboot的牙科就诊管理系统（有报告）。Javaee项目，springboot项目。

演示视频&#xff1a; 基于Springboot的牙科就诊管理系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍: 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&#xff0c…
阅读更多...
＜Linux＞ 线程池

＜Linux＞ 线程池

目录 前言&#xff1a; 一、线程池概念 &#xff08;一&#xff09;池化技术 &#xff08;二&#xff09;优点 &#xff08;三&#xff09;应用场景 二、线程池的实现 &#xff08;一&#xff09;线程池_V1&#xff08;朴素版&#xff09; &#xff08;二&#xff09;线…
阅读更多...
GaussDB WDR分析之集群报告篇

GaussDB WDR分析之集群报告篇

AWR报告目前已经成为Oracle DBA分析问题&#xff0c;定位故障最为重要的报告&#xff0c;阅读与分析AWR报告的技能也是Oracle DBA必备的技能。国产数据库为了提高运维便捷性&#xff0c;都在做类似Oracle AWR报告的模仿&#xff0c;只不过由于指标体系不够完善&#xff0c;因此…
阅读更多...
列强，瓜分台积电！

列强，瓜分台积电！

特朗普曾说&#xff0c;台积电是他能想到的&#xff0c;唯一一家被迫停产会导致全球经济萧条的企业。 如今&#xff0c;美国、日本、欧洲争相发出巨额补贴&#xff0c;“邀请”台积电到当地设厂&#xff0c;对这家唯一重要的企业发起了攻势。 2022年12月6日&#xff0c;美国…
阅读更多...
【LeetCode: 120. 三角形最小路径和 + 动态规划】

【LeetCode: 120. 三角形最小路径和 + 动态规划】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…
阅读更多...
WEB DDOS的安全策略

WEB DDOS的安全策略

近年来网络攻击的数量和频率急剧上升&#xff0c;针对Web应用程序的DDoS海啸攻击就是其中增长非常迅速的一个种类。过去常见的HTTP/S洪水攻击正在大范围的转变为更难对付的Web DDoS海啸攻击&#xff0c;网络安全空间攻防对抗越演越烈&#xff0c;企业用户面临更加严峻的网络安全…
阅读更多...
思通舆情 是一款开源免费的舆情系统 介绍

思通舆情 是一款开源免费的舆情系统 介绍

思通舆情 是一款开源免费的舆情系统。 支持本地化部署&#xff0c;支持在线体验。 支持对海量舆情数据分析和挖掘。 无论你是使用者还是共同完善的开发者&#xff0c;欢迎 pull request 或者 留言对我们提出建议。 您的支持和参与就是我们坚持开源的动力&#xff01;请 sta…
阅读更多...
[java基础揉碎]理解main方法语法

[java基础揉碎]理解main方法语法

目录 深入理解main方法 解释main方法的形式: main方法的特别说明: main方法的动态传值: 深入理解main方法 解释main方法的形式: public static void main(String[] args){} 1.mian方法是虚拟机调用 2. java虚拟机需要调用类的main()方法&#xff0c;所以该方法的访问权…
阅读更多...
每日一题 --- 移除链表元素[力扣][Go]

每日一题 --- 移除链表元素[力扣][Go]

移除链表元素 题目&#xff1a;203. 移除链表元素 给你一个链表的头节点 head 和一个整数 val &#xff0c;请你删除链表中所有满足 Node.val val 的节点&#xff0c;并返回 新的头节点 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,6,3,4,5,6], val 6 输出&#xf…
阅读更多...
【源码】I.MX6ULL移植OpenCV

【源码】I.MX6ULL移植OpenCV

编译完成的源码&#xff1a; git clone https://gitee.com/wangyoujie11/atkboard_-linux_-driver.git 1.下载源码放在自己的opecv源码目录下 2.QTOpenCV工程代码放置的位置 3.更改.pro工程文件的opencv地址 4.使用命令行编译 前提是自己环境中已经配置好arm-qt的交叉编译…
阅读更多...
【Redis知识点总结】（六）——主从同步、哨兵模式、集群

【Redis知识点总结】（六）——主从同步、哨兵模式、集群

Redis知识点总结&#xff08;六&#xff09;——主从同步、哨兵模式、集群 主从同步哨兵集群 主从同步 redis的主从同步&#xff0c;一般是一个主节点&#xff0c;加上多个从节点。只有主节点可以接收写命令&#xff0c;主节点接收到的写命令&#xff0c;会同步给从节点&#…
阅读更多...
Github 2024-03-24php开源项目日报 Top10

Github 2024-03-24php开源项目日报 Top10

根据Github Trendings的统计，今日(2024-03-24统计)共有10个项目上榜。根据开发语言中项目的数量，汇总情况如下： 开发语言项目数量PHP项目10JavaScript项目1Nextcloud服务器：安全的数据之家 创建周期：2796 天开发语言：PHP, JavaScript协议类型：GNU Affero General Public…
阅读更多...
【数据结构】考研真题攻克与重点知识点剖析 - 第 1 篇：绪论

【数据结构】考研真题攻克与重点知识点剖析 - 第 1 篇：绪论

前言 本文基础知识部分来自于b站&#xff1a;分享笔记的好人儿的思维导图与王道考研课程&#xff0c;感谢大佬的开源精神&#xff0c;习题来自老师划的重点以及考研真题。此前我尝试了完全使用Python或是结合大语言模型对考研真题进行数据清洗与可视化分析&#xff0c;本人技术…
阅读更多...
IDDR、ODDR、IDEALY2和ODELAY2详解

IDDR、ODDR、IDEALY2和ODELAY2详解

文章目录 前言一、IDDR原语二、ODDR原语三、IDELAYCTRL原语四、IDELAY原语4.1、参数配置 &#xff1a;4.2、端口说明 &#xff1a;4.3、延时控制时序图 五、ODELAY原语 前言 本文参考XILINX手册UG471 一、IDDR原语 参考xilinx手册UG471 IDDR #(.DDR_CLK_EDGE ("SAME_…
阅读更多...
【C++11】：统一的列表初始化|声明|STL变化

【C++11】：统一的列表初始化|声明|STL变化

​ &#x1f3ac;慕斯主页&#xff1a;修仙—别有洞天 ♈️今日夜电波&#xff1a;マイノリティ脈絡—ずっと真夜中でいいのに。 0:24━━━━━━️&#x1f49f;──────── 4:02 &#x1f504; …
阅读更多...
已知屏幕分辨率和屏幕尺寸，JavaScript如何计算屏幕PPI像素密度

已知屏幕分辨率和屏幕尺寸，JavaScript如何计算屏幕PPI像素密度

返回主目录：OpenLayers扩展组件系列汇总目录：常用OpenLayers地图扩展组件ol-ext、ol-cesium、ol-layerswitcher、ol-geocoder和ol-wind等扩展库 前言 本章作为补充章，用于讲解使用ol-ext组件的前置知识。 要想知道 PPI 是什么，我们需要先理解“像素”这个概念，那么什么是…
阅读更多...
【C++算法】洛谷P1102：A-B数对，思路，lower_bound，upper_bound，二分答案，代码详解

【C++算法】洛谷P1102：A-B数对，思路，lower_bound，upper_bound，二分答案，代码详解

文章目录 1&#xff09;解题思路2&#xff09;三种情况3&#xff09;代码 题目链接&#xff1a;P1102 A-B 数对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 1&#xff09;解题思路 这道题要求我们在序列中找到 A − B C A-BC A−BC 的数对的个数&#xff0c;下标不同的数…
阅读更多...
最新文章

Copyright @ 2022~2023

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