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 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 Node;
		typedef Iterator iterator;
		typedef Iteratorconst 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 reverse_iterator;
		typedef Reverse_iteratorconst 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 reverse_iterator;
		typedef Reverse_iteratorconst 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;
	};
}