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

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

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

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

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

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

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

  

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

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

  

  二、运算符重载细节介绍

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

  • 重载 ++

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

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

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

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

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

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

      • 重载 ->

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

        • 重载 !=

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

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

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

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

          全部代码：

          template
          struct 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*());
          	}
          };