C++ 反向迭代器的设计与实现

在���文开始之前，先明晰几个 关键词 的含义（T : 模板参数）：

• Ref : T& / const T&
• Ptr : T* / const T*

  一、反向迭代器设计的上帝视角

  我们希望将 反向迭代器 设计成一种适配器——传 list::iterator 得到 list 的反向迭代器，传 vector::iterator 得到 vector 的反向迭代器。

  templatestruct ReverseIterator{Iterator cur;        ReverseIterator(const Iterator& it)        :cur(it)    {}};

  STL 中，（正向）迭代器和反向迭代器是一种对称设计——rend() == begin() ，rbegin() == end() ：

  对于反向迭代器重载++ / – ，我们只需要复用正向迭代器的 – / ++ 即可。

  不过，需要注意的是，反向迭代器调用 it.operator*() 应取到 it 的前一个位置的数据（取数据时，不改变 it 的位置）。

  二、运算符重载细节介绍

  为了使我们的反向迭代器能快速用起来，优先实现 ++ , * , -> , != 等功能，其余以此类推。

  • 重载 ++

    templatestruct ReverseIterator{    ReverseIterator& operator++()    {        --cur;        return *this;}        ReverseIterator operator++(int)    {        Iterator tmp = cur;        --cur;        return tmp;// 存在隐式类型转换  ReverseIterator(tmp);}};

    “为什么前置++ 的返回值不能是 cur ？”

    error C2440: “return”: 无法从“Iterator”转换为“ReverseIterator &”

    • 重载 * ：引入一个模版参数 Ref

      templatestruct ReverseIterator{    Ref operator*()    {        Iterator tmp = cur;        --tmp;        return *tmp;    }};

      当 tmp 的类型是 list::iterator，我们调用的 --tmp; return *tmp; ，编译器会调用 list 迭代器的运算符重载。

      • 重载 ->

        templatestruct ReverseIterator{    Ptr operator->()    {        return &(operator*());}};

        • 重载 !=

          templatestruct ReverseIterator{    bool operator!=(const ReverseIterator& l)    {        return cur != l.cur;}};

          ReverseIterator 太长太过复杂，我们可以利用 typedef 进行简化。

          templatestruct ReverseIterator{    typedef ReverseIterator Self;    bool operator!=(const Self& l)    {        return cur != l.cur;}};

          PS： typedef ... 应放在 public 区域，否则非成员函数无法使用 typedef 后的命名。

          全部代码：

          templatestruct ReverseIterator{Iterator cur;typedef ReverseIterator Self;ReverseIterator(const Iterator& it):cur(it){}Self& operator++(){--cur;return *this;}Self operator++(int){Iterator tmp = cur;--cur;return tmp;// 隐式类型转换}Self& operator--(){++cur;return *this;}Self operator--(int){Iterator tmp = cur;++cur;return tmp;}Ref operator*(){Iterator tmp = cur;--tmp;return *tmp;}bool operator!=(const Self& s){return cur != s.cur;}bool operator==(const Self& s){return cur == s.cur;}Ptr operator->()// -> 返回数据的地址{return &(operator*());}};