在本文开始之前,先明晰几个
关键词
的含义(T : 模板参数):
- Ref : T& / const T&
- Ptr : T* / const T*
一、反向迭代器设计的上帝视角
我们希望将 反向迭代器
设计成一种适配器——传 list::iterator 得到 list 的反向迭代器,传 vector::iterator 得到 vector 的反向迭代器。
template<class Iterator>
struct ReverseIterator
{Iterator cur;ReverseIterator(const Iterator& it):cur(it){}
};
STL 中,(正向)迭代器和反向迭代器是一种对称设计——rend() == begin() ,rbegin() == end() :
对于反向迭代器重载++ / – ,我们只需要复用正向迭代器的 – / ++ 即可。
不过,需要注意的是,反向迭代器调用 it.operator*() 应取到 it 的前一个位置的数据(取数据时,不改变 it 的位置)。
二、运算符重载细节介绍
为了使我们的反向迭代器能快速用起来,优先实现 ++ , * , -> , != 等功能,其余以此类推。
- 重载 ++
template<class Iterator>
struct ReverseIterator
{ReverseIterator<Iterator>& operator++(){--cur;return *this;}ReverseIterator<Iterator> operator++(int){Iterator tmp = cur;--cur;return tmp;// 存在隐式类型转换 <--> ReverseIterator<Iterator>(tmp);}
};
“为什么前置++ 的返回值不能是 cur ?”
error C2440: “return”: 无法从“Iterator”转换为“ReverseIterator<int *> &”
- 重载 * :引入一个模版参数 Ref
template<class Iterator, class Ref>
struct ReverseIterator
{Ref operator*(){Iterator tmp = cur;--tmp;return *tmp;}
};
当 tmp 的类型是 list::iterator,我们调用的 --tmp; return *tmp;
,编译器会调用 list 迭代器的运算符重载。
- 重载 ->
template<class Iterator, class Ref, class Ptr>
struct ReverseIterator
{Ptr operator->(){return &(operator*());}
};
- 重载 !=
template<class Iterator, class Ref, class Ptr>
struct ReverseIterator
{bool operator!=(const ReverseIterator<Iterator, Ref, Ptr>& l){return cur != l.cur;}
};
ReverseIterator<Iterator, Ref, Ptr>
太长太过复杂,我们可以利用 typedef 进行简化。
template<class Iterator, class Ref, class Ptr>
struct ReverseIterator
{typedef ReverseIterator<Iterator, Ref, Ptr> Self;bool operator!=(const Self& l){return cur != l.cur;}
};
PS: typedef ...
应放在 public
区域,否则非成员函数无法使用 typedef 后的命名。
全部代码:
template<class Iterator, class Ref, class Ptr>
struct ReverseIterator
{Iterator cur;typedef ReverseIterator<Iterator, Ref, Ptr> 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*());}
};