一、反向迭代器与正向迭代器的区别
反向迭代器与正向迭代器的解引用都是一样的，都是可以直接找到该位置里面存储的值。不同的是他们之间的运算规则不同，反向迭代器的++就相当于正向迭代器的–
按照我们一般的理解，正向迭代器与反向迭代器在list与vector中的实际应该是如下的
对于设计这个正向迭代器与反向迭代器。
对于list我们可能的想法是将原来的正向迭代器给拷贝一份，然后++运算符重载中修改为指向前一个结点，–运算符重载修改为指向后一个结点
对于vector可能是类似于list一样，写一个迭代器类，然后运算符重载去处理。
这样做确实可以，但是显得过于冗余了
二、适配器模式来实现反向迭代器
在库里面其实使用的是适配器来实现反向迭代器的，如下所示，它封装了一个反向迭代器的类，然后传递正向迭代器作为类型。就是我们的反向迭代器了。
也就是说，库里面就是写了一个万能的类，无论是谁的迭代器传过来，都能将之改变为反向迭代器
下面是库里面的vector的迭代器
如下是库里面对于反向迭代器的实现
我们可以着重看一下这个解引用的，我们会发现，它是先–，然后再解引用的，这一点就很奇怪，与我们之前所设想的结构不符合。那么我们再继续深入研究一下begin，end，rbegin，rend这些函数
我们可以主要到，这个rbegin返回的其实是end，rend返回的是begin
也就是说，根据库里面的结构，它的实际图应该是这样的
这里其实就体现了一个镜像对称特性，认为反向迭代器与正向迭代器是具有对称关系的
这样一来就说明了为什么要先减一下，才能去解引用
三、手撕反向迭代器
根据前面的思路我们就可以设计出我们的反向迭代器了
可以看出，这又是一层套娃。将我们原来的普通迭代器给再套娃一层，就可以改变原来迭代器的行为了。
#pragma once namespace Sim { template<class Iterator, class Ref, class Ptr> struct ReverseIterator { Iterator _it; typedef ReverseIterator<Iterator, Ref, Ptr> Self; ReverseIterator(Iterator it) :_it(it) {} Ref operator*() { Iterator tmp = _it; return *(--tmp); } Ptr operator->() { return &(operator*()); } Self& operator++() { --_it; return *this; } Self operator++(int) { Iterator tmp(_it); _it--; return tmp; } Self& operator--() { ++_it; return *this; } Self& operator--(int) { Iterator tmp(_it); _it++; return tmp;; } bool operator!=(const Self& s) const { return _it != s._it; } bool operator==(const Self& s) const { return _it == s._it; } }; }
我们这个反向迭代器是万能的，我们可以应用于其他类中，下面是用list使用这个反向迭代器
#define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> #include<list> #include<assert.h> #include"reverse_iterator.h" using namespace std; namespace Sim { template<class T> struct list_node { list_node<T>* _next; list_node<T>* _prev; T _val; list_node(const T& val = T()) :_next(nullptr) ,_prev(nullptr) ,_val(val) {} }; template<class T, class Ref, class Ptr> struct __list_iterator { typedef list_node<T> Node; typedef __list_iterator<T, Ref, Ptr> self; Node* _node; __list_iterator(Node* node) :_node(node) {} Ref operator*() { return _node->_val; } Ptr operator->() { return &_node->_val; } self& operator++() { _node = _node->_next; return *this; } self operator++(int) { self tmp(*this); _node = _node->_next; return tmp; } self& operator--() { _node = _node->_prev; return *this; } self operator--(int) { self tmp(*this); _node = _node->_prev; return tmp; } bool operator!=(const self & it) const { return _node != it._node; } bool operator==(const self & it) const { return _node == it._node; } }; template<class T> class list { typedef list_node<T> Node; public: typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; typedef ReverseIterator<iterator, T&, T*> reverse_iterator; typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator; iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head); } const_iterator begin() const { return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); } 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()); } void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; _size = 0; } list() { empty_init(); } list(const list<T>& lt) { empty_init(); for (auto& e : lt) { push_back(e); } } void swap(list<T>& lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } list<T>& operator=(list<T> lt) { swap(lt); return *this; } void push_back(const T& val) { insert(end(), val); } void push_front(const T& val) { insert(begin(), val); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } iterator insert(iterator pos, const T& val) { Node* newnode = new Node(val); Node* cur = pos._node; Node* prev = cur->_prev; prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; ++_size; return newnode; } iterator erase(iterator pos) { assert(pos != end()); Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; delete cur; cur = nullptr; prev->_next = next; next->_prev = prev; --_size; return next; } size_t size() { return _size; } ~list() { clear(); delete _head; _head = nullptr; } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } private: Node* _head; size_t _size; }; }
下面是vector的代码
#pragma once #include<iostream> #include<string.h> #include<assert.h> #include<algorithm> #include"reverse_iterator.h" using namespace std; namespace Sim { template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; typedef ReverseIterator<iterator, T&, T*> reverse_iterator; typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator; 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()); } vector() :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) {} vector(const vector<T>& v) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { _start = new T[v.capacity()]; //memcpy(_start, v._start, sizeof(T) * v.size()); for (size_t i = 0; i < v.size(); i++) { _start[i] = v[i]; } _finish = _start + v.size(); _end_of_storage = _start + v.capacity(); } //vector(const vector<T>& v) // :_start(nullptr) // , _finish(nullptr) // , _end_of_storage(nullptr) //{ // reserve(v.capacity()); // for (auto e : v) // { // push_back(e); // } //} vector(size_t n, const T& val = T()) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { resize(n, val); } vector(int n, const T& val = T()) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { resize(n, val); } template<class InputIterator> vector(InputIterator first, InputIterator last) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { while (first != last) { push_back(*first); first++; } } void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish,v._finish); std::swap(_end_of_storage,v._end_of_storage); } vector<T>& operator=(vector<T> v) { swap(v); return *this; } ~vector() { if (_start) { delete[] _start; _start = nullptr; _finish = nullptr; _end_of_storage = nullptr; } } size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } void reserve(size_t n) { if (n > capacity()) { iterator tmp = new T[n]; int sz = size(); if (_start) { //memcpy(tmp, _start, sizeof(T) * sz); for (size_t i = 0; i < size(); i++) { tmp[i] = _start[i]; } delete[] _start; } _start = tmp; _finish = _start + sz; _end_of_storage = _start + n; } } void resize(size_t n, const T& val = T()) { if (n < size()) { _finish = _start + n; } else { reserve(n); while (_finish != _start + n) { *_finish = val; _finish++; } } } void push_back(const T& val) { if (_finish == _end_of_storage) { size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); } *_finish = val; _finish++; } void pop_back() { if (_start) { _finish--; } //erase(_finish-1); } T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } const T& operator[](size_t pos) const { assert(pos < size()); return _start[pos]; } iterator insert(iterator pos, const T& val) { assert(pos >= _start && pos <= _finish); if (_finish == _end_of_storage) { int sz = pos - _start; int newcapacity= capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); pos = _start + sz; } iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *(end); end--; } *pos = val; _finish++; return pos; } iterator erase(iterator pos) { assert(pos >= _start && pos < _finish); if (_start) { iterator end = pos + 1; while (end != _finish) { *(end - 1) = *end; end++; } _finish--; } return pos; } private: iterator _start; iterator _finish; iterator _end_of_storage; }; }
除此外，我们可以使用下面的代码进行测试我们上面的代码，结果是符合我们的预期的
#define _CRT_SECURE_NO_WARNINGS 1 #include"list.h" #include"vector.h" void Print(const Sim::list<int>& lt) { Sim::list<int>::const_reverse_iterator rit = lt.rbegin(); while (rit != lt.rend()) { cout << *rit << " "; rit++; } cout << endl; } void test() { Sim::list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); Sim::list<int>::reverse_iterator rit = lt.rbegin(); while (rit != lt.rend()) { cout << *rit << " "; ++rit; } cout << endl; Print(lt); } void Print(const Sim::vector<int>& v) { Sim::vector<int>::const_reverse_iterator rit = v.rbegin(); while (rit != v.rend()) { cout << *rit << " "; rit++; } cout << endl; } void testvector() { Sim::vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); Sim::vector<int>::reverse_iterator rit = v.rbegin(); while (rit != v.rend()) { cout << *rit << " "; ++rit; } cout << endl; Print(v); } int main() { //test(); testvector(); return 0; }
好了，本期内容就到这里了
如果对你有帮助的话，不要忘记点赞加收藏哦！！！
