✨个人主页： 夜 默
🎉所属专栏： C++修行之路
🎊每篇一句： 图片来源
- A year from now you may wish you had started today.
- 明年今日，你会希望此时此刻的自己已经开始行动了。
文章目录
- 🌇前言
- 🏙️正文
- 1、反向迭代器设计
- 1.1、反向思想
- 1.2、多参数模板
- 1.3、极致对称
- 1.4、其他功能
- 2、应用于 vector
- 3、应用于 list
- 4、源码
- 🌆总结
🌇前言
适配器模式是 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; //重命名迭代器类为 self
Iterator _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 once
namespace Yohifo
{
template<class Iterator, class Ref, class Ptr>
struct __reverse_iterator
{
typedef __reverse_iterator<Iterator, Ref, Ptr> self; //重命名迭代器类为 self
Iterator _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的使用】
