目录引言1.源码及框架分析2.实现反向迭代器老版本实现多模板参数迭代器新版本实现单模板参数迭代器结语引言在学反向迭代器之前需要先掌握封装迭代器以及适配器相关的内容如果是新版反向迭代器实现的话还需要懂模板相关内容主要是偏特化——迭代器萃取要用到这些内容我在这里就不反复叙述了C_stack和queue和priority_queue容器适配器-CSDN博客C_模板进阶-CSDN博客那么 话不多说接下来进入正文——————1.源码及框架分析SGI-STL3.0版本的源代码反向迭代器实现的核心源码在stl_iterator.h中反向迭代器是一个适配器各个容器中再适配出自己的反向迭代器我们先分析分析源码里反向迭代器是怎么实现的这边我们就主要分析vector和list的了我们把vectorlist以及stl_iterator.h的源码全都拉出来结合着看这是vector.h中条件编译的宏内部就是反向迭代器这是list的从这里我们可观察到如果定义了这个宏不管是vector.h中的反向迭代器还是list.h中的反向迭代器都是一个叫reverse_iterator的一个类模板搞出来的如果这个宏未定义vector的反向迭代器虽然和定义时候一样但是参数列表不一样有四个参数list的反向迭代器会变为由reverse_bidirectional_iterator这个类模板搞出来接下来我们去iterator源码中去找一找这俩个类模板用ctrlF快捷键找会方便点先是reverse_iterator的源码太长了截图会糊这里就放代码了在源码中的521行template class Iterator class reverse_iterator { protected: Iterator current; public: typedef typename iterator_traitsIterator::iterator_category iterator_category; typedef typename iterator_traitsIterator::value_type value_type; typedef typename iterator_traitsIterator::difference_type difference_type; typedef typename iterator_traitsIterator::pointer pointer; typedef typename iterator_traitsIterator::reference reference; typedef Iterator iterator_type; typedef reverse_iteratorIterator self; public: reverse_iterator() {} explicit reverse_iterator(iterator_type x) : current(x) {} reverse_iterator(const self x) : current(x.current) {} #ifdef __STL_MEMBER_TEMPLATES template class Iter reverse_iterator(const reverse_iteratorIter x) : current(x.current) {} #endif /* __STL_MEMBER_TEMPLATES */ iterator_type base() const { return current; } reference operator*() const { Iterator tmp current; return *--tmp; } #ifndef __SGI_STL_NO_ARROW_OPERATOR pointer operator-() const { return (operator*()); } #endif /* __SGI_STL_NO_ARROW_OPERATOR */ self operator() { --current; return *this; } self operator(int) { self tmp *this; --current; return tmp; } self operator--() { current; return *this; } self operator--(int) { self tmp *this; current; return tmp; } self operator(difference_type n) const { return self(current - n); } self operator(difference_type n) { current - n; return *this; } self operator-(difference_type n) const { return self(current n); } self operator-(difference_type n) { current n; return *this; } reference operator[](difference_type n) const { return *(*this n); } };接下来是lish.h中宏未定义时调用的类模板431行class reverse_bidirectional_iterator { typedef reverse_bidirectional_iteratorBidirectionalIterator, T, Reference, Distance self; protected: BidirectionalIterator current; public: typedef bidirectional_iterator_tag iterator_category; typedef T value_type; typedef Distance difference_type; typedef T* pointer; typedef Reference reference; reverse_bidirectional_iterator() {} explicit reverse_bidirectional_iterator(BidirectionalIterator x) : current(x) {} BidirectionalIterator base() const { return current; } Reference operator*() const { BidirectionalIterator tmp current; return *--tmp; } #ifndef __SGI_STL_NO_ARROW_OPERATOR pointer operator-() const { return (operator*()); } #endif /* __SGI_STL_NO_ARROW_OPERATOR */ self operator() { --current; return *this; } self operator(int) { self tmp *this; --current; return tmp; } self operator--() { current; return *this; } self operator--(int) { self tmp *this; current; return tmp; } };接下来是vector.h中宏未定义时候 调用的类模板准确来说是634行开始我这里从622行开始是为了给你们展示进入这一块内容的条件是那个宏未定义就是下面的第一行#else前面那俩个也是同理但篇幅问题前面俩个我就不放宏定义判断那部分源码了#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */ // This is the old version of reverse_iterator, as found in the original // HP STL. It does not use partial specialization. #ifndef __STL_LIMITED_DEFAULT_TEMPLATES template class RandomAccessIterator, class T, class Reference T, class Distance ptrdiff_t #else template class RandomAccessIterator, class T, class Reference, class Distance #endif class reverse_iterator { typedef reverse_iteratorRandomAccessIterator, T, Reference, Distance self; protected: RandomAccessIterator current; public: typedef random_access_iterator_tag iterator_category; typedef T value_type; typedef Distance difference_type; typedef T* pointer; typedef Reference reference; reverse_iterator() {} explicit reverse_iterator(RandomAccessIterator x) : current(x) {} RandomAccessIterator base() const { return current; } Reference operator*() const { return *(current - 1); } #ifndef __SGI_STL_NO_ARROW_OPERATOR pointer operator-() const { return (operator*()); } #endif /* __SGI_STL_NO_ARROW_OPERATOR */ self operator() { --current; return *this; } self operator(int) { self tmp *this; --current; return tmp; } self operator--() { current; return *this; } self operator--(int) { self tmp *this; current; return tmp; } self operator(Distance n) const { return self(current - n); } self operator(Distance n) { current - n; return *this; } self operator-(Distance n) const { return self(current n); } self operator-(Distance n) { current n; return *this; } Reference operator[](Distance n) const { return *(*this n); } };所以和vector和list涉及的反向迭代器总共有三个类模板如下图vector和list中宏定义时的反向迭代器模板参数列表只有一个参数vector中宏未定义时的反向迭代器模板参数列表有四个参数list中宏未定义时的反向迭代器接下来我们看看这三个迭代器这三个迭代器其实核心思路都是一样的都是适配器模式因为反向迭代器跟正向迭代器的思维是完全类似的无非就是方向是相反的用适配器减里用加加里用减就好了。但是如果针对每个容器都去实现一个反向迭代器太浪费了那每个容器都有正向迭代器直接用正向迭代器当模板适配封装出一个反向迭代器就好啦所以源码里也是这样的然后内部成员函数其他都一样就是加调减减调加那为什么还要分三个迭代器呢我们具体来看看首先这个是任意类型的迭代器或者严格来说它双向迭代器随机迭代器这些都支持因为它运算符重载的时候不仅重载了,--还重载了和-。因为从功能来说只有随机迭代器支持--等等然后这个在早期时候就是针对双向迭代器设计的他就只支持--但其实后期的时候都希望通过这个一个模板参数的来一统天下但是这个一个模板参数的有时候会有点问题就会用到 iterator_traits这个就涉及到了迭代器萃取的问题这个东西的本质就是模板的特化这个实现起来比较复杂在实现的时候会讲。在早期的 时候因为没有萃取所以那时候用的是四个模板参数的方法这里简单总结下这里由于历史原因我们的迭代器有好几个类模板这三个之中有个专门针对双向的那个在现如今基本已经被淘汰了所以我们主要用的是这俩个这俩个的差异就是一个是一个模板参数一个是四个模板参数这就是取决于要不要用一个萃取的技术这个会在下面讲2.实现反向迭代器上面的宏指的意思其实就是支不支持偏特化支持偏特化的话就采用单模板参数的迭代器萃取版本。不支持的话就采用老的版本多模板参数的版本我们看源码解引用的访问方式我们可以得出它的rbegin和rend是这样的就相当于是和正向迭代器的起始点结束点对调因为rbegin开始是头结点所以想要*时候就需要访问前一个元素老版本实现多模板参数迭代器我们先实现老版本iterator.h#pragma once namespace qiu { templateclass Iterator,class Ref,class Ptr class Reverse_Iterator { public: typedef Reverse_IteratorIterator, Ref, Ptr Self; Reverse_Iterator(Iterator it) :_it(it) { } Ref operator*() const { Iterator tmp _it; --tmp; return *tmp; } Ptr operator-() const { return (operator*()); } Self operator() { --_it; return *this; } Self operator(int) { Self tmp *this; --_it; return tmp; } Self operator--() { _it; return *this; } Self operator--(int) { Self tmp *this; _it; return tmp; } bool operator(const Self it) const { return _it it._it; } bool operator!(const Self it) const { return _it ! it._it; } private: Iterator _it; }; }随后我们把这个头文件包到对应的STL头文件中我就以vector为例我们先前所实现的vector代码#pragma once #include iostream #include cassert #include iterator.h namespace qiu { templateclass T class vector { public: typedef T* iterator; typedef const T* const_iterator; typedef Reverse_Iteratoriterator, T, T* reverse_iterator; typedef Reverse_Iteratorconst_iterator, const T, const T* const_reverse_iterator; void push_back(const T x); void reserve(size_t n); void clear(); iterator insert(iterator pos, const T x); void insert(iterator pos, size_t n, const T x); iterator erase(iterator pos); iterator erase(iterator first, iterator last);; vector() { } vector(size_t n, const T x T()) { reserve(n); while (n--) push_back(x); } vector(const vectorT x) { if (x.capacity() 0) { reserve(x.capacity()); iterator it x.begin(); while (it ! x.end()) { new (finish) T(*it); it; finish; } } } templateclass InputIterator vector(InputIterator first, InputIterator last) { while (first ! last) { push_back(*first); first; } } vector(std::initializer_listT il) { reserve(il.size()); for (auto x : il) push_back(x); } ~vector() { iterator it start; while (it ! finish) { it-~T(); it; } ::operator delete(start); } size_t size() const { return finish - start; } size_t capacity() const { return end_of_storage - start; } iterator begin() { return start; } iterator end() { return finish; } const_iterator begin() const { return start; } const_iterator end() const { return finish; } reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } T operator[](size_t n) { return *(start n); } vectorT operator(vectorT x) { swap(x); return *this; } void swap(vectorT x) { std::swap(start, x.start); std::swap(finish, x.finish); std::swap(end_of_storage, x.end_of_storage); } void resize(size_t n, T x T()) { assert(n 0); if (n size()) { while (size() n) { pop_back(); } } else { while (size() n) push_back(x); } } void pop_back() { assert(start ! finish); (finish - 1)-~T(); --finish; } private: iterator start nullptr; iterator finish nullptr; iterator end_of_storage nullptr; }; templateclass T void vectorT::push_back(const T x) { if (finish end_of_storage) reserve(capacity() 0 ? 4 : 2 * capacity()); new (finish) T(x); finish; } templateclass T void vectorT::reserve(size_t n) { if (n 0) { iterator new_start (iterator)::operator new(sizeof(T) * n); iterator new_finish new_start; iterator it start; while (it ! finish) { new (new_finish) T(*it); it; new_finish; } it start; while (it ! finish) { it-~T(); it; } ::operator delete(start); start new_start; finish new_finish; end_of_storage new_start n; } } templateclass T void vectorT::clear() { iterator it start; while (it ! finish) { it-~T(); it; } finish start; } templateclass T typename vectorT::iterator vectorT::insert(iterator pos, const T x) { assert(pos start pos finish); size_t len pos - start; if (finish end_of_storage) reserve(capacity() 0 ? 4 : 2 * capacity()); pos start len; iterator it finish; while (it ! pos) { if (it finish) new (it) T(*(it - 1)); else *it *(it - 1); --it; } *pos x; finish; return pos; } templateclass T void vectorT::insert(iterator pos, size_t n, const T x) { assert(pos start pos finish); size_t len pos - start; if (finish n end_of_storage) reserve(size() n 2 * capacity() ? size() n : 2 * capacity()); pos start len; iterator it finish n - 1; while (it ! pos n - 1) { if (it finish) { new (it) T(*(it - n)); } else { *(it) *(it - n); } --it; } it pos; for (int i 0; i n; i) { if (it finish) new (it) T(x); else *it x; it; } finish n; } templateclass T typename vectorT::iterator vectorT::erase(iterator pos) { assert(pos start pos finish); iterator it pos; while (it ! finish - 1) { *it *(it 1); it; } pop_back(); return pos; } templateclass T typename vectorT::iterator vectorT::erase(iterator first, iterator last) { assert(first start last finish first last); size_t len last - first; iterator it last; while (it ! finish) { *(it - len) *it; it; } it finish - 1; finish - len; while (it finish) { it-~T(); --it; } return first; } };我把新增的框选出来其实反向迭代器适配器封装好了后后面操作就很简单了先包头文件随后给Reverse_Iterator重命名下随后把rbegin,rend实现下就好了直接调用正向迭代器的就行可以用下面这个代码测试一下#define _CRT_SECURE_NO_WARNINGS #include iostream #include string #include vector.h using namespace std; void test2() { qiu::vectorstring v { aa,bb,cc,dd,ee }; qiu::vectorstring::iterator it1 v.begin(); while (it1 ! v.end()) { cout *it1 ; it1; } cout endl; qiu::vectorstring::reverse_iterator it v.rbegin(); while (it ! v.rend()) { cout *it ; it; } } void test1() { qiu::vectorint v { 1,2,3,4,5 }; qiu::vectorint::iterator it1 v.begin(); while (it1 ! v.end()) { cout *it1 ; it1; } cout endl; qiu::vectorint::reverse_iterator it v.rbegin(); while (it ! v.rend()) { cout *it ; it; } } int main() { test1(); cout endl; test2(); return 0; }测试下来是没问题的如下图其他容器也是同理这里就不演示了新版本实现单模板参数迭代器在老版本的反向迭代器实现的时候我们需要手动传指针和引用类型但其实正向迭代器无非就俩种版本一种是封装的正向迭代器另一种就是原生指针那我们就可以采用偏特化的方式来解决这方面的问题 这也正是迭代器萃取底层所实现的功能templateclass Iterator struct iterator_traits { typedef typename Iterator::Ref Ref; typedef typename Iterator::Ptr Ptr; }; templateclass T struct iterator_traitsT* { typedef T Ref; typedef T* Ptr; }; templateclass T struct iterator_traitsconst T* { typedef const T Ref; typedef const T* Ptr; };这就是迭代器萃取的底层如果是对应容器的迭代器是封装的我们就直接把对应容器内部的指针和引用重命名如果是原生指针类型的我们就进行一下偏特化就好了接下来再把这个迭代器萃取优化到我们刚刚实现的多模板参数迭代器上#pragma once namespace qiu { templateclass Iterator struct iterator_traits { typedef typename Iterator::Ref Ref; typedef typename Iterator::Ptr Ptr; }; templateclass T struct iterator_traitsT* { typedef T Ref; typedef T* Ptr; }; templateclass T struct iterator_traitsconst T* { typedef const T Ref; typedef const T* Ptr; }; templateclass Iterator class Reverse_Iterator { public: typedef Reverse_IteratorIterator Self; typedef typename iterator_traitsIterator::Ref Ref; typedef typename iterator_traitsIterator::Ptr Ptr; Reverse_Iterator(Iterator it) :_it(it) { } Ref operator*() const { Iterator tmp _it; --tmp; return *tmp; } Ptr operator-() const { return (operator*()); } Self operator() { --_it; return *this; } Self operator(int) { Self tmp *this; --_it; return tmp; } Self operator--() { _it; return *this; } Self operator--(int) { Self tmp *this; _it; return tmp; } bool operator(const Self it) const { return _it it._it; } bool operator!(const Self it) const { return _it ! it._it; } private: Iterator _it; }; }我们依旧用vector来测试一下没有问题结语那么C反向迭代器部分的内容就全部讲解完毕啦希望以上内容对你有所帮助感谢观看若觉得写的还可以可以分享给朋友一起来看哦毕竟一起进步更有动力嘛当然能关注一下就更好啦。
)
