C++【STL】【反向迭代器】

目录

一、反向迭代器的简介

1.什么是反向迭代器

2.方向迭代器的实现

二、反向迭代器的相关问题

1.为什么在operator*中需要--迭代器

2.适配list的反向迭代器

3.适配vector的反向迭代器

4.迭代器的分类

5.迭代器萃取浅述

---

一、反向迭代器的简介

1.什么是反向迭代器

如果是正向迭代器就是从1->2->3->4->5，也就是正向迭代器的++是向右边走

但是我们的反向迭代器的++是向左边走，也就是5->4->3->2->1

void test_list1()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(5);
 
    //正向迭代器
    list<int>::iterator it = lt.begin();
    while (it != lt.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
 
    //反向迭代器
    list<int>::reverse_iterator rit = lt.rbegin();
    while (rit != lt.rend())
    {
        cout << *rit << " ";
        ++rit;
    }
    cout << endl;
}

2.方向迭代器的实现

普通思维：拷贝一份正向迭代器，修改一下，搞出我们的方向迭代器

大佬的思维：list是可以通过将遍历p.next变成p.prev，从而在++的时候实现反向迭代，

1.但是vector怎么办呢？因为vector的迭代器底层是原生指针，++就只会往后走。

vector的反向迭代器可以这样生成一个类，直接将++的方式重载成--，从而实现反向迭代

struct_vector_iterator
{
    T *_ptr;
    operator++()
    {
        --_ptr;
    }
}

2.采用复用（正向迭代器）的方式。

从我们下面的STL源码中可以看到我们的STL其实是采用复用正向迭代器的方式的 

一下是我们STL中关于反向迭代器的源码 

template <class Iterator>
class reverse_iterator 
{
protected:
  Iterator current;
public:
  typedef typename iterator_traits::iterator_category
          iterator_category;
  typedef typename iterator_traits::value_type
          value_type;
  typedef typename iterator_traits::difference_type
          difference_type;
  typedef typename iterator_traits::pointer
          pointer;
  typedef typename iterator_traits::reference
          reference;
 
  typedef Iterator iterator_type;
  typedef reverse_iterator self;
 
public:
  reverse_iterator() {}
  explicit reverse_iterator(iterator_type x) : current(x) {}
 
  reverse_iterator(const self& x) : current(x.current) {}
#ifdef __STL_MEMBER_TEMPLATES
  template <class Iter>
  reverse_iterator(const reverse_iterator& x) : current(x.current) {}
#endif /* __STL_MEMBER_TEMPLATES */
    
  iterator_type base() const { return current; }
  reference operator*() const {
    Iterator tmp = current;
    return *--tmp;
  }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
  pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
 
  self& operator++() {
    --current;
    return *this;
  }
  self operator++(int) {
    self tmp = *this;
    --current;
    return tmp;
  }
  self& operator--() {
    ++current;
    return *this;
  }
  self operator--(int) {
    self tmp = *this;
    ++current;
    return tmp;
  }
 
  self operator+(difference_type n) const {
    return self(current - n);
  }
  self& operator+=(difference_type n) {
    current -= n;
    return *this;
  }
  self operator-(difference_type n) const {
    return self(current + n);
  }
  self& operator-=(difference_type n) {
    current += n;
    return *this;
  }
  reference operator[](difference_type n) const { return *(*this + n); }  
}; 

二、反向迭代器的相关问题

1.为什么在operator*中需要--迭代器

这里我们观察到operator*，也就是解析迭代器所指向的数据，竟然需要先--迭代器，这是为什么呢？

我们的STL源码中的迭代器的是这样定义的

iterator begin() {return (link_type)(*node).next);}
iterator end(){ return node;}

 

这样就设计了一个对称的结构，正向迭代器的开始就是反向迭代器的结束，反向迭代器的开始就是正向迭代器的结束 

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

所以说我们的迭代器指针指向1前面的那个头结点的时候，将current的值赋给tmp,tmp--就到了5的位置然后将5的值返回，在5的位置的时候解引用得到的是4，在4位置解引用得到的是3，在3的位置解引用得到的是2，在2位置解引用，得到的是1，到了1，也就是我们rend()的位置也就结束了。

当然我们将rebegin()放在5的位置也是可以的，那样的话就不用--再解引用了，这两种方法都是可以的。

2.适配list的反向迭代器

这是定义在reverse_iterator中的代码

由于上面的1中已经介绍过为什么STL中国的源码采用先--在解引用的写法，所以我们下面的写法中，我们也是先--再引用。

#pragma once
 
namespace zhuyuan
{
    // 复用，迭代器适配器
    //Iterator是用来定义反向迭代器的模板的，
    // Ref是用来里定义反向迭代器的数据类型，是const类型的就是const类型的迭代器，不是const类型的，就不是const类型的迭代器
    // Ptr定义的是结构体指针的模板
    template<class Iterator, class Ref, class Ptr>
    struct __reverse_iterator
    {
        Iterator _cur;
        typedef __reverse_iterator RIterator;
 
        __reverse_iterator(Iterator it)
                :_cur(it)
        {}
 
        //反向迭代器的++就是--，这里我们需要重载一下
        RIterator operator++()
        {
            --_cur;
            return *this;
        }
        //反向迭代器--就是++，这里我们需要重载一下
        RIterator operator--()
        {
            ++_cur;
            return *this;
        }
 
        Ref operator*()
        {
            //return *_cur;
            //解引用是不能够改变当前的数据的，所以我们用一个tmp对象来拷贝一下
            auto tmp = _cur;
            --tmp;
            return *tmp;
        }
 
        Ptr operator->()
        {
            //这是一个结构体指针，
            //这两种写法是一样的
            //return _cur.operator->();
            return &(operator*());
        }
 
        bool operator!=(const RIterator& it)
        {
            return _cur != it._cur;
        }
    };
}

然后在我们的list.h中的list类中封装反向迭代器对象，然后再list.h引入我们上面的reverse_iterator.h文件

//封装正向迭代器
        typedef __list_iterator iterator;
        typedef __list_iteratorconst T&, const T*> const_iterator;
 
        //封装反向迭代器
        typedef __reverse_iterator reverse_iterator;
        typedef __reverse_iteratorconst T&, const T*> const_reverse_iterator;

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

测试代码

    void test_list1()
    {
        list<int> lt;
        lt.push_back(1);
        lt.push_back(2);
        lt.push_back(3);
        lt.push_back(4);
        lt.push_back(5);
 
        list<int>::iterator it = lt.begin();
        while (it != lt.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
 
        list<int>::reverse_iterator rit = lt.rbegin();
        while (rit != lt.rend())
        {
            cout << *rit << " ";
            ++rit;
        }
        cout << endl;
 
        it = lt.begin();
        while (it != lt.end())
        {
            *it *= 2;
            ++it;
        }
        cout << endl;
 
        for (auto e : lt)
        {
            cout << e << " ";
        }
        cout << endl;
    }

3.适配vector的反向迭代器

在我们的vector类中定义下面的方法

然后再定义引用#include "reverse_iterator.h"，也就是我们之前写的reverse_iterator.h文件

        typedef T* iterator;
        typedef const T* const_iterator;
 
        typedef __reverse_iterator reverse_iterator;
        typedef __reverse_iteratorconst T&, const T*> const_reverse_iterator;
 
        reverse_iterator rbegin()
        {
            return reverse_iterator(end());
        }
 
        reverse_iterator rend()
        {
            return reverse_iterator(begin());
        }

测试代码

void test_vector1()
    {
 
        vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
        v.push_back(5);
 
 
        vector<int>::iterator it = v.begin();
        while (it != v.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
 
 
        vector<int>::reverse_iterator rit = v.rbegin();
        while (rit != v.rend())
        {
            cout << *rit << " ";
            ++rit;
        }
        cout << endl;
 
    }

 

也就是说我们的rbegin()指向end()的位置也就是最后一个元素的下一个位置，解引用的时候，先--也就是到5的位置然后返回5，然后在5的位置，解引用的时候先--，到4的位置再返回4，以此类推，然后在2的位置解引用先--到1的位置，然后返回1，然后在1的位置到了rend()结束。 

4.迭代器的分类

这里我们的vector和list都是可以用我们上面写的reverse_iterator.h文件的，也就是说我们其实是可以实现大量的复用的！！

我们的反向迭代器中只要是正向迭代器中可以实现的，我们反向迭代器都可以实现。

反向迭代器：迭代器适配器，可以适配生成支持++和--的容器的反向迭代器。

一般的容器都是支持++的，但是--并不是所有的容器都支持的

（forward_list(单链表,forward是单向的意思，bidrectional是双向的意思)，unodered_map(哈希表)和unordered_set）

迭代器从功能的角度分类：

forward_list：只支持++（forward_list，unordered_map，unordered_set）

bidrectional：支持++也支持--（list,map,set）

random_access_iterator：除了支持++也支持--还支持+和-（比方说从第三个位置+5直接到了第八个位置）（vector,deque）

我们注意到 cplusplus的官方网站中写模板函数的时候也是按照迭代器的功能分类的

（这里的名称暗示你sort的容器得是随机迭代器，reverse的名称暗示你，sort的容器得是双向迭代器（当然随机迭代器也支持双向迭代器，其实是继承关系））

 

5.迭代器萃取浅述

这是stl_list中的部分源码

#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  typedef reverse_iterator const_reverse_iterator;
  typedef reverse_iterator reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  typedef reverse_bidirectional_iterator
  const_reference, difference_type>
  const_reverse_iterator;
  typedef reverse_bidirectional_iterator
  difference_type>
  reverse_iterator; 
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */

这是老版本中的定义，它将value_type和reference全部都传递过去

 也就是我们上面的自己写的

而在新的版本中，我们注意到它只将这里的迭代器传了过去

那按照我们的理解，那要是我们将自己写的代码中的ref和ptr去掉，那我们下面的两个函数就不知道应该返回什么类型了。

 这里就是用到了迭代器萃取。

萃取可以用来提高运算的效率。

适配器真正的特点就是实现了复用。也就是上层的封装，转换出我们想要的东西。