【C++】STL——反向迭代器的模拟实现：迭代器适配器

@[TOC]

前言

<font color = black>反向迭代器的使用相信大家都已经比较熟悉了，那我们这篇文章具体讲什么呢？ 🆗，这篇文章我们重点来讲一下反向迭代器的模拟实现。 那为什么我们之前不和正向迭代器放在一块讲呢？为什么要等到我们讲完了容器适配器再来讲反向迭代器的模拟实现呢？ 那这个问题我相信学完这篇文章大家就明白了。

1. list 的反向迭代器模拟实现

首先我们来回看一下我们之前模拟实现list的代码：

<font color = black>这是我们之前写的list的正向迭代器。

那现在大家思考一个问题：单从使用的角度来看，反向迭代器和正向迭代器有什么区别？

<font color = black>其实区别好像也不是很大，就是正向迭代器的++是从前往后走，而反向迭代器的++是从后往前走，那对于list来说正向++是_node = _node->_next;，那反向就应该是_node = _node->_prev;，反过来嘛。 当然如果支持- -的话- -也是反过来嘛。 然后其它的解引用，判断是否相等啥的不就是一样的操作了嘛。

所以，我们是不是就可以这样来实现反向迭代器：

<font color = black>直接把正向迭代器的代码拷贝一份，然后名字改一下，++和- -的操作改一下就行了。 然后list里面： 把反向迭代器的类型放进去。 然后是不是还要提供rbegin和rend啊： 那rbegin应该返回最后一个元素的迭代器 rend应该返回 第一个元素的前一个，那对于list来说就是头结点嘛 那对应的代码就是这样。

哦豁，那我们的反向迭代器不就写好了嘛！

<font color = black>试一下： 哎呀，是不是没问题啊。 那这样看来，要实现一个反向迭代器好像也不难啊。

2. 思考

但是呢：

<font color = black>此时，我们跟那些高手们，大佬们的差距就体现出来了，上面这种方法可能是我们大多数人最先想到的一种比较简单的方法。 虽然好像也可以；但是，有没有什么缺陷呢？ 🆗，这样写的话代码是不是比较冗余啊： 除了圈出来的部分这两类是不是没什么差别啊。 那想要进步的话，看优秀的代码是一种很好的方法，那我们接下来就来看一下真正的大佬写的代码是怎么样的。

3. 库里面反向迭代器的实现——迭代器适配器

🆗，我们来看一下库里面list的迭代器是如何实现的

<font color = black> 我们看到，这里的反向迭代器包括const版本的，它们都是对reverse_iterator这个类模板的一个typedef，但是它们的模板参数却是传的正向迭代器。 这是怎么回事啊？而且我们在当前stl_list.h这个头文件里并没有找到reverse_iterator这个类模板的定义！ 那我们就需要继续去源码里面找，所以看源码其实并不是一件舒服的事情，或者说是比较痛苦的。 那reverse_iterator这个类模板的实现其实是在另一个头文件stl_iterator.h里面： 那reverse_iterator这个类呢，其实是一个适配器，是一个迭代器适配器。 即reverse_iterator是对普通的正向迭代器进行了一个适配，进行了一个封装。 但是库里面实现的是比较复杂的，涉及一个迭代器萃取的东西，这个我们可以不用管。 我们后面实现会简化一点。 那我们来大致看一下它是怎么实现的： 那它封装正向迭代器的话，反向的++就是正向的- -嘛，反向的- -就是正向的++。这些我们都好理解。

但是我们看这个：

<font color = black> 欸！它的解引用怎么不是返回当前结点的值啊，为什么返回的是- 1之后再解引用的值？ 那按照我们上面的分析和理解，除了++和- -这些操作之外，其它的解引用，判断相等不相等这些是不是可以不用动啊。 那它这里是怎么搞的呢？跟我们上面的实现有什么不同吗？ 那这时候我们就要去看它里面的实现了，我们回到stl_list.h看到它的rbegin和rend是这样的： rbegin 是end的位置， rend 是begin的位置，我们拿begin和end来对比一下： 它们对应的位置是这样的： 那这样我们就看出来了，库里面应该是想追求一个对称。

但是如果这样实现的话：

<font color = black>反向迭代器在解引用的时候如果还是直接去它对应的那个位置是不是就出问题了，就拿rbeign来说，我们看： 如果直接取rbegin解引用的值，是不是就取到头结点的值了，但是正确的情况rbegin解引用是不是拿到的是最后一个元素的值。

那它这里怎么解决呢？

<font color = black>就是上面我们看到的： 它的解引用是不是返回的是-1之后的值啊，正向迭代器-1就是取prev嘛，头结点的prev是不是就正好是最后一个元素啊。 那现在大家应该就理解这里的解引用为什么这样写了。 那对应这个图的话： 走到5的话，解引用访问的是4，到4访问的是3，3对应2，2对应1，走到1等于rend了，就结束了。

那了解了库里面的实现机制之后，我们就来按照库里面的方式来实现一下。

4. 反向迭代器模拟实现的改进——适配器模式

接下来我们按照库里面的方式来实现一下：

namespace yin
{
    template <class Iterator>
    struct Reverse_Iterator
    {
        typedef Reverse_Iterator<Iterator> self;
        Iterator _cur;
​
        Reverse_Iterator(Iterator it)
            :_cur(it)
        {}
​
        self& operator++()
        {
            --_cur;
            return *this;
        }
        self operator++(int)
        {
            self tmp(*this);
            --_cur;
            return tmp;
        }
​
        self& operator--()
        {
            ++_cur;
            return *this;
        }
        self operator--(int)
        {
            self tmp(*this);
            ++_cur;
            return tmp;
        }
​
        bool operator!=(const self& s)
        {
            return _cur != s._cur;
        }
    };
}

<font color = black>首先上面这段代码大家应该都能看得懂，我就不过多解释了，上面我们已经实现了构造、++、- -和！=。

然后我们实现一下解引用*：

<font color = black>那我们这里按库里面走，经过上面我们的分析我们知道这里解引用返回的是- -之后的值。 这样做。 但是这里的返回值是不是有点难搞啊，普通对象解引用返回引用，const对象解引用返回const引用。 那这个问题我们之前是不是提出了比较好的解决方式啊，可以增加一个模板参数去控制。这里我们不按库里面的方法去走了，它里面实现的比较复杂，其实它用我们这个方法也能搞，但它考虑到其它的一些原因搞的比较复杂，我们不用管。 当然我们之前讲的由于 重载->的缘故是不是又增加一个模板参数Ptr。我们现在还没重载->，不过可以也加上。

那现在之前我们单独写的那个__list_reverse_iterator的那个类就不需要了，我们这样搞：

<font color = black> 然后rbegin和rend也要改一下： 那写到这里其实就好了，来试一下： 🆗，已经可以了。

那实现好了，我们再来探讨一点东西。

5. 适配器模式的实现——一劳永逸

我们刚才按库里面的方式，即适配器的模式又把我们的反向迭代器实现了一下。

但是呢：

<font color = black>大家可能会提出这样的疑问： 我们后面的改进，按照适配器模式去重新实现，与之前我们自己的方法相比，好像也没有牛🐂到那里去啊？ 不还是需要我们自己手动去写一个类嘛。

那为什么还要这样搞呢？

<font color = black>🆗，那接下来就给大家解释一下这样做真正的牛逼之处： 大家想一下，对于我们的list来说，我们使用最开始我们自己的方法去实现反向迭代器（拷贝一份正向迭代器的代码，进行一些简单修改），确实也可以。 但是，如果是vector呢？ 我们还可以用那种方法去搞吗？ 是不是就不行了啊，因为我们vector的迭代器是怎么搞的？ 是不是直接使用的原生指针啊（因为原生指针的行为 完全符合我们的需求），只不过进行了一下typedef：  ++和- -这些我们都不需要自己去重载，因为原生的行为就符合需求。 那这样的话我们就没法像上面那样去搞了。

但是对于适配器的实现方式：

<font color = black>你给我一个list的正向迭代器，我可以给你适配出list的反向迭代器，那如果给一个vector的正向迭代器，能否适配出vector的反向迭代器呢？ 🆗，当然也是可以的。 回想我们之前学的容器适配器，它们对应的底层容器仅限一种吗？ 不是的，是不是只要支持指定的那些操作就可以作为其底层的适配容器啊。 那我们这里的迭代器适配器Reverse_Iterator是不是只要对应容器的迭代器支持++和--操作就可以进行适配啊。（因为里面反向的++需要复用正向的- -，反向- -复用正向++） 所以，对于任何一个容器，只要迭代器至少是双向的，都可以用Reverse_Iterator这个类模板去适配出其反向的迭代器。 那我们常见的这些容器什么vector，list，string的反向迭代器不就都可以搞定了嘛。

所以，现在大家体会到了吗？

当我们还停留在思考去如何实现list的迭代器的时候，人家考虑的已经是如何做到一劳永逸，搞定所有容器的反向迭代器。 这就是我们和真正的大佬，高手之间的差距。

那我们来试一下吧，把vector的反向迭代器也搞出来：

<font color = black>那有了Reverse_Iterator这个迭代器适配器的模板类，我们现在想要适配出vector的反向迭代器，怎么搞？ 很简单： 然后就可以使用了： 是不是就行了。 我Reverse_Iterator是一个类模板，你给我任何容器的正向迭代器，只要支持++和- -，我就给你适配出反向迭代器来。

🆗，这才是它真正的牛逼之处。

6. 源码展示

6.1 iterator.h

#pragma once
​
namespace yin
{
    template <class Iterator, class Ref, class Ptr>
    struct Reverse_Iterator
    {
        typedef Reverse_Iterator<Iterator, Ref, Ptr> self;
        Iterator _cur;
​
        Reverse_Iterator(Iterator it)
            :_cur(it)
        {}
​
        Ref operator*()
        {
            Iterator tmp = _cur;
            --tmp;
            return *tmp;
        }
​
        self& operator++()
        {
            --_cur;
            return *this;
        }
        self operator++(int)
        {
            self tmp(*this);
            --_cur;
            return tmp;
        }
​
        self& operator--()
        {
            ++_cur;
            return *this;
        }
        self operator--(int)
        {
            self tmp(*this);
            ++_cur;
            return tmp;
        }
​
        bool operator!=(const self& s)
        {
            return _cur != s._cur;
        }
    };
}

6.2 list.h

#pragma once
#include <assert.h>
#include <algorithm>
#include "iterator.h"
namespace yin
{
    template <class T>
    struct __list_node
    {
        __list_node<T>* _next;
        __list_node<T>* _prev;
        T _data;
        __list_node(const T& x = T())
            :_next(nullptr)
            , _prev(nullptr)
            , _data(x)
        {}
    };
    template <class T, class Ref, class Ptr>
    struct __list_iterator
    {
        typedef __list_node<T> node;
        typedef __list_iterator<T, Ref, Ptr> self;
        node* _node;
        __list_iterator(node* n)
            :_node(n)
        {}
        Ref operator*()
        {
            return _node->_data;
        }
        Ptr operator->()
        {
            return &_node->_data;
        }
        self& operator++()
        {
            _node = _node->_next;
            return *this;
        }
        self operator++(int)
        {
            self tmp(*this);
            _node = _node->_next;
            return tmp;
        }
        self& operator--()
        {
            _node = _node->_prev;
            return *this;
        }
        self operator--(int)
        {
            self tmp(*this);
            _node = _node->_prev;
            return tmp;
        }
        bool operator!=(const self& s)
        {
            return _node != s._node;
        }
        bool operator==(const self& s)
        {
            return _node == s._node;
        }
    };
    /*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;
        }
    };*/
    /*template <class T>
    struct __list_const_iterator
    {
        typedef __list_node<T> node;
        typedef __list_const_iterator<T> self;
        node* _node;
        __list_const_iterator(node* n)
            :_node(n)
        {}
        const T& operator*()
        {
            return _node->_data;
        }
        self& operator++()
        {
            _node = _node->_next;
            return *this;
        }
        self operator++(int)
        {
            self tmp(*this);
            _node = _node->_next;
            return tmp;
        }
        self& operator--()
        {
            _node = _node->_prev;
            return *this;
        }
        self operator--(int)
        {
            self tmp(*this);
            _node = _node->_prev;
            return tmp;
        }
        bool operator!=(const self& s)
        {
            return _node != s._node;
        }
        bool operator==(const self& s)
        {
            return _node == s._node;
        }
    };*/
    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;
        typedef Reverse_Iterator<iterator, T&, T*> reverse_iterator;
        typedef Reverse_Iterator<const_iterator, const T&, const T*> const_reverse_iterator;
​
        //typedef __list_reverse_iterator<T, T&, T*> reverse_iterator;
        //typedef __list_const_iterator<T> const_iterator;
​
        /*reverse_iterator rbegin()
        {
            return reverse_iterator(_head->_prev);
        }
        reverse_iterator rend()
        {
            return reverse_iterator(_head);
        }*/
        reverse_iterator rbegin()
        {
            return reverse_iterator(end());
        }
        reverse_iterator rend()
        {
            return reverse_iterator(begin());
        }
        const_iterator begin()const
        {
            return const_iterator(_head->_next);
        }
        const_iterator end()const
        {
            return const_iterator(_head);
        }
        iterator begin()
        {
            return iterator(_head->_next);
        }
        iterator end()
        {
            return iterator(_head);
        }
        void empty_initialize()
        {
            _head = new node;
            _head->_next = _head;
            _head->_prev = _head;
        }
        list()
        {
            empty_initialize();
        }
        template <class Iterator>
        list(Iterator first, Iterator last)
        {
            empty_initialize();
​
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }
        /*list(const list<T>& l)
        {
            empty_initialize();
            for (auto e : l)
                push_back(e);
        }*/
        void swap(list<T>& l)
        {
            std::swap(_head, l._head);
        }
        list(const list<T>& l)
        {
            empty_initialize();
            list<T> tmp(l.begin(), l.end());
            swap(tmp);
        }
        list<T>& operator=(list<T> l)
        {
            swap(l);
            return *this;
        }
        ~list()
        {
            clear();
            delete _head;
            _head = __nullptr;
        }
        void clear()
        {
            iterator it = begin();
            while (it != end())
            {
                //it = erase(it);
                erase(it++);
            }
        }
        void push_back(const T& x)
        {
            //node* newnode = new node(x);
            ////找尾
            //node* tail = _head->_prev;
            ////链接
            //_head->_prev = newnode;
            //newnode->_next = _head;
            //tail->_next = newnode;
            //newnode->_prev = tail;
​
            insert(end(), x);
        }
        void push_front(const T& x)
        {
            insert(begin(), x);
        }
        void insert(iterator pos, const T& x)
        {
            node* cur = pos._node;
            node* prev = cur->_prev;
​
            node* newnode = new node(x);
​
            prev->_next = newnode;
            newnode->_prev = prev;
            newnode->_next = cur;
            cur->_prev = newnode;
        }
        iterator erase(iterator pos)
        {
            assert(pos != end());
            node* prev = pos._node->_prev;
            node* next = pos._node->_next;
​
            prev->_next = next;
            next->_prev = prev;
            delete pos._node;
​
            return iterator(next);
        }
        void pop_back()
        {
            erase(--end());
        }
        void pop_front()
        {
            erase(begin());
        }
        void print_list(const list<T>& l)
        {
            for (list<T>::const_iterator it = l.begin(); it != l.end(); ++it)
            {
                //(*it)++;
                cout << *it << " ";
            }
            cout << endl;
        }
    private:
        node* _head;
    };
}

6.3 测试

#include <iostream>
using namespace std;
#include "list.h"
​
int main()
{
    yin::list<int> l;
    l.push_back(1);
    l.push_back(8);
    l.push_back(4);
    l.push_back(7);
    l.push_back(-3);
    for (yin::list<int>::reverse_iterator rit = l.rbegin(); rit != l.rend(); ++rit)
    {
        cout << *rit << " ";
    }
    cout << endl;
    return 0;
}

我的gitee链接: link