目录

1.反向迭代器的功能

2.算法

方法1:新写一个类用于反向迭代器

方法2:封装正向迭代器实现反向迭代器

解析operator*

正向迭代器和反向迭代器的关系

返回 *--tmp的原因

3.为自制的vector和list编写反向迭代器

编写统一的反向迭代器

修改vector头文件

修改list头文件

测试代码

4.洛谷题目测试:B2089 数组逆序重存放


1.反向迭代器的功能

以list为例,下面画框的都是反向迭代器

(https://legacy.cplusplus.com/reference/list/list/?kw=list) 

功能:使用operator++操作反向迭代器能反向遍历;使用operator--操作反向迭代器能正向遍历;和正向迭代器是反过来的

2.算法

方法1:新写一个类用于反向迭代器

修改CD46.【C++ Dev】list的模拟实现(1)文章和CD47.【C++ Dev】list的模拟实现(2)文章的__list_iterator结构体的operator++和operator--

template<class T, class Ref, class Ptr>
struct __list_reverse_iterator
{typedef __list_node<T>* link_type;typedef __list_reverse_iterator<T, T&, T*> reverse_iterator;typedef __list_reverse_iterator<T, const T&, const T*> const_reverse_iterator;typedef __list_reverse_iterator<T, Ref, Ptr>	self;typedef Ref reference;typedef Ptr pointer;__list_iterator(link_type x):node(x){}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& x) const{return node != x.node;}bool operator==(const self& x) const{return node == x.node;}reference operator*(){return node->data;}pointer operator->(){return &(node->data);}link_type node;
};

但会有部分代码和正向迭代器重复,会冗余,而且STL库不是像上面这样写的:

typedef reverse_iterator<const_iterator> const_reverse_iterator;
typedef reverse_iterator<iterator> reverse_iterator;

核心:封装正向迭代器实现反向迭代器

方法2:封装正向迭代器实现反向迭代器

反向迭代器++使用正向迭代器的--;反向迭代器--使用正向迭代器的++

STL库的list:

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

STL库的vector:

typedef value_type* iterator;
typedef const value_type* const_iterator;
typedef reverse_iterator<const_iterator> const_reverse_iterator;
typedef reverse_iterator<iterator> reverse_iterator;

会发现反向迭代器的形式都是统一的,这种写法的reverse_iterator能适配各种容器

typedef reverse_iterator<const_iterator> const_reverse_iterator;
typedef reverse_iterator<iterator> reverse_iterator;

其实STL库的迭代器的统一实现在stl_iterator.h中:

下面摘取核心部分:

template <class Iterator>
class reverse_iterator
{typedef Iterator iterator_type;typedef reverse_iterator<Iterator> self;
private:Iterator current;
public:reference operator*() const{Iterator tmp = current;return *--tmp;}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;}pointer operator->() const { return &(operator*()); }
};

解析operator*

operator++/--/->的算法比较好理解,但是operator*返回语句的写法:return *--tmp比较奇怪

看看listh和vector的rbegin()和rend()的实现:

两者的代码都是一样的

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());
}
正向迭代器和反向迭代器的关系

对于list:

 begin()指向哨兵位指向的节点,end()指向哨兵位:

rbegin()是用end()构造的,rend()是用begin()构造的:

对于vector:

begin()指向哨兵位指向的节点,end()指向哨兵位:

rbegin()是用end()构造的,rend()是用begin()构造的:

结论:正向迭代器和反向迭代器是镜像对称关系: begin()是rend();end()是rbegin()

返回 *--tmp的原因

设想一下,如果对rbegin()直接返回*tmp,对于vector和list得到的结果都是随机值,会出现错误

STL的策略:错位访问, 返回*--tmp,即返回tmp的前一个迭代器

例如:

下面图片中的it代表反向迭代器,--tmp是调用了operator--

对于vector:

(当it==rbegin()时) 

(当it==rend()时,越界访问)

 (当it==rend()-1时)

it==rend()-1可以做个测试:

#include <iostream>
#include <vector>
int main()
{std::vector<int> v = { 1,2,3 };auto it = v.rend()-1;//it指向2std::cout << *(it);//返回it指向的前一个元素的值return 0;
}

运行结果:

对于list:

(当it==rbegin()时)

(当it==rend()时,越界访问)

 (当it==--rend()时)

it==--rend()可以做个测试:

#include <iostream>
#include <list>
int main()
{std::list<int> v = { 1,2,3 };auto it = --v.rend();std::cout << *(it);return 0;
}

运行结果:

结论:operator*解引用是前一个位置,虽然错位,但遍历能正常进行

3.为自制的vector和list编写反向迭代器

编写统一的反向迭代器

#pragma once
namespace mystl
{template<class Iterator,class Ref,class Ptr>class ReverseIterator{typedef Ref reference;typedef Ptr pointer;typedef ReverseIterator<Iterator, Ref, Ptr> Self;public:ReverseIterator(Iterator it):current(it){}reference operator*(){Iterator tmp= current;return *(--tmp);}pointer operator->(){return &(operator*());}Self& operator++(){current--;return *this;}Self& operator++(int){ReverseIterator tmp(current);current--;return tmp;}Self& operator--(){current++;return *this;}Self& operator--(int){ReverseIterator tmp(current);current++;return tmp;}bool operator!=(const Self& s) const{return s.current != current;}bool operator==(const Self& s) const{return s.current == current;}private:Iterator current;};
}

注意operator*的返回值是ReverseIterator对象,需要右3个参数:<Iterator, Ref, Ptr>,自定义成Self即可

修改vector头文件

之前在以下文章写过vector的模拟实现:

CD42.【C++ Dev】vector模拟实现(1)
CD43.【C++ Dev】vector模拟实现(2)

CD44.【C++ Dev】vector模拟实现(3)

添加这两行即可:

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

修改list头文件

添加这两行即可:

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

测试代码

#include "vector.h"
#include "list.h"
#include <iostream>
int main()
{mystl::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);int times = 0;auto it1 = v.rbegin();while (it1 != v.rend()){std::cout << *it1 << " ";if (times % 2)//测试前置++和后置++it1++;else++it1;}std::cout << std::endl;mystl::list<int> ls;ls.push_back(6);ls.push_back(7);ls.push_back(8);ls.push_back(9);ls.push_back(10);auto it2 = ls.rbegin();while (it2 != ls.rend()){std::cout << *it2 << " ";if (times % 2)//测试前置++和后置++it2++;else++it2;}return 0;
}

运行结果:

4.洛谷题目测试:B2089 数组逆序重存放

https://www.luogu.com.cn/problem/B2089

使用vector存储的代码:

#include <iostream>
namespace mystl
{template<class Iterator,class Ref,class Ptr>class ReverseIterator{typedef Ref reference;typedef Ptr pointer;typedef ReverseIterator<Iterator, Ref, Ptr> Self;public:ReverseIterator(Iterator it):current(it){}reference operator*(){Iterator tmp= current;return *(--tmp);}pointer operator->(){return &(operator*());}Self& operator++(){current--;return *this;}Self& operator++(int){ReverseIterator tmp(current);current--;return tmp;}Self& operator--(){current++;return *this;}Self& operator--(int){ReverseIterator tmp(current);current++;return tmp;}bool operator!=(const Self& s) const{return s.current != current;}bool operator==(const Self& s) const{return s.current == current;}private:Iterator current;};template<class T>class vector{public:typedef T value_type;typedef value_type* iterator;typedef const value_type* const_iterator;typedef ReverseIterator< iterator, T&, T*> reverse_iterator;typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;typedef size_t size_type;typedef value_type& reference;typedef const value_type& const_reference;vector() : start(0), finish(0), end_of_storage(0) {}vector(const vector<value_type>& x):start(0), finish(0), end_of_storage(0){reserve(x.capacity());for (size_type i = 0; i < x.size(); i++){start[i] = x.start[i];}finish = start + x.size();}size_type capacity() const{return end_of_storage - start;}size_type size() const{return finish - start;}iterator begin(){return start;}reverse_iterator rbegin(){return reverse_iterator(end());}const_iterator begin() const{return start;}iterator end(){return finish;}reverse_iterator rend(){return reverse_iterator(begin());}const_iterator end() const{return finish;}void  reserve(size_type n){if (n > capacity()){T* tmp = new T[n];size_t len = size();//delete前先保存元素的个数!bool flag = false;if (size() == 0){flag = true;len = n;}if (start){for (size_type i = 0; i < len; i++){tmp[i] = start[i];}delete[] start;}if (flag)//如果vector在什么元素都没有{start = finish = tmp;}else{start = tmp;finish = start + len;}end_of_storage = start + n;}}void push_back(const value_type& val){if (finish == nullptr)reserve(4);if (finish == end_of_storage)reserve(capacity() * 2);*finish = val;finish++;}iterator insert(iterator position, const value_type& val){assert(position >= start && position <= finish);if (finish == nullptr)reserve(4);if (finish == end_of_storage)reserve(capacity() * 2);iterator i = finish - 1;while (i >= position){*(i + 1) = *i;i--;}*position = val;finish++;return start;}iterator erase(iterator position){//position最大为finish-1assert(position >= start && position < finish);iterator i = position + 1;while (i < finish){*(i - 1) = *i;i++;}finish--;return position;}void pop_back(){erase(finish - 1);}void resize(size_type n, value_type val = value_type()){if (n < capacity())finish = start + n;else{//如果vector不为空,reserve不会修改start和finish的相对位置关系reserve(n);while (finish != start + n){*finish = val;finish++;}}}void swap(vector<T> tmp){std::swap(start, tmp.start);std::swap(finish, tmp.finish);std::swap(end_of_storage, tmp.end_of_storage);}vector& operator= (vector<T> x){swap(x);return *this;}explicit vector(size_type n, const value_type& val = value_type()):start(nullptr), finish(nullptr), end_of_storage(nullptr){resize(n, val);}explicit vector(int n, const value_type& val = value_type()):start(nullptr), finish(nullptr), end_of_storage(nullptr){resize(n, val);}explicit vector(long n, const value_type& val = value_type()):start(nullptr), finish(nullptr), end_of_storage(nullptr){resize(n, val);}template <class InputIterator>vector(InputIterator first, InputIterator last){InputIterator i = first;while (i != last){push_back(*i);i++;}}~vector(){if (start){delete[] start;start = finish = end_of_storage = nullptr;}}reference operator[] (size_type n){assert(n < size());return *(start + n);}const_reference operator[] (size_type n) const{assert(n < size());return *(start + n);}iterator start;iterator finish;iterator end_of_storage;};
}int main()
{int cnt;mystl::vector<int> arr;std::cin>>cnt;while(cnt--){int tmp;std::cin>>tmp;arr.push_back(tmp);}auto rit=arr.rbegin();while (rit!=arr.rend()){std::cout<<*rit<<" ";rit++;}return 0;
}

提交结果:

使用list存储的代码:

#include <iostream>
namespace mystl
{template<class Iterator,class Ref,class Ptr>class ReverseIterator{typedef Ref reference;typedef Ptr pointer;typedef ReverseIterator<Iterator, Ref, Ptr> Self;public:ReverseIterator(Iterator it):current(it){}reference operator*(){Iterator tmp= current;return *(--tmp);}pointer operator->(){return &(operator*());}Self& operator++(){current--;return *this;}Self& operator++(int){ReverseIterator tmp(current);current--;return tmp;}Self& operator--(){current++;return *this;}Self& operator--(int){ReverseIterator tmp(current);current++;return tmp;}bool operator!=(const Self& s) const{return s.current != current;}bool operator==(const Self& s) const{return s.current == current;}private:Iterator current;};template<class T>struct __list_node{//默认公有typedef __list_node<T>* link_type;__list_node(const T& x = T()):next(nullptr), prev(nullptr), data(x){}link_type next;link_type prev;T data;};template<class T,class Ref,class Ptr>struct __list_iterator{typedef __list_node<T>* link_type;typedef __list_iterator<T,T&,T*> iterator;typedef __list_iterator<T,const T&,const T*> const_iterator;typedef __list_iterator<T, Ref,Ptr>	self;typedef Ref reference;typedef Ptr pointer;__list_iterator(link_type x):node(x){}self& operator++(){node = node->next;return *this;}self operator++(int){self tmp(*this);node = node->next;return tmp;}self& operator--(){node = node->prev;return *this;}self operator--(int){self tmp(*this);node = node->prev;return tmp;}bool operator!=(const self& x) const{return node != x.node;}bool operator==(const self& x) const{return node == x.node;}reference operator*(){return node->data;}pointer operator->(){return &(node->data);}link_type node;};template<class T>class list{typedef __list_node<T> list_node;typedef __list_node<T>* link_type;typedef size_t size_type;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;typedef ReverseIterator< iterator, T&, T*> reverse_iterator;typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;list(){empty_initialize();}list(const list<T>& ls){empty_initialize();for (auto& a : ls){push_back(a);}}void push_back(const T& x){insert(end(), x);}iterator begin(){//返回哨兵位的下一个节点return node->next;}reverse_iterator rbegin(){return reverse_iterator(end());}iterator end(){//返回哨兵位return node;}reverse_iterator rend(){return reverse_iterator(begin());}const_iterator begin() const{//返回哨兵位的下一个节点return node->next;}const_iterator end() const{//返回哨兵位return node;}iterator insert(iterator pos,const T& val){link_type newnode = new list_node(val);newnode->prev = pos.node->prev;newnode->next = pos.node;pos.node->prev->next = newnode;pos.node->prev = newnode;return newnode;}iterator erase(iterator pos){iterator ret = pos.node->next;pos.node->prev->next = pos.node->next;pos.node->next->prev = pos.node->prev;delete pos.node;return ret;}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}void distance(const_iterator begin, const_iterator end, size_type& result) const{const_iterator it = begin;while (it != end){it++;result++;}}size_type size() const {size_type result = 0;distance(begin(), end(), result);return result;}void clear(){iterator it = begin();while (it != end())it=erase(it);//应对迭代器失效,接收返回值}void swap(list<T>& ls)//写成void swap(list& ls)也可以{std::swap(node, ls.node);}list<T>& operator=(list<T>& tmp)//写成list& operator=(list& tmp)也可以{swap(tmp);return *this;}~list(){clear();delete node;node = nullptr;}private:void empty_initialize(){node = new list_node;node->next = node;node->prev = node;}link_type node;};
}int main()
{int cnt;mystl::list<int> ls;std::cin>>cnt;while(cnt--){int tmp;std::cin>>tmp;ls.push_back(tmp);}auto rit=ls.rbegin();while (rit!=ls.rend()){std::cout<<*rit<<" ";rit++;}return 0;
}

提交结果:

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

如若内容造成侵权/违法违规/事实不符,请联系英文站点网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

如何解决pip安装报错ModuleNotFoundError: No module named ‘django’问题

【Python系列Bug修复PyCharm控制台pip install报错】如何解决pip安装报错ModuleNotFoundError: No module named ‘django’问题 摘要 在日常 Django 项目开发中&#xff0c;最常见的“拦路虎”之一就是 ModuleNotFoundError: No module named django。该异常通常在以下场景出…

单页面和多页面的区别和优缺点

单页面应用&#xff08;SPA&#xff09;与多页面应用&#xff08;MPA&#xff09;的区别单页面应用&#xff08;SPA&#xff09;整个应用只有一个HTML文件&#xff0c;内容通过JavaScript动态加载和渲染。页面切换时无需重新加载整个页面&#xff0c;仅更新部分DOM。依赖前端框…

暑期自学嵌入式——Day05(C语言阶段)

接续上文&#xff1a;暑期自学嵌入式——Day04&#xff08;C语言阶段&#xff09;-CSDN博客 点关注不迷路哟。你的点赞、收藏&#xff0c;一键三连&#xff0c;是我持续更新的动力哟&#xff01;&#xff01;&#xff01; 主页&#xff1a; 一位搞嵌入式的 genius-CSDN博客 …

通用人工智能AGI遥遥无期,面临幻灭

通用人工智能AGI有可能2080年前也实现不了 首先说一下&#xff0c;目前的人工智能方向是错的&#xff0c;通用人工智能不值得追捧。 真的特别无奈&#xff0c;现在还有很多人在吹AI&#xff0c;说什么2027年就能实现AGI&#xff0c;如果你指的是真正的强人工智能AGI&#xff0c…

智能体开发工具链全景图:IDE、调试器与监控平台

智能体开发工具链全景图&#xff1a;IDE、调试器与监控平台 &#x1f31f; 嗨&#xff0c;我是IRpickstars&#xff01; &#x1f30c; 总有一行代码&#xff0c;能点亮万千星辰。 &#x1f50d; 在技术的宇宙中&#xff0c;我愿做永不停歇的探索者。 ✨ 用代码丈量世界&…

三十四、【扩展工具篇】JSON 格式化与解析:集成 Monaco Editor 打造在线 JSON 工具

三十四、【扩展工具篇】JSON 格式化与解析:集成 Monaco Editor 打造在线 JSON 工具 前言 功能概览 技术选型 实现步骤 第一步:添加路由和侧边栏菜单入口 第二步:创建 JSON 工具页面 第三部分:全面测试与验证 总结 前言 在日常的接口开发和测试中,我们经常需要处理 JSON 数…

MySQL高可用集群架构:主从复制、MGR与读写分离实战

1. MySQL高可用架构概述 MySQL高可用性(High Availability)解决方案旨在确保数据库服务在硬件故障、网络问题等异常情况下仍能持续提供服务。以下是主流的高可用方案对比: 方案 原理 优点 缺点 适用场景 主从复制 基于binlog的异步复制 简单易用,对性能影响小 数据一致性弱,…

JxBrowser 7.43.5 版本发布啦!

在此版本中&#xff0c;我们进行了错误修复和稳定性改进。 &#x1f517; 点击此处了解更多详情。 &#x1f193; 获取 30 天免费试用。

借助AI学习开源代码git0.7之编译和使用

如何学习优秀的开源代码&#xff1f;目前大部分的优秀开源代码&#xff0c;代码量都已经非常庞大&#xff0c;比如git。以git为例&#xff0c;git最新版本代码有279814行&#xff0c; 而git0.7版本已经大部分实现了现在git版本的基本功能&#xff0c;而代码量却只有4950行&…

ObservableCollection全面解析

本文仅作为参考大佬们文章的总结。 ObservableCollection是C#中一个功能强大的动态数据集合类&#xff0c;特别适用于需要数据绑定和UI自动更新的场景。本文将系统性地总结ObservableCollection的核心概念、使用方法、性能优化策略以及在实际项目中的应用实践。 一、Observab…

佰力博检测与您探讨超高温介电测试的应用领域

超高温介电测试是指在极端高温条件下&#xff08;通常高于1000℃&#xff09;对材料的介电性能进行测量和分析的过程。以评估材料在高温环境下的电学性能稳定性&#xff0c;如介电常数、介电损耗、阻抗谱等参数。超高温介电测试需要用到的超高温介电阻抗测试设备&#xff1a;UT…

OneCode自治UI核心组件Layout布局介绍:构建灵活高效的界面布局系统

在现代前端开发中&#xff0c;布局系统扮演着至关重要的角色&#xff0c;它不仅决定了界面的结构美感&#xff0c;更直接影响用户体验和开发效率。OneCode作为一款企业级低代码开发平台&#xff0c;其布局引擎通过精巧的设计实现了简洁API与强大功能的完美平衡。本文将深入剖析…

为何“白名单媒体”是性价比之选?

在信息媒体空前发展的今天&#xff0c;软文营销已成为企业品牌推广的重要手段之一。然而&#xff0c;面对众多媒体&#xff0c;如何选择高性价比的发稿媒体成为许多营销人员的一个课题。其中&#xff0c;“白名单媒体”凭借其高收录率、权威背书等优势&#xff0c;逐渐成为软文…

Python 异步编程之 async 和 await

基础知识 在 Python 中&#xff0c;async 和 await 是用于异步编程的关键字&#xff0c;引入了异步/协程&#xff08;coroutine&#xff09;的概念。核心思想是通过 协程&#xff08;Coroutine&#xff09; 和 事件循环&#xff08;Event Loop&#xff09; 实现非阻塞并发&…

关于接口测试的HTTP基础【接口测试】

HTTP 协议基础知识总结&#xff08;用于 Web API 接口测试&#xff09;接口测试中最常用的通讯协议就是 HTTP&#xff08;Hypertext Transfer Protocol&#xff09;&#xff0c;本节旨在帮助理解 HTTP 协议的结构、工作流程以及如何用于接口测试。一、HTTP 协议简介HTTP 是一种…

STM32 DMA通信详解

STM32 DMA通信详解DMA(Direct Memory Access&#xff0c;直接内存访问)是STM32微控制器中一种重要的数据传输机制&#xff0c;它允许外设与内存之间或内存与内存之间直接传输数据&#xff0c;而无需CPU的干预。这种机制可以显著提高系统性能&#xff0c;特别是在需要高速数据传…

pytest--1--pytest-mock常用的方法

1. mocker.patch mocker.patch 是最常用的方法&#xff0c;用于替换指定的对象或方法。它可以用于模拟函数、方法、类或模块。 语法 mocker.patch(target, newDEFAULT, specNone, createFalse, spec_setNone, autospecNone, new_callableNone, **kwargs)示例 import pytest fro…

尚庭公寓----------分页查询

根据条件分页查询公寓列表 进行分页配置 package com.nie.lease.common.mybatisplus;import com.baomidou.mybatisplus.annotation.DbType; import com.baomidou.mybatisplus.extension.plugins.MybatisPlusInterceptor; import com.baomidou.mybatisplus.extension.plugins.in…

【图像质量评价指标】图像熵(Image Entropy) —— 熵值饱和现象

文章目录一、图像熵&#xff08;Image Entropy&#xff09;&#xff08;1&#xff09;基本原理&#xff08;2&#xff09;优势与局限&#xff08;3&#xff09;推荐策略多指标联合推荐体系噪声应对机制建议二、项目实战 —— 通过图像熵评价序列图像&#xff0c;并提取最优图像…

GaussDB in的用法

1 in的作用in运算符允许您在WHERE子句中指定多个值。 in运算符是多个OR条件的简写。2 in的语法select column_name(s) from table_name where column_name in (value1, value2, ...); 或者 select column_name(s) from table_name where column_name in (select statement);3 i…