✨个人主页: 北 海
?所属专栏: C++修行之路
?每篇一句: 图片来源
文章目录
?前言?️正文1、反向迭代器设计1.1、反向思想1.2、多参数模板1.3、极致对称1.4、其他功能 2、应用于 vector3、应用于 list4、源码 ?总结
?前言
适配器模式是 STL
中的重要组成部分,在上一篇文章中我们学习了 容器适配器
的相关知识,即 stack
与 queue
,除了 容器适配器
外,还有 迭代器适配器
,借助 迭代器适配器
,可以轻松将各种容器中的普通迭代器转变为反向迭代器,这正是适配器的核心思想
?️正文
反向迭代器适用于所有的容器,因此它是作为一个单独的 .h
文件出现的,别的容器如果想使用,直接包含就行了
1、反向迭代器设计
反向迭代器 reverse_iterator
可以用来反向遍历容器,在某些场景下很实用
反向迭代器类中需要有:正向迭代器对象
、构造函数
template<class Iterator>struct __reverse_iterator{Iterator _cur;//正向迭代器类//需要借助构造函数,构成出正向迭代器__reverse_iterator(Iterator cur):_cur(cur){}};
注意:源码中的反向迭代器设计较为复杂,涉及 萃取 等操作,为了方便学习,这里实现的是简易版本
1.1、反向思想
何谓反向?与正向相反就是反向,比如时钟正常都是顺时针转,但如果时钟逆时针选择,此时就称为反方向的钟
存在 vector<int>() = {1, 2, 3, 4, 5}
不同方向的遍历结果不同
正向迭代器:正向遍历
结果:1 2 3 4 5
反向迭代器:反向遍历
结果:5 4 3 2 1
注:库中的反向迭代器在设计时,为了最求极致的对称,rbegin()
指向最后一个有效元素的下一个位置,rend()
指向第一个有效元素(位置是与正向迭代器相反的)
//_cur 为正向迭代器self& operator++(){--_cur;//你要++,我就--return *this;}self operator++(int){Iterator tmp = _cur;--_cur;return tmp;}self& operator--(){++_cur;//你要--,我就++,反过来操作return *this;}self operator--(int){Iterator tmp = _cur;++_cur;return tmp;}
1.2、多参数模板
在模拟实现 list
迭代器类时,为了解决普通对象与 const
对象的代码冗余问题,引入了多参数,通过对形参传递不同的对象,变换为不同属性的迭代器;在反向迭代器类重,这一种巧妙思想也得到了继承
template<class Iterator, class Ref, class Ptr>struct __reverse_iterator{typedef __reverse_iterator<Iterator, Ref, Ptr> self;//重命名迭代器类为 selfIterator _cur;//正向迭代器类//……};
在涉及 operator*()
时,需要返回目标对象引用,使用 Ref
;同理,在涉及 operator->()
时,需要返回目标对象指针,使用 Ptr
具体返回对象(引用 / 指针)是否为 const
修饰,取决于调用方
1.3、极致对称
在反向迭代器类中,有一个十分奇怪的函数 operator*()
,它返回的并非当前所指向的对象,而且上一个对象
Ref operator*(){Iterator tmp = _cur;return *--tmp;//返回的是上一个对象}
原因:大佬在设计时为了追求与正向迭代器的绝对对称,故意指向位置与其保持一致,仅仅是 rend()
在 begin()
处,rbegin()
在 end()
处
经过这样设计后,rbegin()
和 rend()
函数的实现就变得简单了,此时压力给到了 operator*()
的实现
reverse_iterator rbegin() { reverse_iterator(end()); }//开始 -> 尾reverse_iterator rend() { reverse_iterator(begin()); }//结束 -> 头
1.4、其他功能
假设想通过迭代器直接访问自定义对象中的成员时,需要用到 operator->()
函数,作用是取出迭代器所指向对象的指针 Ptr
Ptr operator->(){return &(operator*());//采取复用的形式}
迭代器还需要比较函数 operator==()
与 operator!=()
,具体实现时,都是在复用具体对象的比较函数
bool operator==(const self& s){return (_cur == s._cur);}bool operator!=(const self& s){return (_cur != s._cur);}
以上就是反向迭代器所必须的基础功能,如果你还想实现更多比较逻辑,如 operator<()
等,可以自己实现
反向迭代器类的完整代码:
#pragma oncenamespace Yohifo{template<class Iterator, class Ref, class Ptr>struct __reverse_iterator{typedef __reverse_iterator<Iterator, Ref, Ptr> self;//重命名迭代器类为 selfIterator _cur;//正向迭代器类__reverse_iterator(Iterator cur):_cur(cur){}Ref operator*(){Iterator tmp = _cur;return *--tmp;}Ptr operator->(){return &(operator*());}//_cur 为普通(正向)迭代器self& operator++(){--_cur;return *this;}self operator++(int){Iterator tmp = _cur;--_cur;return tmp;}self& operator--(){++_cur;return *this;}self operator--(int){Iterator tmp = _cur;++_cur;return tmp;}bool operator==(const self& s){return (_cur == s._cur);}bool operator!=(const self& s){return (_cur != s._cur);}};}
编写完成此头文件 reverse_iterator.hpp
后,任何具有正向迭代器的容器,都可以利用迭代器适配器,适配出属于自己的反向迭代器
具体使用例子可以接着往下看
2、应用于 vector
在 vector
模拟实现中,引入头文件 reverse_iterator.hpp
,定义出反向迭代器所必须的函数
#pragma once#include <iostream>#include <string>#include <assert.h>#include <vector>//对比测试用#include <algorithm>//排序所需要的头文件#include <functional>//仿函数头文件#include "reverse_iterator.hpp"//使用反向迭代器必须的头文件using std::cin;using std::cout;using std::endl;using std::string;template<class T>class vector{public://……//=====反向迭代器=====typedef __reverse_iterator<iterator, T&, T*> reverse_iterator;typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;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()); }//……private:iterator _start;//指向起始位置iterator _finish;//指向有效元素的下一个位置iterator _end_of_storage;//指向可用空间的下一个位置};
通过反向迭代器进行遍历
void TestVector9(){int arr[] = { 1,2,3,4,5,6,7,8,9 };vector<int> v(arr, arr + sizeof(arr) / sizeof(arr[0]));vector<int>::reverse_iterator rit = v.rbegin();while (rit != v.rend()){cout << *rit << " ";++rit;//反向迭代器++,就是--}cout << endl;}
可以成功使用反向迭代器进行遍历
3、应用于 list
既然是迭代器适配器,那么反向迭代器也可以适用于 list
#pragma once#include <iostream>#include <cassert>#include <vector>#include "reverse_iterator.hpp"//使用反向迭代器using namespace std;//……//list本类template<class T>class list{typedef __list_node<T> node;typedef T value_type;typedef T& refence;typedef const T& const_refence;public://……//=====反向迭代器=====typedef __reverse_iterator<iterator, T&, T*> reverse_iterator;typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;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()); }//……private://初始化出头节点void empty_init(){_head = new node;_head->_prev = _head->_next = _head;}node* _head;//哨兵位节点};
通过反向迭代器对自定义类型数据进行遍历
struct B{B(int a = 0, char c = 0):_a(a),_c(c){}int _a;char _c;};void TestList(){list<B> lb;lb.push_back(B(1, 'a'));lb.push_back(B(2, 'b'));lb.push_back(B(3, 'c'));list<B>::reverse_iterator rit = lb.rbegin();while (rit != lb.rend()){cout << "_a: " << rit->_a << " | " << "_c: " << rit->_c << endl;++rit;//即使是反向迭代器,也是++}cout << endl;}
此时主要是用到了 operator->()
访问自定义类型中的成员变量
4、源码
关于 vector
和 list
(迭代器版)的源码在下面仓库中
vector(反向迭代器版)
list(反向迭代器版)
?总结
以上就是本篇关于 C++ STL 学习之【反向迭代器】的全部内容了,在本篇文章中,我们主要学习了反向迭代器类的思想及实现,最后分别用了 vector
和 list
进行了测试,成功实现了反向遍历
如果你觉得本文写的还不错的话,可以留下一个小小的赞?,你的支持是我分享的最大动力!
如果本文有不足或错误的地方,随时欢迎指出,我会在第一时间改正
相关文章推荐
STL 之 适配器
C++ STL学习之【容器适配器】
===============
STL 之 list 类
C++ STL学习之【list的模拟实现】
C++ STL学习之【list的使用】
===============
STL 之 vector 类
C++ STL学习之【vector的模拟实现】
C++ STL学习之【vector的使用】
![承蒙厚爱,感谢支持 感谢支持](http://zhangshiyu.com/zb_users/upload/2023/05/20230503145707168309702714166.gif)