‍博主名称鱼子星_✅数据结构专栏【数据结构】✅算法竞赛专栏【算法竞赛】✅C系列专栏【C从零开始系列】前言如果将当代处于叛逆期的青年和父母说成是“对着干”的关系那么我们就可以将C中迭代器和反向迭代器看成是“父母”和“叛逆期的青年”。没错C中反向迭代器和普通迭代器的关系就是反着来那是怎么个“反”呢其实就是在遍历方向上是反着的即反向迭代器的的效果和普通迭代器--的效果一样普通迭代器是往容器后面走而反向迭代器则是往容器前面走。本篇文章主要的核心是讲解反向迭代器的实现如果对反向迭代器还有不理解的地方可以看我 【C】string上string的基本使用 这篇文章这篇文章更详细的讲解了反向迭代器“反”在哪里以及其使用方式在掌握了反向迭代器的和普通迭代器的区别和使用后再来学习本文反向迭代的实现也不晚。目录前言一. 反向迭代器的实现原理1.1 适配器的设计模式1.2 使用运算符重载小结二. 反向迭代器的实现2.1 反向迭代器的框架2.2 反向迭代器成员函数的实现2.3 反向迭代器在类中的实例化三. 总结一. 反向迭代器的实现原理1.1 适配器的设计模式反向迭代器的实现和stackqueue的底层实现一样使用了适配器的设计模式即可以自行的选择它的底层是什么但是反向迭代器使用的适配器就不是容器了而是迭代器。这里要注意将迭代器和反向迭代器进行区分迭代器就是平常使用的iterator而反向迭代器是reverse_iterator。前面既然说了反向迭代器和迭代器之间是对着干的关系那为什么反向迭代器的实现还是可以使用迭代器呢原因在于虽然说反向迭代器和迭代器的遍历方向和遍历结果是相反的但是它们本质上都还是在遍历容器所以底层的实现是可以直接复用的且除了没有迭代器的容器其它所有的容器都实现了迭代器直接复用这些实现好的迭代器也可以减少代码量提升程序的可读性。下面我们来看 sgi3.0 版本的STL源码中对于反向迭代器实现的部分#ifndef__STL_LIMITED_DEFAULT_TEMPLATEStemplateclassRandomAccessIterator,classT,classReferenceT,classDistanceptrdiff_t#elsetemplateclassRandomAccessIterator,classT,classReference,classDistance#endifclassreverse_iterator{typedefreverse_iteratorRandomAccessIterator,T,Reference,Distanceself;protected:RandomAccessIterator current;public:reverse_iterator(){}explicitreverse_iterator(RandomAccessIterator x):current(x){}};这段代码是随机迭代器类型的反向迭代器可以看到其模板参数中的RandomAccessIterator就是适配器的接口可以使用任意的随机迭代器作为参数传递。而从类中唯一的成员变量current不难推断出反向迭代器的底层实现依靠的也就是作为模板参数传递的迭代器。反向迭代器的不仅仅只有这一个版本还有一个只有一个模板参数的版本见图 1-1它只传递了一个模板参数是因为用到了迭代器萃取的方法而再另外一个版本就是传递四个模板参数的双向迭代器的版本见图 1-2。图 1-1 一个模板参数实现的反向迭代器图 1-2 四个模板参数实现的双向反向迭代器1.2 使用运算符重载不过如果仅仅只是将迭代器作为反向迭代器的底层还不够因为反向迭代器的遍历方向要和迭代器相反。举个例子假设此时有数据1,2,3,4,5此时各有一个迭代器和反向迭代器指向3这两个迭代器都执行操作反向迭代器会指向2迭代器会指向4。所以反向迭代器实现的另外一个关键点就是运算符重载通过运算符重载使得反向迭代器和迭代器的遍历方向相反才是真正的形成了反向迭代器。小结反向迭代器的实现也使用了适配器的设计模式它的底层是通过复用迭代器来实现通过运算符重载实现与迭代器遍历的方向相反的反向迭代器简单来说反向迭代器的实现就是将迭代器类型进行封装再重载出和迭代器名字相同效果相反的函数就是为反向迭代器。二. 反向迭代器的实现2.1 反向迭代器的框架这里模拟实现的反向迭代器为四个模板参数的版本的不过这里不对随机迭代器和双向迭代器进行区分因为如果是双向迭代器的反向迭代器要使用-等操作时它自身的迭代器就会报错。这又印证了用迭代器做反向迭代器的底层的好处。namespaceyzx{templateclassIterator,classT,classRef,classPtrclassreverse_iterator{typedefreverse_iteratorIterator,T,Ref,PtrSelf;public:reverse_iterator(Iterator it)// 构造函数 只能使用迭代器类型进行构造:_it(it){}private:Iterator _it;//成员遍历 以迭代器类型为底层实现反向迭代器};}2.2 反向迭代器成员函数的实现Selfoperator(){--_it;return*this;}Selfoperator(int){Selftmp(*this);--_it;returntmp;}Selfoperator--(){return_it;}Selfoperator--(int){Selftmp(*this);_it;returntmp;}booloperator(constSelfrit){return_itrit._it;}booloperator!(constSelfrit){return_it!rit._it;}Refoperator*(){Iteratortmp(_it);return*(--tmp);}Ptroperator-(){return(operator*());}这里讲解一下opreator*为什么不是直接解引用_it而是解引用 _it的前一个位置这是为了让反向迭代器和迭代器完成保持对称的关系所设定的。这里对称的意思是让rend和begin指向同一个位置rbegin和end指向同一个位置如图 2-1而因为普通迭代器end指向的位置没有有效元素只有在它的前一个位置才开始有有效元素且rbegin返回的迭代器解引用得到的是最后一个元素的值所以此时operator*需要先--tmp再去解引用才能拿到正确的值。图 2-1 反向迭代器和迭代器保持的对称性2.3 反向迭代器在类中的实例化typedefreverse_iteratoriterator,T,T,T*reverse_iterator;typedefreverse_iteratorconst_iterator,T,constT,constT*const_reverse_iterator;// 反向迭代器reverse_iteratorrbegin(){returnreverse_iterator(end());}reverse_iteratorrend(){returnreverse_iterator(begin());}// const反向迭代器const_reverse_iteratorrbegin(){returnconst_reverse_iterator(end());}const_reverse_iteratorrend(){returnconst_reverse_iterator(begin());}三. 总结反向迭代器的本质就是复用各个容器的普通迭代器或者说将普通迭代器进行封装。当使用反向迭代器时就在内部调用普通迭代器的--以此来达到反向遍历的效果。同时为了确保反向迭代器与迭代器完全”相反“我们让rbegin endrend begin而要维护这个效果就得改变解引用的逻辑提前一个位置解引用刚好使得各个位置的值可以正常拿到。