reverse_iterator实现

对于实现reverse_iterator，我们可以学栈和队列的实现过程，利用适配器，实现如下;

#pragma oncetemplate<class Iterator,class Ref,class Ptr>
class reverse_Iterator
{
public://构造函数：reverse_Iterator(Iterator it):_it(it){}typedef reverse_Iterator<Iterator, Ref, Ptr> Self;//操作：bool operator!=(const Self& cur){return !(_it == cur._it);}bool operator==(const Self& cur){return _it == cur._it;}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;}Ref operator*(){//解引用是找前一个：Iterator tmp = _it;return *(--tmp);}Ptr operator&(){//取地址也是找前一个：return &(operator*());}
private:Iterator _it;
};

此时我们将实现的reverse_iterator添加到vector和list上如下：

（注意：vector、list其余部分之前已经实现过了）

vector.h

#pragma once
#include <assert.h>
#include <iostream>
#include <string.h>
#include "reverse_iterator.h"
namespace cx
{//模板类template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;typedef reverse_Iterator<iterator, T&, T*> reverse_iterator;typedef reverse_Iterator<const_iterator, const T&, const T*> const_reverse_iterator;//构造函数:vector(){}//传统写法/*vector(const vector<T>& v){_start = new T[v.capacity()];memcpy(_start, v._start, v.size() * sizeof(T));_finish = _start + v.size();_endofstorage = _start + v.capacity();}*///现代写法：vector(const vector<T>& v){reserve(v.capacity());for (const auto e : v){*_finish = e;_finish++;}}vector(size_t n, const T& val = T()){resize(n,val);}/*template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}*///析构函数~vector(){if (_start){delete[] _start;_start = _finish = _endofstorage = nullptr;}}vector<T>& operator=(vector<T> v){swap(v);return *this;}//迭代器iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}reverse_iterator rend(){return _start;}reverse_iterator rbegin(){return _finish;}const_reverse_iterator crend()const{return _start;}const_reverse_iterator crbegin()const{return _finish;}//计算大小size_t size()const {return end() - begin();}size_t capacity()const {return _endofstorage - _start;}//操作:bool empty() const{return _finish == _start;}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}void reserve(size_t n){if (n > capacity()){size_t old = size();T* tmp = new T[n];if (_start){memcpy(tmp, _start, sizeof(T) * old);delete[] _start;}_start = tmp;_finish = _start + old;_endofstorage = _start + n;}}void push_back(const T x){//检查是否扩容if (_finish == _endofstorage){size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}*_finish = x;_finish++;}void pop_back(){assert(size() > 0);_finish--;}T& operator[](size_t pos){assert(pos < size());return _start[pos];}T& operator[] (size_t pos) const{assert(pos < size());return _start[pos];}iterator insert(iterator pos, const T& val){assert(pos <= _finish && pos >= _start);if (_finish == _endofstorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;}//memmove(pos + 1, pos, sizeof(T) * (_finish - pos));iterator end = _finish - 1;while (end >= pos){*(end + 1) = *(end);end--;}*pos = val;_finish++;return pos;}/*void insert(iterator pos, const T& x){//检查assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());//注意：pos位置也要改变pos = _start + len;}memmove(pos + 1, pos, sizeof(T) * (_finish - pos));*pos = x;_finish++;}*/iterator erase(iterator pos){assert(pos < _finish && pos >= _start);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;it++;}_finish--;return pos;}iterator erase(iterator first, iterator last){}void resize(size_t n, T val = T()){if (n > size()){reserve(n);while (_finish < _start + n){*_finish = val;_finish++;}}else{_finish = _start + n;}}T& front(){return *_start;}const T& front() const{*_start;}T& back(){return *_finish;}const T& back() const{return *_finish;}T& at(size_t pos){assert(pos < size());return _start[pos];}const T& at(size_t pos) const{assert(pos < size());return _start[pos];}void assign(size_t n, const T& val){assert(_start == _finish);reserve(n);while (_finish != _endofstorage){*_finish = val;_finish++;}}void clear(){resize(0);}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;};
}

list.h:

#pragma once
#include <assert.h>
#include "reverse_iterator.h"
namespace cx
{template <class T>struct ListNode{//构造函数ListNode(const T& x=T()):_next(nullptr),_prev(nullptr),_val(x){}//成员变量：ListNode<T>* _next;ListNode<T>* _prev;T _val;};template <class T,class Ref,class Ptr>//template <class T, class Ref>struct _list_iterator{typedef ListNode<T> Node;typedef _list_iterator<T,Ref, Ptr> self;//typedef _list_iterator<T, Ref> self;//构造函数：//_list_iterator()/*iterator(Node* x):_node(x){}*/_list_iterator(Node* x):_node(x){}//不用写析构：原因在于我们的目标不是在这里析构//常见操作：		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;}Ref operator*(){return _node->_val;}bool operator!=(const self& s){return !(_node == s._node);}bool operator==(const self& s){return !(*this != s);}Ptr operator->(){return &_node->_val;}//类成员函数：Node* _node;};//template <class T>//struct _list_const_iterator//{//	typedef ListNode<T> Node;//	typedef _list_const_iterator<T> const_iterator;//	//构造函数：//	//_list_iterator()//	/*iterator(Node* x)//		:_node(x)//	{}*///	_list_const_iterator(Node* x)//		:_node(x)//	{}//	//不用写析构：原因在于我们的目标不是在这里析构//	//常见操作：		//	const_iterator& operator++()//前置++//	{//		_node = _node->_next;//		return (*this);//	}//	const_iterator operator++(int)//后置++//	{//		const_iterator tmp(*this);//		_node = _node->_next;//		return tmp;//	}//	const_iterator& operator--()//前置--//	{//		_node = _node->_prev;//		return *this;//	}//	const_iterator& operator--(int)//后置--//	{//		const_iterator tmp(*this);//		_node = _node->_prev;//		return tmp;//	}//	const T& operator*()//	{//		return _node->_val;//	}//	bool operator!=(const const_iterator& s)//	{//		return !(_node == s._node);//	}//	bool operator==(const const_iterator& s)//	{//		return !(*this != s);//	}//	//类成员函数：//	Node* _node;//};template <class T>class list{public:typedef ListNode<T> Node;//typedef _list_iterator<T,T&> iterator;typedef _list_iterator<T, T&, T*> iterator;//typedef _list_iterator<T, const T&> const_iterator;typedef _list_iterator<T,const T&,const T*> const_iterator;//typedef reverse_Iterator<iterator, T&, T*> reverse_iterator;typedef reverse_Iterator<const_iterator, const T&, const T*> const_reverse_iterator;//构造函数void empty_list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}list(){empty_list();}//list ( list& x);list(const list<T>& s){empty_list();for (auto e : s)//该类型为：T{push_back(e);}}//list& operator= (const list& lt);//传统写法：//list<T>& operator= (list<T>& lt)//{//	if(this != &lt)//	{//		//清除*this中内容//		clear();//		for (T e : lt)//		{//			push_back(e);//		}//	}//	return *this;//}//现代写法：list<T>& operator= (list<T> lt){swap(lt);return *this;}//析构函数：void clear(){//区别析构函数，clear只会删除有效数据，保留虚拟头结点iterator it = begin();while (it != end()){it=erase(it);}}~list(){clear();//删除_head;delete _head;_head = nullptr;}//迭代器：iterator begin()//有效第一个节点{//assert(_head->_next != _head);//如果写上面这句，会出现开始为空链表报错情况return _head->_next;}const_iterator begin() const{return _head->_next;}iterator end(){return _head;}const_iterator end() const{return _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());}//常见操作：iterator erase(iterator pos){//检查pos位置非_head位置assert(pos !=end());//删除的是pos位置Node* current = pos._node;Node* prev = current->_prev;Node* next = current->_next;//删除操作prev->_next = next;next->_prev = prev;delete current;return next;//返回的是pos下一个位置}iterator erase(iterator first, iterator last)//区间左闭右开{assert(first != end());assert(last != end());while (first != last){if (first == end())break;first = erase(first);}return first;}void push_back(const T& val){Node* tmp = new Node(val);Node* tail = _head->_prev;tail->_next = tmp;tmp->_prev = tail;tmp->_next = _head;_head->_prev = tmp;}void swap(list<T>& tmp){std::swap(_head, tmp._head);}iterator insert(iterator pos, const T& x){//insert是指在pos位置前插入Node* current = pos._node;Node* prev = current->_prev;//开空间Node* tmp = new Node(x);tmp->_prev = prev;prev->_next = tmp;tmp->_next = current;current->_prev = tmp;//return iterator(tmp);return tmp;//注意点：单参数的类可以隐式类型转换}//容量相关：bool empty() const{return _head->_next == _head;}size_t size() const{size_t n = 0;Node* tmp = _head->_next;while (tmp!=_head){tmp = tmp->_next;n++;}return n;}void push_front(const T& x){this->insert(begin(), x);}void pop_back(){this->erase(--end());}void pop_front(){erase(begin());}//Element access:T& front(){return _head->_next->_val;}const T& front() const{return _head->_next->_val;}T& back(){return _head->_prev->_val;}const T& back() const{return _head->_prev->_val;}private://虚拟头结点：Node* _head;};
}

这里再给大家一组测试用例：

#include <iostream>using namespace std;
#include "vector.h"
#include "list.h"void test_list()
{cx::list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);l.push_back(5);l.push_back(6);cx::list<int>::reverse_iterator it = l.rbegin();while (it != l.rend()){cout << *it << " ";it++;}cout << endl;
}
void test_vector()
{cx::vector<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);l.push_back(5);l.push_back(6);cx::vector<int>::reverse_iterator it = l.rbegin();while (it != l.rend()){cout << *it << " ";it++;}cout << endl;
}
int main()
{test_list();test_vector();return 0;
}

感谢大家的支持！！！