C++ 补充 反向迭代器的实现

阅前提要：

本文主要是对list和vector的实现的补充，以代码实现为主，注释为辅，如果对vector，list底层实现感兴趣的可以自行阅读，代码量有点大，请大家耐心查看，对理解语言很有帮助（本文的实现方式并不是stl标准库中的实现，但大致的思路一样）

一、反向迭代器的实现

实现思想：反向迭代器和正向迭代器的不同点只在于++，--时迭代器的移动方向不同，其他的操作基本一样，我们可以对正向迭代器进行封装，从而得到反向迭代器，代码如下

namespace zxws
{// 适配器 -- 复用//这里细节关键在于模板参数可以传任何一个容器的正向迭代器，//即只要该容器的正向迭代器实现了，那么反向迭代器也就实现了(这就是模板的力量)template<class Iterator, class Ref, class Ptr>struct Reverse_iterator{Iterator _it;//这是正向迭代器typedef Reverse_iterator Self;Reverse_iterator(Iterator it):_it(it){}bool operator==(const Self& s){return _it == s._it;}bool operator!=(const Self& s){return _it != s._it;}//这个函数的实现和我们默认的rbegin()和rend()的位置有关//下面的代码实现是默认rbegin()是end()   rend()是begin()Ref operator*(){Iterator cur = _it;return *(--cur);}Ptr operator->(){return &(operator*());}Self& operator++(){--_it;return *this;}Self& operator--(){++_it;return *this;}Self operator++(int){Self tmp(_it);--_it;return tmp;}Self operator--(int){Self tmp(_it);++_it;return tmp;}};
}

二、list的实现

思路：本质和数据结构中的双向循环链表一样，只是用C++的语法实现的，不同点在迭代器

代码如下

namespace zxws
{template<class T>struct Node {T _val;Node* _next;Node* _pre;Node(const T& x=T()):_val(x),_next(nullptr),_pre(nullptr){}};//正向迭代器的实现template<class T,class Ref,class Ptr>struct Iterator {typedef Node<T> Node;typedef Iterator Self;Node* node;Iterator(Node* p):node(p){}Self& operator++(){node = node->_next;return *this;}Self& operator--(){node = node->_pre;return *this;}Self operator++(int){Self tmp(node);node = node->_next;return tmp;}Self operator--(int){Self tmp(node);node = node->_pre;return tmp;}Ref operator*(){return node->_val;}Ptr operator->(){return &node->_val;}bool operator==(const Self& tmp){return node == tmp.node;}bool operator!=(const Self& tmp){return node != tmp.node;}};template<class T>class list{public:typedef Node<T> Node;typedef Iterator<T, T&, T*> iterator;typedef Iterator<T,const T&,const T*> const_iterator;iterator begin(){return iterator(_head->_next);}const_iterator begin() const{return const_iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator end() const{return const_iterator(_head);}typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;//对rbegin(),rend()的位置的定义//与反向迭代器中解引用运算符的重载实现有关reverse_iterator rbegin(){return reverse_iterator(end());}const_reverse_iterator rbegin() const{return const_reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}list(){init();}void init(){_head = new Node;_head->_next = _head;_head->_pre = _head;}~list(){clear();delete _head;_head = nullptr;}void clear(){auto cur = begin();while(cur!=end()){cur = erase(cur);}}list(const list& tmp){init();for(auto& x:tmp){push_back(x);}}list& operator=(list tmp){swap(tmp);return *this;}void swap(list& tmp){std::swap(_head, tmp._head);}void push_back(const T& x){insert(x, end());}void push_front(const T& x){insert(x, begin());}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator insert(const T& x, iterator pos){Node* cur = pos.node;Node* pre = cur->_pre;Node* newnode = new Node(x);newnode->_next = cur;cur->_pre = newnode;newnode->_pre = pre;pre->_next = newnode;return newnode;//类型转化}iterator erase(iterator pos){assert(pos != end());Node* cur = pos.node;Node* next = cur->_next;cur->_next->_pre = cur->_pre;cur->_pre->_next = cur->_next;delete(cur);return next;//类型转化}private:Node* _head = nullptr;};
}

三、vector的实现

思路：本质和数据结构中的动态数组一样，只是用C++的语法实现的，不同点在迭代器

namespace zxws
{template <class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}const_iterator begin() const{return _start;}iterator end(){return _finish;}const_iterator end() const{return _finish;}//++,--,==,!=,*,->没必要写，因为vector迭代器底层是指针，是内置类型，能够自己实现++，--，比较大小等操作typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(end());}const_reverse_iterator rbegin() const{return const_reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}vector(){}vector(const vector& tmp){if (tmp.size()){_finish = _start = new T[tmp.capacity()];for (auto x : tmp)*(_finish++) = x;_end_of_storage = _start + tmp.capacity();}}void swap(vector& tmp){std::swap(_start, tmp._start);std::swap(_finish, tmp._finish);std::swap(_end_of_storage, tmp._end_of_storage);}vector& operator=(vector tmp){swap(tmp);return *this;}~vector(){delete[] _start;_start = nullptr;_finish = nullptr;_end_of_storage = nullptr;}T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}void push_back(const T& x){if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}void pop_back(){assert(size() > 0);--_finish;}void resize(size_t n, const T& x = T()){if (n>size()){reserve(n);for (int i = size(); i < n; i++)_start[i] = x;}_finish = _start + n;}void reserve(size_t n){if (capacity() < n){size_t sz = size();T* tmp = new T[n];for (size_t i = 0; i < sz; i++)tmp[i] = _start[i];delete[] _start;_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}}iterator insert(iterator pos,const T& x){assert(pos>=_start&&pos<=_finish);if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator it = _finish;while (it > pos){*it = *(it - 1);it--;}_finish++;*pos = x;return pos;}iterator erase(iterator pos){assert(pos >= _start && pos < _finish);iterator cur = pos;while (cur < _finish - 1){*cur = *(cur + 1);cur++;}--_finish;return pos;}size_t size(){return _finish - _start;}size_t capacity(){return _end_of_storage - _start;}private:T* _start = nullptr;T* _finish = nullptr;T* _end_of_storage = nullptr;};
}