STL--List--与正反向迭代器复写

• 前言：
• 迭代器
• • 正向迭代器
  • • 思路
    • 构造函数
    • ++，--
    • *，->
    • ！=，==
  • 反向迭代器
  • • 成员
    • 构造函数
    • ++，--
    • *与->
    • ！=与==
• list
• • • begin()
    • rbegin()
    • end()
    • rend()
  • inert()
  • erase()
• 全部代码
• • Reverse_iterator.h
  • List.h
• 总结

• 本文介绍STL——list功能复写，重点是迭代器，感受泛型编程，函数重载之美

• 博主收集的资料New Young，连载中。

• 博主收录的问题:New Young

• 转载请标明出处：New Young

1. list的关键地方是对迭代器的复写，在复写这一过程，可以不断体会C++语言泛型编程，函数重载的魅力

2. 不同于vector，string，其底层类似数组，它们的迭代器是对元素对象的==“通用指针”,通过指针的运算，就可以完成很多操作：++，解引用等，但是因为结点是在堆上是随机存储的，因此链表的迭代器必然要进行改变，同时为了支持算术运算（++，–…）解引用等操作，链表的迭代器必然要封装成一个结构体==。

3. 为什么使用结构体？结构体默认成员是public，方便访问成员。

4. 同时又因为list是有const之分，因此迭代器分为iterarot和const_iterator,（注意这里的const是指节点中的data不可更改，但是迭代器仍是可以改变的，对比常量指针）**但是这2者的功能非常类似，因此这里就通过类模板的模板参数进行区别。----``泛型编程**

注意拷贝构造函数的形参，是最小权限，可以满足很多情形：匿名对象，类型提升

//迭代器
	template 
	struct list_iterator
	{
typedef list_iterator					 iterator;
		typedef list_iterator   const_iterator;
		typedef list_node									Node;
		typedef list_iterator						Self;
		Node* _node;
		list_iterator( Node*x)
			:_node(x)
		{
			;
		}
		list_iterator() 
		{}
		//场景：权限缩小的拷贝，同时因为计算需要，生成临时对象时会调用
		//其它的通过默认的拷贝构造和默认赋值运算符即可
		list_iterator(const iterator& x) : _node(x._node)
		{

		}

	typedef list_iterator					 iterator;
		typedef list_iterator   const_iterator;
		typedef list_node									Node;
		typedef list_iterator						Self;
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;
}

1. 通过返回值的引用，当*时就可以防止const时，进行的写操作

2. 对于节点中存放内置类型的数据时，通过*就可以得到数据但是对于自对于类型如果需要访问数据成员时，需要->运算符但是在使用->,为避免出现->->的情况，编译器会进行优化为一个->
   如日期类 cout< < it- > year<<“” << it->month<<“”<< it->day< 本质上要想得到year，需要 (it->) ->year=Date->year,只是编译器优化了一下

	Ref operator*()
		{
			return _node->_data;
		}
Ptr  operator->()
		{
			return &_node->_data;
		
		}

依据不同类型的迭代器，可能会因为生产一个临时的同类型的迭代器如：iterator和const iterator进行比较，会生成一个iterator的临时const_iterator的拷贝

	
		bool operator !=(const Self& it)const 
		{
			return _node != it._node;
		}
		bool operator ==(const Self& it)const
		{
			return _node == it._node;

		}

1. 反向迭代器是对正向迭代器的复用，同时几乎所有的反向迭代器都是正向迭代器的复用，因此这里利用类模板来构造反向迭代器
2. 反向迭代器的rbegin是正向迭代器的end(),rend()是正向迭代器的begin().
3. 对于解引用，因为rbegin和rend的特殊性，反向迭代器返回的是迭代器前一个节点的数据

	template
	class reverse_iterator
	{
		
	public:
		typedef reverse_iterator self;	
     private:
		Iterator _it;

template
	class reverse_iterator
	{
		
	public:
		typedef reverse_iterator self;
		//这种形式的形参是最小权限，可以满足任何的拷贝构造
		reverse_iterator(const Iterator& it)
			:_it(it)
		{
			;
		}

self& operator++()
		{
			--_it;
			return *this;
		}

		self operator++(int)
		{
			self tmp = _it--;
			return tmp;
		}

		self& operator--()
		{
			++_it;
			return *this;
		}

		self operator--(int)
		{
			self tmp = _it++;
			return tmp;
		}

Ref operator*()
		{
			Iterator tmp = _it;
			return *(--tmp);
		}
		Ptr operator->()
		{
			Iterator tmp = _it;
			return  &(*(--tmp));
		}

	bool operator !=(const self &rit )
		{
		
			return _it != rit._it;
		}

		bool operator ==(const self& rit)
		{

			return _it == rit._it;
		}
	private:
Iterator _it;

iterator begin()
		{
			return  iterator (_head->_next);
		
		}
 const_iterator begin()const
		 {
			 return  const_iterator(_head->_next);

		 }

 reverse_iterator rbegin()
		 {
			 return  reverse_iterator(end());	
		 }
 reverse_const_iterator rbegin()const
		 {

			 return reverse_iterator(end());

		 }

 iterator end()
		{
			 return iterator(_head);
		}
const_iterator end()const
		 {
			 return const_iterator(_head);

		 }

 reverse_iterator rend()
		 {
			 return  reverse_iterator (begin());
			
		 } 
reverse_const_iterator rend()const
		 {

			 return reverse_iterator(begin());

		 }

 //pos位置前插入数据
		iterator insert(iterator pos, const T& value)
		 {
			assert(pos != end());
			 Node* prevnode = pos._node->_prev;
			 Node* newnode = new Node(value);
			 newnode->_next = pos._node;
			 newnode->_prev = prevnode;
			 prevnode->_next = newnode;

			 pos._node->_prev = newnode;

			 return iterator(newnode);
		 }

//返回删除后下一个节点的迭代器
		iterator erase(iterator pos)
		 {
		 
			 assert(pos != end());
			 Node* prevnode = pos._node->_prev;
			 Node* nextnode = pos._node->_next;
		
			 prevnode->_next = nextnode;
			 nextnode->_prev = prevnode;
			 delete pos._node;
			 return iterator(nextnode);
		 }

#pragma once


namespace My_Rev_It
{

	template
	class reverse_iterator
	{
		
	public:
		typedef reverse_iterator self;
		//这种形式的形参是最小权限，可以满足任何的拷贝构造
		reverse_iterator(const Iterator& it)
			:_it(it)
		{
			;
		}
		self& operator++()
		{
			--_it;
			return *this;
		}

		self operator++(int)
		{
			self tmp = _it--;
			return tmp;
		}

		self& operator--()
		{
			++_it;
			return *this;
		}

		self operator--(int)
		{
			self tmp = _it++;
			return tmp;
		}


		Ref operator*()
		{
			Iterator tmp = _it;
			return *(--tmp);
		}
		Ptr operator->()
		{
			Iterator tmp = _it;
			return  &(*(--tmp));
		}

		bool operator !=(const self &rit )
		{
		
			return _it != rit._it;
		}

		bool operator ==(const self& rit)
		{

			return _it == rit._it;
		}
	private:
		Iterator _it;
	};

}

#pragma once
#include
#include  
#include 
#include 
#include
#include
#include
#include"Reverse_iterator.h"
namespace My_List
{
	//节点
	template
	struct  list_node
	{
		list_node(const T &x=T())
			:_next(nullptr),_prev(nullptr),_data(x)
		{
				;
		}
		list_node* _next;
		list_node* _prev;
		T _data;
	};

	//迭代器
	template 
	struct list_iterator
	{
		typedef list_iterator					 iterator;
		typedef list_iterator   const_iterator;
		typedef list_node									Node;
		typedef list_iterator						Self;
		Node* _node;
		list_iterator( Node*x)
			:_node(x)
		{
			;
		}
		list_iterator() 
		{}
		//这种形式的形参是最小权限，可以满足
		// 权限缩小的拷贝，同时因为计算需要进行提升，生成临时对象时会调用
		//其它的通过默认的拷贝构造和默认赋值运算符即可
		list_iterator(const iterator& x) : _node(x._node)
		{

		}
		//前置++
		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;
		}
		//通过返回值的引用，当*时就可以防止const时，进行的写操作
		Ref operator*()
		{
			return _node->_data;
		}

	
		Ptr  operator->()
		{
			return &_node->_data;
		
		}

		//即使是不同类型的迭代器，这里也会因为生产一个临时的同类型的迭代器
		bool operator !=(const Self& it)const 
		{
			return _node != it._node;
		}
		bool operator ==(const Self& it)const
		{
			return _node == it._node;

		}

	};

	//带头双向循环链表
	template
	class list
	{
	public:
		typedef list_node								 Node;
		typedef list_iterator					 iterator;
		typedef list_iterator const_iterator;

		typedef My_Rev_It::reverse_iterator   reverse_iterator;

		typedef My_Rev_It::reverse_iterator  reverse_const_iterator;




		list(const T&value=T())//头节点
		{
			_head = new Node(value);
			_head->_next = _head;
			_head->_prev = _head;
		}

		list(int  n, const T& value = T())
		{

			_head = new Node(value);
			_head->_next = _head;
			_head->_prev = _head;

			for (int  i = 0; i < n; ++i)
				push_back(value);
		}

		//:list lt(5, Date(2022, 1, 2));
		//list lt1(5, 1);
		//当形参进行对比时，对于Date会准确调用list(size_t n, const T& value = T())
		//当为int时，编译器更倾向于list(Inputitator first, Inputitator last)
		//因此重载一份list(int  n, const T& value = T())即可
		list(size_t n, const T& value = T())
		{

			_head = new Node(value);
			_head->_next = _head;
			_head->_prev = _head;
			for (size_t i = 0; i < n; ++i)
				push_back(value);
		}

		//利用迭代器区别初始化list
		template
		list(Inputitator first, Inputitator last)
		{
			//构建头节点
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		//拷贝构造
		list(const list <)
			
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;

			list tmp(lt.begin(), lt.end());
			//注意 _head可能是随机指针或者nullptr
			std::swap(_head, tmp._head);
		}

		//赋值运算符
		list& operator=(const list lt)
		{
			clear();
			std::swap(_head, lt._head);
			return *this;
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				erase(it++);
			}
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
		void push_back(const T &x)
		{
				
			insert(end(),x);
			
		}
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		void pop_back()
		{
			erase(--end());
		}
		void pop_front()
		{
			
			erase(begin());
		}

		iterator begin()
		{
			return  iterator (_head->_next);
		
		}

		 iterator end()
		{
			 return iterator(_head);
		}

		 reverse_iterator rbegin()
		 {
			 return  reverse_iterator(end());
				
		 }
		 reverse_iterator rend()
		 {
			 return  reverse_iterator (begin());
			
		 }


		 reverse_const_iterator rbegin()const
		 {

			 return reverse_iterator(end());

		 }
		 reverse_const_iterator rend()const
		 {

			 return reverse_iterator(begin());

		 }


		 const_iterator begin()const
		 {
			 return  const_iterator(_head->_next);

		 }
		 const_iterator end()const
		 {
			 return const_iterator(_head);

		 }
		 //pos位置前插入数据
		 //不会出现迭代器失效问题，但是需要返回一个插入位置的迭代器
		 //很显然，constlist是不需要insert的
		iterator insert(iterator pos, const T& value)
		 {
			 Node* prevnode = pos._node->_prev;
			 Node* newnode = new Node(value);
			 newnode->_next = pos._node;
			 newnode->_prev = prevnode;
			 prevnode->_next = newnode;
			 pos._node->_prev = newnode;
			 return iterator(newnode);
		 }

		//返回删除后下一个节点的迭代器
		iterator erase(iterator pos)
		 {
		 
			 assert(pos != end());
			 Node* prevnode = pos._node->_prev;
			 Node* nextnode = pos._node->_next;
		
			 prevnode->_next = nextnode;
			 nextnode->_prev = prevnode;
			 delete pos._node;
			 return iterator(nextnode);
		 }
	private:
		Node* _head;

	};
	
}

复写过程经常遇到类型无法转化问题，大概率是因为权限问题或者