C++的stack和queue类（三）：适配所有容器的反向迭代器

前言

list的反向迭代器

list.h文件

ReverseIterator.h文件

test.cpp文件

前言

迭代器按性质分类：

单向：forward_list
双向：list
随机：vector / deque

迭代器按功能分类：

正向
反向
const

list的反向迭代器

问题：反向迭代器和正向迭代器的不同点在哪？

答：二者功能类似，只是++和--的方向不一样

基本概念：本来每个容器都要写一个反向迭代器的类，但是这样太费劲了，我们只需要写一个反向迭代器的类模板给编译器，传不同的容器的正向迭代器实例化，编译器帮助我们实例化出各种容器的对应反向迭代器

list.h文件

#pragma once
#include<assert.h>
#include"ReverseIterator.h"namespace bit
{template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& x = T()):_next(nullptr), _prev(nullptr), _data(x){}};//正向迭代器的类模板
///template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T> Node;// typedef ListIterator<T, T&, T*>// typedef ListIterator<T, const T&, const T*>typedef ListIterator<T, Ref, Ptr> iterator;Node* _node;ListIterator(Node* node):_node(node){}// *it//T& operator*()Ref operator*(){return _node->_data;}// it->//T* operator->()Ptr operator->(){return &_node->_data;}// ++ititerator& operator++(){_node = _node->_next;return *this;}iterator operator++(int){iterator tmp(*this);_node = _node->_next;return tmp;}iterator& operator--(){_node = _node->_prev;return *this;}iterator operator--(int){iterator tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const iterator& it){return _node != it._node;}bool operator==(const iterator& it){return _node == it._node;}};//list类模板
///template<class T>class list{typedef ListNode<T> Node;public://<容器类>typedef ListIterator<T, T&, T*> iterator;//正向迭代器的类模板typedef ListIterator<T, const T&, const T*> const_iterator;//const正向迭代器的类模板//<容器的正向迭代器类>typedef ReverseIterator<iterator, T&, T*> reverse_iterator;//反向迭代器的类模板typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;//const反向迭代器的类模板//普通反向迭代器（const没写）reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}iterator begin(){return _head->_next;}iterator end(){return _head;}// const迭代器，需要是迭代器不能修改，还是迭代器指向的内容？// 迭代器指向的内容不能修改！const iterator不是我们需要const迭代器// T* const p1// const T* p2const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}//C++11的initializer_listlist(initializer_list<T> il){empty_init();for (auto& e : il){push_back(e);}}// lt2(lt1)list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}// 需要析构，一般就需要自己写深拷贝// 不需要析构，一般就不需要自己写深拷贝，默认浅拷贝就可以void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}// lt1 = lt3list<T>& operator=(list<T> lt){swap(lt);return *this;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}~list(){clear();delete _head;_head = nullptr;}/*void push_back(const T& x){Node* newnode = new Node(x);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;}*/void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}void insert(iterator pos, const T& val){Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;// prev newnode cur;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;_size--;return iterator(next);}size_t size() const{return _size;}bool empty(){return _size == 0;}private:Node* _head;size_t _size;};
}

ReverseIterator.h文件

#pragma once// 所有容器的反向迭代器
// 迭代器适配器
namespace bit
{// vector<T>::iterator// list<T>::iteratortemplate<class Iterator, class Ref, class Ptr>struct ReverseIterator{// typedef ReverseIterator<T, T&, T*>// typedef ReverseIterator<T, const T&, const T*>typedef ReverseIterator<Iterator, Ref, Ptr> rever_iterator;//将反向迭代器的类型重命名为rever_iteratorIterator _it;//定义一个正向迭代器类型的对象，并对其进行初始化和封装ReverseIterator(Iterator it)//反向迭代器的对象由正向迭代器的对象初始化:_it(it){}Ref operator*(){Iterator tmp = _it;//不改变原迭代器本身的指向，只想获取迭代器指向的下一个位置的数据的值return *(--tmp);}Ptr operator->(){return &(operator*());//返回该对象地址，返回值的类型是Ptr*，匿名指针}//++和--逻辑与正向迭代器相反//前置++rever_iterator& operator++()//返回类型是一个反向迭代器类类型的引用{--_it;return *this;}//前置--rever_iterator& operator--(){++_it;return *this;}bool operator!=(const rever_iterator& s){return _it != s._it;}};
}

test.cpp文件

#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
using namespace std;
#include"list.h"//list必须放在这，list.h中有需要以上头文件的地方，不改变其它代码的前提下放在上面几行会报错int main()
{bit::list<int> lt = { 1,2,3,4 };bit::list<int>::reverse_iterator rit = lt.rbegin();while (rit != lt.rend()){cout << *rit << " ";++rit;}cout << endl;return 0;
}

lt是一个被多参数实例化的一个list类类型的对象
rit是一个反向迭代器类型的对象，先调用lt中的rbegin函数，该函数又会调用end函数返回一个实例化好的普通正向迭代器类类型的匿名对象，然后该匿名对象会作为参数传递给ReverseIterator类模板，从而实例化出一个反向迭代器类类型的对象，最后返回给rit

调用lt的rend函数，经过一系列操作后返回一个反向迭代器类类型的匿名对象，rit和该匿名对象一起传入rit的!=重载函数中进行比较，该函数又会调用二者正向迭代器中的!=重载函数，最后将比较结果返回
*rit会调用rit中的*重载函数，生成一个临时的正向迭代器类型的对象tmp（_it是由正向迭代初始化的）--tmp调用正向迭代器的--重载函数令tmp指向的前一个对象，调用tmp的*重载函数返回获取的数据（运用临时对象原迭代器指向的对象不变）
++rit调用rit的++重载函数，先调用_it的--重载函数将_it指向前一个对象并返回更新后的_it，最后++重载函数返回更新后的_it