【C++】反向迭代器

一、什么是反向迭代器

C++ 中一共有四种迭代器 – iterator、const_iterator、reverse_iterator 以及 const_reverse_iterator，其中正向迭代器我们已经很熟悉了，其实反向迭代器的使用和正向迭代器几乎一样，反向迭代器的特点如下：

• rbegin() 相当于 end()；
• rend() 相当于 begin()；
• 反向迭代器++相当于正向迭代器–；
• 其他操作比如 * != -> 和正向迭代器相同。

反向迭代器的使用：反向迭代器的使用和正向迭代器完全相同

void reverse_iterator_test() {vector<int> v;v.push_back(1);v.push_back(5);v.push_back(6);v.push_back(5);v.push_back(9);vector<int>::reverse_iterator rit = v.rbegin();while (rit != v.rend()) {(*rit) += 1;cout << *rit << " ";++rit;}cout << endl;
}

在以前 string、vector 和 list 中模拟实现中我们只实现了正向迭代器，而并没有去实现反向迭代器，今天我们就来探究如何实现反向迭代器。

---

二、STL 源码中反向迭代器的实现

我们可以通过参考 STL 源码中反向迭代器的实现方式来学习如何实现反向迭代器，如下：

//list.h部分源码 -- SGI版
template <class T, class Alloc = alloc>
class list {
public:typedef __list_iterator<T, T&, T*>             iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;#ifdef __STL_CLASS_PARTIAL_SPECIALIZATIONtypedef reverse_iterator<const_iterator> const_reverse_iterator;typedef reverse_iterator<iterator> reverse_iterator;

//vector.h部分源码 -- SGI版
template <class T, class Alloc = alloc>
class vector {
public:typedef T value_type;typedef value_type* iterator;typedef const value_type* const_iterator;#ifdef __STL_CLASS_PARTIAL_SPECIALIZATIONtypedef reverse_iterator<const_iterator> const_reverse_iterator;typedef reverse_iterator<iterator> reverse_iterator;

可以看到，STL 源码中 vector 和 list 的反向迭代器都是 reverse_iterator 类的 typedef，而 reverse_iterator 类位于源码中的 stl_iterator.h 中，其部分源码如下：

//stl_iterator.h -- SGI版
template <class Iterator>
class reverse_iterator {
protected:Iterator current;public: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) {}reference operator*() const {Iterator tmp = current;return *--tmp;}
#ifndef __SGI_STL_NO_ARROW_OPERATORpointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */self& operator++() {--current;return *this;}self& operator--() {++current;return *this;}//...
}

如上，正向迭代器是 reverse_iterator 的模板参数，而反向迭代器是 reverse_iterator 的对象，所以反向迭代器是一个容器适配器，它的适配容器就是对应的正向迭代器，这样它就能根据传递过来的正向迭代器的不同实例化出对应的反向迭代器。

也就是说，只要实现了 reverse_iterator 类，以后不管是 vector、list、map 还是其他的容器，只要你将其对应的正向迭代器传递给我，我就能适配出对应的反向迭代器，做到泛型编程。

---

三、reverse_iterator 的模拟实现

模拟实现代码：iterator.h

#pragma oncenamespace thj {template<class Iterator, class Ref, class Ptr>class reverse_iterator {typedef reverse_iterator<Iterator, Ref, Ptr> self;public:reverse_iterator(Iterator it)   //构造: _it(it){}self& operator++() {  //++--_it;return *this;}self operator++(int) {  //后置++  返回值不加引用，因为tmp是局部变量Iterator tmp = _it;--_it;return tmp;}self& operator--() {  //--++_it;return *this;}self operator--(int) {  //后置--  返回值不加引用Iterator tmp = _it;++_it;return tmp;}bool operator!=(const self& s) const {  //不等于return _it != s._it;}Ref operator*() {  //解引用，返回的是反向迭代器的前一个位置Iterator tmp = _it;return *(--tmp);}Ptr operator->() {  //-> 返回节点数据的地址return &(operator*());}private:Iterator _it;  //成员变量是正向迭代器};
}

模拟实现细节：

1、由于 rbegin() 等价于 end()，rend() 等价于 begin()，所以 ++reverse_iterator 等价于 --iteraor，–reverse_iterator 等价于 ++iterator；

2、在实现 operator*() 和 operator->() 时我们并不知道 T 的类型 (const 与非 const)，所以我们不能确定函数的返回值；STL 源码中使用迭代器萃取的方法来解决这个问题，如下：

//stl_iterator.h部分源码
template <class Iterator>
class reverse_iterator
{// iterator_traits -- 迭代器萃取typedef typename iterator_traits<Iterator>::pointertypedef typename iterator_traits<Iterator>::reference reference;reference operator*() const {Iterator tmp = current;return *--tmp;}
#ifndef __SGI_STL_NO_ARROW_OPERATORpointer operator->() const { return &(operator*()); }
};

但是这种方式十分复杂，并且校招的时候并不会考察萃取相关的知识，所以这里我们参考 list 正向迭代器 的设计思路 – 增加两个模板参数分别作为 operator*() 和 operator->() 函数的返回值，如下：

//typedef reverse_iterator<Iterator, T&, T*> reverse_iterator 反向迭代器
//typedef const_reverse_iterator<Iterator, const T&, const T*> const_reverse_iterator const反向迭代器template<class Iterator, class Ref, class Ptr>
class reverse_iterator {typedef reverse_iterator<Iterator, Ref, Ptr> self;public:Ref operator*() {  //解引用，特别注意：返回的是反向迭代器的前一个位置Iterator tmp = _it;return *(--tmp);}Ptr operator->() {  //-> 返回节点数据的地址return &(operator*());}private:Iterator _it;  //成员变量是正向迭代器
};

3、同时，由于 end 是指向最后一个元素的下一个位置，而 rbegin 由 end 适配得到，所以反向迭代器中 operator*() 不是返回迭代器当前位置的数据，而是返回迭代器前一个位置的数据，不然会发生越界访问。

---

四、vector 和 list 反向迭代器的实现

现在我们已经实现了 reverse_iterator 类，所以可以直接用 vector 和 list 的正向迭代器作为 reverse_iterator 的适配容器适配出它们的反向迭代器。

vector 反向迭代器

反向迭代器相关代码：

#include "iterator.h"
template<class T>class list{//反向迭代器typedef thj::reverse_iterator<iterator, T&, T*> reverse_iterator;typedef thj::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());}};
}

list.h：

#pragma once#include <assert.h>
#include <algorithm>
#include "iterator.h"namespace thj {template<class T>struct list_node{list_node<T>* _next;//不加<T>也没错，但是写上好一些list_node<T>* _prev;T _data;list_node(const T& x)//构造:_next(nullptr), _prev(nullptr), _data(x){}};//迭代器最终版//const 迭代器 -- 增加模板参数，解决 operator*() 返回值与 operator->() 返回值问题//typedef __list_iterator<T, T&, T*> iterator;//typedef __list_iterator<T, const T&, const T*> const_iterator;//STL源码中大佬的写法，利用多个模板参数来避免副本造成的代码冗余问题template<class T, class Ref, class Ptr>struct __list_iterator  //迭代器类{typedef list_node<T> node;  //重命名list节点typedef __list_iterator<T, Ref, Ptr> Self;  //这里进行重命名是为了后续再添加模板参数时只用修改这一个地方node* _pnode;  //节点指针作为类的唯一成员变量__list_iterator(node* p):_pnode(p){}Ref operator*()  //解引用{return _pnode->_data;}Ptr operator->()  //->{return &_pnode->_data;}Self& operator++() //前置++{_pnode = _pnode->_next;return *this;}Self& operator++(int) //后置++{Self it(*this);_pnode = _pnode->_next;return it;}Self& operator--() //前置--{_pnode = _pnode->_prev;return *this;}Self& operator--(int) //后置--{Self it(*this);_pnode = _pnode->_prev;return it;}bool operator!=(const Self& it) const //!={return _pnode != it._pnode;}bool operator==(const Self& it) const  //=={return _pnode == it._pnode;}};//list 类template<class T>class list{typedef list_node<T> node;public:typedef __list_iterator<T, T&, T*> iterator;  //迭代器typedef __list_iterator<T, const T&, const T*> const_iterator; //const 迭代器//反向迭代器typedef thj::reverse_iterator<iterator, T&, T*> reverse_iterator;typedef thj::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());}//迭代器iterator begin() {return iterator(_head->_next);}iterator end() {//iterator it(_head);//return it;//直接利用匿名对象更为便捷return iterator(_head);}const_iterator begin() const {return const_iterator(_head->_next);}const_iterator end() const {return const_iterator(_head);}void empty_initialize() {  //初始化 -- 哨兵位头结点_head = new node(T());_head->_next = _head;_head->_prev = _head;_size = 0;  //空间换时间，用于标记节点个数}list() {  //构造，不是list<T>的原因：构造函数函数名和类名相同，而list<T>是类型empty_initialize();}//迭代器区间构造template <class InputIterator>list(InputIterator first, InputIterator last) {empty_initialize();while (first != last){push_back(*first);++first;//first++;}}// 拷贝构造的现代写法//list(const list& lt) 官方库是这样写的，这是由于在类内类名等价于类型，但不建议自己这样写list(const list<T>& lt) {empty_initialize();  //初始化头结点，防止交换后tmp野指针不能正常的调用析构list<T> tmp(lt.begin(), lt.end());swap(tmp);}//赋值重载现代写法//list& operator=(list lt)list<T>& operator=(list<T> lt) {  //不能加引用，lt是调用拷贝构造生成的swap(lt);return *this;}~list() {  //析构clear();delete _head;_head = nullptr;}void swap(list<T>& lt) {  //交换两个链表，本质上是交换两个链表的头结点std::swap(_head, lt._head);std::swap(_size, lt._size);}size_t size() const {  //增加一个计数的成员，以空间换时间return _size;}bool empty() {  //判空return _size == 0;}void clear() {iterator it = begin();while (it != end()) {it = erase(it);}_size = 0;}void push_back(const T& x) {insert(end(), x);  //复用}void push_front(const T& x) {insert(begin(), x);  //复用}void pop_front() {erase(begin());}void pop_back() {erase(--end());}iterator insert(iterator pos, const T& x) {node* newnode = new node(x);node* cur = pos._pnode;node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;cur->_prev = newnode;newnode->_next = cur;++_size;return iterator(pos);}iterator erase(iterator pos) {assert(pos != end());node* prev = pos._pnode->_prev;node* next = pos._pnode->_next;prev->_next = next;next->_prev = prev;delete pos._pnode;--_size;return iterator(next);}private:node* _head;size_t _size;};
}

test.cpp：

void list_reverse_iterator_test() {thj::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);thj::list<int>::reverse_iterator rit = lt.rbegin();  //反向迭代器while (rit != lt.rend()) {(*rit)++;cout << *rit << " ";++rit;}cout << endl;const thj::list<int> clt(lt.begin(), lt.end());thj::list<int>::const_reverse_iterator crit = clt.rbegin();  //const反向迭代器while (crit != clt.rend()) {//(*crit)++;cout << *crit << " ";++crit;}cout << endl;
}

vector 反向迭代器

反向迭代器相关代码：

namespace thj {template<class T>class vector {public://正向迭代器typedef T* iterator;typedef const T* const_iterator;//反向迭代器 -- 容器适配器typedef thj::reverse_iterator<iterator, T&, T*> reverse_iterator;typedef thj::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());}};
}

vector.h：

#pragma once
#include <iostream>
#include <assert.h>
#include <string.h>
#include <algorithm>
#include "iterator.h"namespace thj {template<class T>class vector {public://正向迭代器typedef T* iterator;typedef const T* const_iterator;iterator begin() {return _start;}iterator end() {return _finish;}const_iterator begin() const {return _start;}const_iterator end() const {return _finish;}//反向迭代器 -- 容器适配器//反向迭代器 -- 容器适配器typedef thj::reverse_iterator<iterator, T&, T*> reverse_iterator;typedef thj::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());}public://---------------------------constructor------------------------------////无参构造vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}//迭代器区间构造template<class InputIterator>vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){while (first != last){push_back(*first);++first;}}//n个val构造vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(n);for (size_t i = 0; i < n; i++)push_back(val);}//n个val构造 -- 重载vector(int n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(n);for (int i = 0; i < n; i++)push_back(val);}//拷贝构造 -- 现代写法vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){vector<T> tmp(v.begin(), v.end());  //复用构造函数和swap函数swap(tmp);}//析构函数~vector() {delete[] _start;_start = _finish = _end_of_storage = nullptr;}//赋值重载vector<T>& operator=(vector<T> v)  //复用拷贝构造，存在自我赋值的问题，但不影响程序正确性{swap(v);return *this;}//---------------------------------capacity------------------------------------//size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}bool empty() const{return _start == _finish;}//扩容void reserve(size_t n){if (n > capacity())  //reserve 函数不缩容{T* tmp = new T[n];//memcpy(tmp, _start, sizeof(T) * size());  //error//memcpy有自定义类型的浅拷贝问题，需要对每个元素使用拷贝构造进行深拷贝for (int i = 0; i < size(); i++)tmp[i] = _start[i];  //拷贝构造size_t oldSize = _finish - _start;  //记录原来的size，避免扩容不能确定_finishdelete[] _start;_start = tmp;_finish = _start + oldSize;_end_of_storage = _start + n;}}//扩容并初始化void resize(size_t n, T x = T()){if (n > capacity())  //resize 不缩容{reserve(n);}if (n > size()){while (_finish < _start + n){*_finish = x;++_finish;}}if (n < size()){_finish = _start + n;}}//------------------------------element access-------------------//T& operator[](size_t pos){assert(pos < size());  //检查越界return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}//----------------------------------modifys-----------------------------------////尾插void push_back(const T& n){if (size() == capacity()){size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);}*_finish = n;++_finish;}//尾删void pop_back(){assert(!empty());--_finish;}//任意位置插入iterator insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);//扩容导致 pos 迭代器失效if (size() == capacity()){size_t oldPos = pos - _start;  //记录pos，避免扩容后pos变为野指针size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);pos = _start + oldPos;  //扩容之后更新pos}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}//任意位置删除 -- erase 之后也认为 pos 迭代器失效iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator begin = pos;while (begin < _finish - 1){*begin = *(begin + 1);++begin;}--_finish;return pos;}//交换两个对象void swap(vector<T>& v){std::swap(_start, v._start);  //复用算法库的swap函数std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}void clear(){_finish = _start;}private:T* _start;T* _finish;T* _end_of_storage;};
}

test.cpp：

void vector_reverse_iterator_test() {thj::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);thj::vector<int>::reverse_iterator rit = v.rbegin();while (rit != v.rend()) {(*rit)++;cout << *rit << " ";++rit;}cout << endl;const thj::vector<int> cv(v.begin(), v.end());thj::vector<int>::const_reverse_iterator crit = cv.rbegin();while (crit != cv.rend()) {//(*crit)++;cout << *crit << " ";++crit;}cout << endl;
}

---