💭 写在前面

上一章讲解 list 模拟实现时，我们简单的提到了反向迭代器，我们说反向迭代器其实就是对正向迭代器的一种封装 —— 适配器模式（配接器模式）。当时我们做的是简单的了解，本章我们就来探讨这一部分的知识。

0x00 引入：什么是适配器

上一章讲解 list 迭代器的实现时，我们提到了反向迭代器的实现。

💬 代码：reverse_iterator （我们自己实现的）

namespace chaos
{
  /* 定义反向迭代器 */
  template <class Iterator>
  class reverse_iterator {
  typedef reverse_iterator<Iterator, Ref, Ptr> self;
  public:
  reverse_iterator(Iterator it)
    :_it(it)
  {}
  Ref operator*() {
    //return *_it;
    Iterator prev = _it;
    return *--prev;
  }
  Ptr operator->() {
    return &operator*();
  }
  self& operator++() {
    --_it;
    return *this;
  }
  self& operator--() {
    ++_it;
    return *this;
  }
  bool operator!= (const self& rit) const {
    return _it != rit._it;
  }
  private:
  Iterator _it;
  };
}

❓ 思考：我们先来讨论一个问题，什么是迭代器适配器？

想了解这里的 "适配器"，我们不如先去看看电源适配器，看完后再去理解可能会更好：

（电源适配器）

【百度百科】电源适配器又叫外置电源，是小型便携式电子设备及电子电器的供电电压变换设备，常见于手机、液晶显示器和笔记本电脑等小型电子产品上。

电源适配器是进行 "转换" 的，它本质上可以理解为是一个变压器。

标准家庭用电电压为 ，我们设备用电其实并不需要这么高，

而电源适配器可以使较高的交流电压降低到合适于手机电池的直流工作电压。

也就是说，电源适配器是用来 "转换" 的。

 👉  

一样的道理，上一章我们提到过，反向迭代器和正向迭代器非常像！

🔍 区别： 反向迭代器和正向迭代器加加的方向不一样（唯一区别）。

（即正向迭代器 ++ 是向后走，反向迭代器 ++ 是向前走）

基于这一系列的原因，在实现反向迭代器的时，没有必要像正向迭代器这样去包装并重新实现。

💬 举个例子：

我们可以对其进行封装地 "转换" ，比如我们需要 list 的反向迭代器，

我们将 list 的正向迭代器传给 Iterator，来实例化 Iterator。

然后通过包装转换出你需要的 list 的反向迭代器：

namespace chaos
{
  /* 反向迭代器 */
  template <class Iterator>
  class reverse_iterator {
  typedef reverse_iterator<Iterator> self;
  public:
  reverse_iterator(Iterator it)
    : _it(it) 
  {}

如果你 vector 需要反向迭代器，那就把 vector 的正向迭代器传给 Iterator，

它就可以通过正向迭代器转换出 vector 的反向迭代器。

也就是说，我们实现的反向迭代器并包装的这个类，不是针对某个容器而是针对所有容器的。

任何一个容器只要你实现了正向迭代器，就可以通过其适配出反向迭代器。

它的本质是一种复用，是一种适配与转换。这就是迭代器适配器！

0x01 反向迭代器的错位访问

上一章我们提到过 operator* 这里返回的是*--prev，是一种有意的 "错位" 。

它解引用取的不是当前位置，而是前一个位置。

对于 list 而言，正向迭代器的 begin 和 end 位置如下：

那我们的反向迭代器的 rbegin 和 rend 在哪呢？按我们的常理来说应该是这样的：

rbegin 和 rend 是和 end 和 begin 是相对称的形式设计的，

你的 end 就是我的 rbegin，你的 begin 就是我的 rend。

这时就产生了一个错位的问题，我们解引用的时候会对不上，举个例子：

rit 在  rbegin() 的位置，rbegin 在头结点处，解引用取该位置么？

不，我们是反向迭代器啊，我们要取的是最后一个位置！取头结点干啥……

💡 解决方案：为了解决该问题，我们在 operator* 上动手脚，让其返回 *--prev：

这样取的就是前一个位置了，rbegin() 位置的前一个位置正是我们想要取的地方！

0x02 利用内嵌类型实现反向迭代器

实际上，STL3.0 的反向迭代器只有一个模板参数：

而我们上一章模拟实现 list 的反向迭代器时，设计了 3 个模板参数

这是因为在上一章为了更方便地区讲解 list 的模拟实现，我们将其简化了。

库里面的实在是让人头皮发麻，我们现在来学习下库里面是如何实现的：

它没有传 Ref 和 Ptr，也就意味着不能显式地去传，自己去控制（详细请阅读上一章内容）。

比如，如果你是普通迭代器的反向迭代器，传的就是 T& 和 T* ：

如果你是 const 迭代器的反向迭代器，传的就是 const T& 和 const T* ：

我们这么做是为了更清楚地表示，降低学习的成本。

而库中采用了一种更难的方式去实现，不传 Ref 和 Ptr 这两个模板参数，只用了一个模板参数。

这就意味着要去取 pointer 和 reference，因为它们要做 operator* 和 operator-> 的返回值。

❓ 而这里只有迭代器 Iterator，我们该怎么去取呢？

💡 大哥是这么做的，他在其中定义了一个内嵌类型：

把 Ptr 和 Ref 定义成了 pointer 和 reference，这样我们就可以从内嵌类型中去取这个类型了。

💬 代码：不传 Ptr 和 Ref 这两个模板参数去实现反向迭代器

namespace chaos
{
  //template <class Iterator, class Ref, class Ptr>
  template <class Iterator>
  class reverse_iterator {
  typedef reverse_iterator<Iterator, Ref, Ptr> self;
  typedef Iterator::Ref reference;  // 取内嵌类型
  typedef Iterator::Ptr pointer;
  public:
  reverse_iterator(Iterator it)
    :_it(it)
  {}
    ...
    }
}

如果你自己试一试你就会发现一个问题：

Iterator 是一个模板参数，你要取模板参数中的内嵌类型 Ref，编译器这里就编不过去了。

如果你对模板参数取 typedef，没有任何问题。但是你要取它的内嵌类型，就有问题了：

因为编译器编译到这一块的时候，模板参数还没有实例化！

既然没有实例化，那编译器也不知道这个 Iterator 的类型是什么，typedef 一下没什么问题。

但是你去 : : 取 Iterator 里面的东西，模板都还没实例化，编译器怎么知道里面到底是什么呢？

那我们该怎么让编译器知道呢？

凡是要取一个模板、类模板或模板参数的内嵌类型（内部类），就可以用 typename：

对于现阶段而言，这种写法是有缺陷的。vector、string 的迭代器怎么适配？

这里在取内嵌类型，只有自定义类型才能在里面搞内嵌类型。如果是一个原生指针呢？

原生指针哪来的内嵌类型？这里不就抓瞎了么。

如果仅看这一部分的实现，自然还是三个模板参数更爽，自己控制。

但是 STL 是非常复杂的，它还要考虑去兼顾全局，不是说只有迭代器和容器，

像 vector、string 这样的容器的迭代器是原生指针，无法取内嵌类型。那么上面的方式就寄了。

0x03 浅谈迭代器萃取

基于这一系列的原因，STL 源码中使用了一个叫 "迭代器萃取" 的技术解决的。

📚 原理：再套一层，去萃取迭代器中的 reference 和 pointer（迭代器管理的数据中的 T& 和 T* 或 const T* 和 constT& 等取出来）。相当于把其他容器的迭代器传给 iterator_traits，在其中再套一层，对于链表而言最终还是要取：

对于 vector、string 这样的原生指针，iterator_traits 里有使用了一个技术 —— "模板特化技术"

大概意思是当你这里是原生指针时，这里会直接自己套一层取解决。萃取的本质就是特化。

（这里先了解一下，关于这里的深入实现我们后面模板的进阶章节会详细讲解）

（迭代器萃取的知识难度较大，我们后期再专门开一个章节去讲）

🔺 总结：list 用一个参数实现还行，但是 vector 和 string 这样的原生指针还是用一个参数去实现会牵扯到更复杂的迭代器萃取。就目前而言，学会实现 3 个模板参数的反向迭代器即可。