[C++]反向迭代器

目录

前言：

1 对反向迭代器的构造思想

2 实现反向迭代器

3 完整代码

---

前言：

        本篇文章主要介绍了STL容器当中的反向迭代器，可能有朋友会说：“反向迭代器有什么好学的？不一样还是迭代器吗，我正向能写出来，还写不出反向？”有这种想法的朋友那你可得好好的看看咯，相信这对你有很大的帮助。

1 对反向迭代器的构造思想

        以同类逻辑去考虑迭代器，我们反向迭代器应该与正向迭代器构造思想相同，正向迭代器的begin指向第一个数据，end指向最后一个数据的后一位，那么我们的反向迭代器也应该是rbegin指向倒数第一个数据，rend指向第一个数据的前一位，如下图：

         我相信大多数人对于第一次遇到反向迭代器的想法都是这样的，包括博主自己，这也没有任何的问题，同样是能够实现反向迭代器的功能，但是这不是重点，我们实现这个思想时，多数会向下方代码那样，我以list举例，以这样的想法我们就会构建出这样的反向迭代器。

template<class T, class Ref, class Ptr>
struct __list_reverse_iterator
{typedef list_node<T> node;typedef __list_reverse_iterator<T, Ref, Ptr> self;node* _node;__list_reverse_iterator(node* n):_node(n){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}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& s){return _node != s._node;}bool operator==(const self& s){return _node == s._node;}
};

        上述代码没有任何问题，博主也测试过能够实现反向迭代器的功能，但是呢看着这个代码是不是觉得很不爽啊，因为这反向迭代器通过这种另外封装一个类的方式，然后实现了一个与正向迭代器相互冗余的功能，这代码相似度太高了，写出来都觉得代码很挫，不好意思说出去是自己写的。

        基于此，请看看大佬是如何设计的吧。

         大佬干了啥，直接将正向迭代器作为反向迭代器的模板类型，在反向迭代器中重定义操作符，然后使用正向迭代器的功能，当然这个方式也是需要重新封装一个类，大伙还是看不出来有啥牛逼的，请继续往下看。

2 实现反向迭代器

代码：

template<class iterator, class Ref, class Ptr>
struct __list_reverse_iterator
{typedef __list_reverse_iterator<iterator, Ref, Ptr> Self;iterator _cur;__list_reverse_iterator(iterator it):_cur(it){}Ref operator*(){iterator temp = _cur;return *(--temp);}Self& operator++(){--_cur;return *this;}Self& operator--(){++_cur;return *this;}bool operator!=(const Self& ss){return _cur != ss._cur;}
};

        看到我们的代码，因为反向迭代器的类型是正向迭代器，所以我们需要在里面放置一个正向迭代器类型变量供使用。

        但是看到我们的反向迭代器构造了吗？我们对_cur变量赋初值等于iterator类型的it，但是it是怎么出来的？我们在使用反向迭代器的时候难道不是vv.rbegin();这种方式吗？我们有传递任何的数据吗？更何况还是一个正向迭代器类型的变量。

        此时就需要看到我们的rbegin函数了。

reverse_iterator rbegin()
{return reverse_iterator(end());
}
reverse_iterator rend()
{return reverse_iterator(begin());
}

        这样看可能不是很清楚，那我换一种方式表示：

reverse_iterator rbegin()
{
    return reverse_iterator(iterator(_head));
}

reverse_iterator rend()
{
    return reverse_iterator(iterator(_head->next));
}

        我们调用rbegin时，会实例化一个反向迭代器类，它通过正向迭代器去构造，正向迭代器通过结点指针构造。

        大家有注意到吗？这种实现方式的rbegin和rend指向我们数据的那个位置？和我们开头的思想相同吗？很明显不同，它的头指向了最后一个数据的下一个位置，它的尾指向了第一个位置，如下图。

         可是这样做的好处是什么？甚至我没有看到好处只看到了我之后*迭代器得到的数据都不对了，第一个数据都取不到了，但事实真的时是这样吗？回到代码中看：

Ref operator*()
{
     iterator temp = _cur;
     return *(--temp);
}

        我们在反向迭代器当中重定义*操作符函数下干了啥？我们创建了一个临时对象，将临时对象--在解引用，那么这样我们不就获取到了正确的数据了吗？所以这种构造思想没有错误。

        但是上面的道理大家都明白，好处在哪里？好了，重点到了！！

        看到上图，我们的begin对应的是rend，end对应的是rbegin，那么我们可以做一件什么事情呢？那就是反向迭代器类的参数传递可以通过正向迭代器的begin()、end()函数构建。也就是下方代码。

reverse_iterator rbegin()
{
    return reverse_iterator(end());
}
reverse_iterator rend()
{
    return reverse_iterator(begin());
}

         这也不是最重要的，最重要的是，我们将这份反向迭代器直接原封不动的放到vector当中，会有什么效果？你一定想不到，我们vector的反向迭代器也实现了！！

        如下：

namespace boqi
{template<class iterator, class Ref, class Ptr>struct __list_reverse_iterator{typedef __list_reverse_iterator<iterator, Ref, Ptr> Self;iterator _cur;__list_reverse_iterator(iterator it):_cur(it){}Ref operator*(){iterator temp = _cur;return *(--temp);}Self& operator++(){--_cur;return *this;}Self& operator--(){++_cur;return *this;}bool operator!=(const Self& ss){return _cur != ss._cur;}};template<class T>class vector{public://迭代器定义typedef T* iterator;typedef const T* const_iterator;typedef struct __list_reverse_iterator<iterator, T&, T*> reverse_iterator;typedef struct __list_reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;iterator begin(){return _start;}iterator end(){return _finish;}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}private://三个迭代器表示一个开辟空间数组的3个位置iterator _start;iterator _finish;iterator _end_of_storage;};
}

        看到，博主甚至连名字都没有更换，再看它是否能用。

测试代码：

void test9()
{yf::vector<int> vv;vv.push_back(1);vv.push_back(2);vv.push_back(3);vv.push_back(4);yf::vector<int>::reverse_iterator rit = vv.rbegin();while (rit != vv.rend()){cout << *rit << " ";++rit;}cout << endl;
}

输出：

         看到了吗？我们的vector的反向迭代器直接就能用了，我们都知道vector和list的底层完全不同，通过大佬的这种方式实现，却将两个完全不同的迭代器完美的联系起来了，并且共用一份代码！而且不只是这两个容器可以用，任何由迭代器的容器都可以使用，因为只要你有迭代器，那一定支持++和--，而且它不关心你的正向迭代器是怎么实现的。对此我只能膜拜，大佬不愧是大佬。

3 完整代码

#pragma once#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
#include<assert.h>namespace yf
{template<class T>struct node{//结点类在list创建时分配数据node(const T& val = T()):next(nullptr), prev(nullptr), data(val){}//前结点、后结点、T类型数据struct node<T>* next;struct node<T>* prev;T data;};//迭代器类//Ref和Ptr分别是T&，和T*，目的是为了不让代码冗余，const T&，const T*template<class T, class Ref, class Ptr>struct __list_iterator{typedef struct node<T> Node;typedef struct __list_iterator<T, Ref, Ptr> self;//浅拷贝传入过来的结点指针，不需要去开辟新空间//因为我们要的就是原本的结点struct __list_iterator(Node* node):Pos(node){}//*迭代器返回结点内部的数据Ref operator*(){return Pos->data;}//到下一个结点，而不是结点指针的下一个位置self& operator++(){Pos = Pos->next;return *this;}self operator++(int){self temp = *this;Pos = Pos->next;return temp;}self& operator--(){Pos = Pos->prev;return *this;}self operator--(int){self temp = *this;Pos = Pos->prev;return temp;}//返回节点数据的地址Ptr operator->(){//Pos已经是结点了，但是如果需要访问的数据也是一个结构体//那么获取到了它的地址，就能用->去访问了return &Pos->data;}bool operator==(const self& val){return Pos == val.Pos;}bool operator!=(const self& val){return Pos != val.Pos;}Node* Pos;};//反向迭代器template<class iterator, class Ref, class Ptr>struct __list_reverse_iterator{typedef __list_reverse_iterator<iterator, Ref, Ptr> Self;iterator _cur;__list_reverse_iterator(iterator it):_cur(it){}Ref operator*(){iterator temp = _cur;return *(--temp);}Self& operator++(){--_cur;return *this;}Self& operator--(){++_cur;return *this;}bool operator!=(const Self& ss){return _cur != ss._cur;}};//带头双向循环链表template<class T>class list{public:typedef struct node<T> Node;typedef struct __list_iterator<T, T&, T*> iterator;typedef struct __list_iterator<T,const T&, const T*> const_iterator;typedef struct __list_reverse_iterator<iterator, T&, T*> reverse_iterator;typedef struct __list_reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;iterator begin(){//进入迭代器类当中去，然后传入起始值的数据初始化return iterator(_head->next);}iterator end(){//_head相当于循环里的迭代器最后一个数据的下一个//所以初始化就用_head去初始化return iterator(_head);}const_iterator begin() const{return const_iterator(_head->next);}const_iterator end() const{return const_iterator(_head);}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());}//构造时，有的对象是没有头结点的，所以需要帮忙开辟void Init_head(){_head = new Node;_head->next = _head;_head->prev = _head;}//无参list(){Init_head();}//拷贝list(const list<T>& val){Init_head();list<T> temp(val.begin(), val.end());std::swap(_head, temp._head);}//赋值重载list<T>& operator=(list<T> val) {std::swap(_head, val._head);return *this;}//迭代器区间构造template<class InputIterator>list(InputIterator first, InputIterator last){Init_head();while (first != last){push_back(*first);++first;}}//插入void insert(iterator pos, const T& val){Node* cur = pos.Pos;Node* NewNode = new Node(val);cur->prev->next = NewNode;NewNode->prev = cur->prev;NewNode->next = cur;cur->prev = NewNode;}//尾插void push_back(const T& val){iterator it = end();insert(it,val);}//头插void push_front(const T& val){iterator it = begin();insert(it,val);}	//删除void erase(iterator pos){assert(pos != end());Node* cur = pos.Pos;cur->prev->next = cur->next;cur->next->prev = cur->prev;delete cur;}//尾删void pop_back(){iterator it = end();erase(--it);}//头删void pop_front(){iterator it = begin();erase(it);}//判空bool empty(){return _head->next == _head;}//清空除头结点之外的所有结点void clear(){iterator it = begin();while (it != end()){erase(it++);}}//析构~list(){clear();delete _head;}private:Node* _head;};
}

---

        以上就是我对反向迭代器的全部理解，谢谢大家观看。