当前位置: 首页 > news >正文

【C++】STL反向迭代器模拟实现,迭代器适配器,迭代器类型简单介绍

本篇主要讲反向迭代器的模拟实现。能够加深各位对泛型的理解。string中已经提到过反向迭代器;迭代器,可以在不暴露底层实现细节的情况下,提供统一的方式去访问容器。那么其屏蔽了底层实现,体现除了C++的封装的价值。

前面两篇栈和队列与优先级队列,这三个都是容器适配器,意思就是传什么容器,就能够用什么容器来实现其函数接口。那么这一篇讲的是反向迭代器,其也是适配器,但是不是容器适配器,而是迭代器适配器,对照着上面容器适配器的话来说,就是当我们传入什么容器的正向迭代器,就生成对应的容器的反向迭代器。

基本演示

反向迭代器和正向迭代器差别不大。我们先用vector来演示一下正向和反向迭代器:

在这里插入图片描述
在这里插入图片描述

模拟实现的大致思路

前面在list模拟实现的最后也说到了,要模拟实现反向迭代器,需要在栈和队列这块学了适配器才能真正领悟到其精髓,不然吃不透。那么现在适配器已经学了,那现在可以说一说反向迭代器了。

如果想要实现一个反向迭代器,我当时是这样想的,对于list而言,迭代器是其结点的地址,那么我可以在各个反向迭代器的接口中复用一下list迭代器的正向接口。

在这里插入图片描述

那么如果是这样写的话,我们就可以用这样的思路来搞一搞。但是库中的思路却是这样的:

  1. list的反向迭代器搞出了,vector的反向迭代器怎么搞?
  2. 如何复用正向迭代器?
  3. 是否可以搞出来迭代器适配器?

那么我们就来根据库中的思路搞一搞。首先就是适配器的问题,就是第一点和第三点。当我们传入什么容器的正向迭代器,就生成对应的容器的反向迭代器。那么就要搞一个模板参数Iterator,这个模板参数用来接收传入的迭代器。

然后就是复用的问题。我们就复用传入的正向迭代器,来实现我们的反向迭代器。接下来就可以搭出框架。

迭代器适配器基本框架

在这里插入图片描述

上面就复用了传入的迭代器,生成一个__reverse_iterator的成员变量_cur,但是其本质还是iterator的。这就是复用。

那么构造函数我们就要用一个Iterator的变量来给_cur赋值:

在这里插入图片描述

然后我们再复用Iterator的++、–、*、->等函数来实现反向的迭代器。在这之前我们可以先把我们的当前类重命名一下,后期写起来方便些。

在这里插入图片描述

这就是用正向的来实现反向的,不是传存储的数据类型T,而是传正向的迭代器。

因为我们定义对象的时候是直接用容器后面跟着<数据类型>,比如说list就是list,数据类型T在这里就定好了。所以其反向的迭代器就是list::reverse_iterator,并不是在迭代器的后面定类型的。而这里用迭代器定义对象的时候,也不用在reverse_iterator后面加上,因为我们定义list的时候是先在list类内typedef正向的迭代器的,正向迭代器的模板参数就是<T, T&, T*>,只要前面T定好了,正向的迭代器就搞好了,之后才轮到我们现在写的反向迭代器的,而反向迭代器模板参数直接穿的是正向迭代器Iterator,所以说只要vector类中模板参数T定好了,那么后面的所有类型就都定好了。是不需要我们手动再传任何的模板参数的。

接下来就复用一下正向迭代器的几个函数接口。来实现一下反向迭代器的++、–、*、->等接口。

前置++、–

反向迭代器和正向迭代器是相反的遍历顺序,那么就可以用正向的++来实现反向的–,用正向的–来实现反向的++。

在这里插入图片描述

*重载

*:就是解引用,返回的值能修改,那么返回引用即可,但是我们这里模板参数没有传数据类型T,不知道怎么搞定这个返回值。那么有两种做法,一个是萃取,非常麻烦,。二个就是再写下模板参数即可。那我们当然选第二个了,更轻松一点,但是后面还有->重载,我们加上两个模板参数,一个引用,一个指针。

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

->重载

在这里插入图片描述
其实不用往下写了。因为上面的模拟实现和库中的是不一样的。(因为我们从开头迭代器图解那里就和库中的不一样)。

我们来看一看库中的*和->重载:

在这里插入图片描述

可以看到,*重载返回的是cur - 1。再来看一下list库中的rbegin和rend:

在这里插入图片描述

我们发现rbegin就是end,rend就是begin。对应到图解中就是这样的:

在这里插入图片描述

而我们画的图解是这样的:

在这里插入图片描述

我们就可以把我们的 * 和->改一改。其实改 * 就好。

在这里插入图片描述

由于我的list模拟里没有实现减法重载,但实现–了,就凑合一下,也能用。

然后再实现以下 !=反向的迭代器就能用了。

在这里插入图片描述

list和vector适配反向迭代器

我们用list模拟的代码来用一用这里的反向迭代器,在我们的list迭代器中,搞出来反向迭代器和rbegin、rend。记得在list中引用一下我们反向迭代器的头文件。

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

那么到这里迭代器适配器就讲完了。上面用了list和vector的正向迭代器两个例子来成功适配出了各自的反向迭代器。当然并不单单只要有正向迭代器就能适配出反向迭代器,这个是有条件,必须能够支持++和 - -。但最主要的还是 - -。

迭代器的类型

在这里插入图片描述

这里面,只有forward_list、unordered_map、unordered_set的迭代器没有 - - 的函数接口,剩下的都有。

迭代器一共分为三类:

  1. forward_iterator(单向迭代器),只支持++,相关容器有:forward_list、unordered_map、unordered_set。
  2. bidirectional_iterator(双向迭代器),支持++和 - -,相关容器有:list、map、set。
  3. random_access_iterator(随机访问迭代器),支持++、- - 还有+和-,相关容器有:vector、deque。

上面的相关容器只给了常用的,一些不常用的没写上去。这里三个迭代器是有继承关系的,这里略提一嘴。但是文档中有一个表概括的非常全面,这里截出来给大家看一眼:

在这里插入图片描述

上面的表中对应的有不同类型迭代器能够重载的操作符。比如说+,Random Access可以重载,但是bidirectional和forward就不能。

根据这个关系就可以得出:双向可实现单向,随机也可实现双向和单向。

库中reverse和sort模板参数中的迭代器

在这里插入图片描述
在这里插入图片描述

上面两个模板参数中其实已经在提示你改用什么样的迭代器了。sort传容器的迭代器至少是随机访问迭代器,reverse传容器的迭代器至少是双向迭代器。所以我们链表就不能用算法库中的sort,要自己实现一个,因为链表的迭代器是双向迭代器。

相关文章:

  • 【竞技宝】LOL:Able小炮连续起跳收割战场 OMG2-0轻取TT
  • 微服务系统设计:横向扩展和纵向扩展的对比
  • C#基础题
  • Java中使用StopWatch实现代码块耗时统计/计时某段代码执行
  • ​LeetCode解法汇总2670. 找出不同元素数目差数组
  • C语言指针学习 之 指针是什么
  • python验证服务器或容器端口是否可以用
  • Linux(ubuntu) -- 安装后调配
  • C语言实现12种排序算法
  • kubernetes内外网通信-集群外节点访问 pod ip
  • k8s二进制及负载均衡集群部署详解
  • grafana安装DevOpsProdigy KubeGraf 1.5.2
  • 协作办公开源神器:ONLYOFFICE
  • BrainAGE作为大脑老化的神经影像标志物的十年
  • 微信小程序for循环嵌套
  • 【翻译】Mashape是如何管理15000个API和微服务的(三)
  • canvas实际项目操作,包含:线条,圆形,扇形,图片绘制,图片圆角遮罩,矩形,弧形文字...
  • ES学习笔记(10)--ES6中的函数和数组补漏
  • JavaScript对象详解
  • WePY 在小程序性能调优上做出的探究
  • 技术胖1-4季视频复习— (看视频笔记)
  • 快速体验 Sentinel 集群限流功能,只需简单几步
  • 人脸识别最新开发经验demo
  • 如何邀请好友注册您的网站(模拟百度网盘)
  • 如何抓住下一波零售风口?看RPA玩转零售自动化
  • 一个JAVA程序员成长之路分享
  • ​一文看懂数据清洗:缺失值、异常值和重复值的处理
  • #我与Java虚拟机的故事#连载03:面试过的百度,滴滴,快手都问了这些问题
  • (32位汇编 五)mov/add/sub/and/or/xor/not
  • (Redis使用系列) SpringBoot中Redis的RedisConfig 二
  • (二)WCF的Binding模型
  • (附源码)springboot金融新闻信息服务系统 毕业设计651450
  • (离散数学)逻辑连接词
  • (每日持续更新)jdk api之StringBufferInputStream基础、应用、实战
  • (三分钟)速览传统边缘检测算子
  • (转)详解PHP处理密码的几种方式
  • .htaccess 强制https 单独排除某个目录
  • .NET delegate 委托 、 Event 事件,接口回调
  • .NET 反射的使用
  • .net 微服务 服务保护 自动重试 Polly
  • .Net7 环境安装配置
  • .pings勒索病毒的威胁:如何应对.pings勒索病毒的突袭?
  • [ Linux ] git工具的基本使用(仓库的构建,提交)
  • [.NET]桃源网络硬盘 v7.4
  • [04]Web前端进阶—JS伪数组
  • [ASP.NET 控件实作 Day7] 设定工具箱的控件图标
  • [AutoSar]BSW_Memory_Stack_004 创建一个简单NV block并调试
  • [BUUCTF 2018]Online Tool
  • [CC2642R1][VSCODE+Embedded IDE+IAR Build+Cortex-Debug] TI CC2642R1基于VsCode的开发环境
  • [Eclipse] 详细设置护眼背景色和字体颜色并导出
  • [EFI]Dell Latitude-7400电脑 Hackintosh 黑苹果efi引导文件
  • [EWS]查找 文件夹
  • [Fri 26 Jun 2015 ~ Thu 2 Jul 2015] Deep Learning in arxiv
  • [Google Guava] 1.1-使用和避免null
  • [hdu 3065] 病毒侵袭持续中 [AC自动机] [病毒特征码匹配]