[数据结构与算法]list、简单的迭代器

头文件

#pragma once
#ifndef LIST_H
#define LIST_H
//防止头文件重复引入
#include<initializer_list>
namespace liujin
{
	template<class T>
	void Swap(T& x, T& y)
	{
		T tmp = x;
		x = y;
		y = tmp;
	}
	template<class _Ty>
	class list
	{
	private:
		struct _Node;//节点
		typedef struct _Node* _Nodeptr;
		struct _Node
		{
			_Nodeptr _Prev, _Next;
			_Ty _value;
		};
		struct _Acc;
		struct _Acc
		{
			typedef _Node*& _Nodepref;//节点指针引用
			typedef _Ty& _Vref;//类型引用
			static _Vref Get_Value(_Nodepref p)
			{
				return p->_value;
			}
			static _Nodepref Get_Prev(_Nodepref p)
			{
				return p->_Prev;
			}
			static _Nodepref Get_Next(_Nodepref p)
			{
				return p->_Next;
			}
		};
	public:
		typedef _Ty          value_type;//值类型
		typedef _Ty& reference;//引用
		typedef const _Ty& const_reference;//常引用
		typedef _Ty* pointer;//指针
		typedef const _Ty* const_pointer;//常指针
		typedef size_t       size_type;
		typedef int          difference_type;//差值类型
	public:
		class iterator;//普通迭代器
		class const_iterator;//const型迭代器
		class const_iterator//常性迭代器（只能对节点进行读不能写）
		{
		protected:
			_Nodeptr _Ptr;
		public:
			const_iterator(_Nodeptr _P) :_Ptr(_P) {}
			const_reference operator*()//返回节点的值的常引用
			{
				return _Acc::Get_Value(_Ptr);
			}
			const_pointer operator->()//返回节点值的地址
			{
				return &**this;
			}
			const_iterator& operator++()
			{
				_Ptr = _Acc::Get_Next(_Ptr);
				return *this;
			}
			const_iterator operator++(int)//后置++
			{
				const_iterator tmp = *this;
				_Ptr = _Acc::Get_Next(_Ptr);
				return tmp;
			}
			const_iterator& operator--()//前置--
			{
				_Ptr = _Acc::Get_Prev(_Ptr);
				return *this;
			}
			const_iterator operator--(int)
			{
				const_iterator tmp = *this;
				_Ptr = _Acc::Get_Prev(_Ptr);
				return tmp;
			}
			bool operator==(const const_iterator& it)
			{
				return this->_Ptr == it._Ptr;
			}
			bool operator!=(const const_iterator& it)
			{
				return !(this->_Ptr == it._Ptr);
			}
			_Nodeptr _Mynode()const
			{
				return _Ptr;
			}
		};
		class iterator:public const_iterator//迭代器
		{
		public:
			iterator(_Nodeptr _p) :const_iterator(_p) {}
			reference operator*()
			{
				return _Acc::Get_Value(this->_Ptr);
			}
			pointer operator->()const
			{
				return &_Acc::Get_Value(this->_Ptr);
				//return &**this;
			}
			iterator& operator++()//前置++ 指向下一个节点
			{
				this->_Ptr = _Acc::Get_Next(this->_Ptr);
				return *this;
			}
			iterator operator++(int)//后置++(先赋值，再++)
			{
				iterator tmp = *this;
				this->_Ptr = _Acc::Get_Next(this->_Ptr);
				return tmp;
			}
			iterator& operator--()//前置-- 指向前一个结点
			{
				this->_Ptr = _Acc::Get_Prev();
				return *this;
			}
			iterator operator--(int)//后置--
			{
				iterator tmp = *this;
				this->_Ptr = _Acc::Get_Prev();
				return tmp;
			}
			bool operator==(const iterator& it)const
			{
				return it._Ptr == this->_Ptr;
			}
			bool operator!=(const iterator& it)const
			{
				return !(it == *this);
			}
		};
public:
		iterator begin() {//返回头结点的_Next
			return iterator(_Acc::Get_Next(_Head));
		}
		iterator end() {//返回尾节点的_Next
			return iterator(_Head);
		}
		const_iterator begin()const {
			return const_iterator(_Acc::Get_Next(_Head));
		}
		const_iterator end()const {
			return const_iterator(_Head);
		}
		public:
			typedef const_iterator _It;
			list():_Head(_Buynode()),_Size(0){}
			list(size_t count, const _Ty& val) :_Head(_Buynode()), _Size(0)
			{
				insert(begin(), count, val);
			}
			list(const _Ty* _F, const _Ty* _L) :_Head(_Buynode()), _Size(0)
			{
				insert(begin(), _F, _L);
			}
			list(const list& _X) :_Head(_Buynode()), _Size(0)
			{
				insert(begin(), _X.begin(), _X.end());
			}
			list(std::initializer_list<_Ty> list):list()
			{
				for (auto& X : list)
				{
					push_back(X);
				}
			}
			list& operator==(const list& _X)
			{
				if (this == &_X)return *this;
				iterator _F1 = begin();
				iterator _L1 = end();
				const_iterator _F2 = _X.begin();
				const_iterator _L2 = _X.end();
				for (; _F1 != _L1 && _F2 != _L2; ++_F1, ++_F2)
				{
					*_F1 = *_F2;
				}
				erase(_F1,_L1);
				insert(_L1, _F2, _L2);//如有没赋值完的节点就插入到末尾
				return*this;
			}
			~list()
			{
				clear();
				_Freenode(_Head);
			}
			//返回的是新插入的节点
			iterator insert(iterator _P, const _Ty& val)//_P前插
			{
				_Nodeptr _S = _P._Mynode ();
				_Acc::Get_Prev(_S) = _Buynode(_Acc::Get_Prev(_S), _S);
				_S = _Acc::Get_Prev(_S);
				_Acc::Get_Next(_Acc::Get_Prev(_S)) = _S;
				new(&_Acc::Get_Value(_S)) _Ty(val);
				//定位new，能够取_S的地址，然后给其地址处构造val
				_Size++;
				return iterator(_S);
			}
			void insert(iterator _P, const _Ty* _F, const _Ty* _L)//将地址为_F到_L的全部内容插入
			{
				for (; _F != _L; _F++)
				{
					insert(_P, *_F);
				}
			}
			void insert(iterator _P, size_t count, const _Ty& val)//插入count个val
			{
				while (count--)
				{
					insert(_P, val);
				}
			}
			void insert(iterator _P, _It _F, _It _L)//插入一个新链表，_F代表begin(),_L代表_end()
			{
				for (; _F != _L; _F++)
				{
					insert(_P, *_F);
				}
			}
			void insert(iterator _P, std::initializer_list<_Ty> list)
			{
				for (auto& x : list)//将list里的值全部一个个取出来
				{
					insert(_P, x);
				}
			}
			void  push_front(const _Ty&val)
			{
				insert(begin(), val);//就是在第一个结点之前插入
			}
			void push_back(const _Ty& val)
			{
				insert(end(), val);//在头节点之前插入
			}
			void pop_front()
			{
				erase(begin());
			}
			void pop_back()
			{
				erase(end());
			}
			void erase(iterator _F, iterator _L)//从_F删到_L
			{
			/*	for (; _F != _L; ++_F)
				{
					erase(_F);
				}*/    //这样不对
				for (; _F != _L;)
				{
					erase(_F++);
				}
			}
			void clear()
			{
				erase(begin(), end());
			}
			void remove(const _Ty& val)//删除一个和val相同的节点
			{
				iterator _F = begin(), _L = end();
				while (_F!= _L)
				{
					if (*_F== val)
					{
						erase(_F);
						return;
					}
					_F++;
				}
			}
			void remove_all(const _Ty& val)//凡是和val相同都删掉
			{
				iterator _F = begin(), _L = end();
				while (_F != _L)
				{
					if (*_F == val)
					{
						erase(_F++);//不++会导致迭代器失效
					}
					else
					{
						_F++;
					}
				}
			}
			iterator erase(iterator _P)//删除之后返回下一个节点
			{
				_Nodeptr _S = _P++._Mynode();
				//_Nodeptr _S = _P.operator++()._Mynode(); 利用返回的_tmp调动_Mynode()然后对_P进行后移
				_Acc::Get_Next(_Acc::Get_Prev(_S)) = _Acc::Get_Next(_S);
				_Acc::Get_Prev(_Acc::Get_Next(_S)) = _Acc::Get_Prev(_S);
				(&_Acc::Get_Value(_S))->~_Ty();//将_S节点存储值的地址里面的内容给析构掉。
				//如果是要删除的是对象的话就需要调动析构函数，先将对象释放掉
				_Freenode(_S); 
				_Size -= 1;
				return _P;
			} 
			void Swap(list& _X)
			{
				liujin::Swap(_X._Head(), _Head);
				liujin::Swap(_X._Size, _Size);
			}
		private:
			_Nodeptr _Buynode(_Nodeptr _Parg = NULL, _Nodeptr _Narg = NULL)
			{//申请节点，然后给节点的_Next和_Prev域都进行赋值
				_Nodeptr _S = (_Nodeptr)malloc(sizeof(_Node));
				_Acc::Get_Next(_S)=_Narg == NULL ? _S : _Narg;
				_Acc::Get_Prev(_S)=_Parg == NULL ? _S : _Parg;
				return _S;
			}
			void _Freenode(_Nodeptr _p)
			{
				free(_p);
			}
			_Nodeptr _Head;//头节点地址
			size_type _Size;//链表有效节点个数
	};
}

测试函数：

#if 1
#include<iostream>
using namespace std;
#include"List.h"
int main()
{
#if 0
	liujin::list<int> ilist, ilist1;
	liujin::list<int>::iterator it = ilist.begin();
	liujin::list<int>::iterator it1=ilist1.begin();
	ilist.insert(it, 12);
	ilist.push_back(23);
	ilist.push_front(0);
	int ar[] = { 12,23,34,45,56,67,78,89,90 };
	int len = sizeof(ar) / sizeof(ar[0]);
	ilist.insert(it, ar, ar + len);//将ar中的数据元素插入
	ilist.insert(it, 10, 23);//通过迭代器插入10个23
	ilist1.insert(ilist1.begin(), ilist.begin(), ilist.end());
	for (it = ilist.begin(); it != ilist.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
	for (it1 = ilist1.begin(); it1 != ilist1.end(); it1++)
	{
		cout << *it1 << " ";
	}
	//收缩空间
	
	{
		liujin::list<int> ailist;
		ilist.Swap(ailist);
		//将ailist的生存期带出块外
	}
	return 0;
#endif
#if 0
	liujin::list<int> ilistb = { 1,2,34,5,6,7,8 };
	//利用初始化列表std::initializer_list<_Ty>来进行赋值的
	//liujin::list<int> ilist({ 2, 3, 45, 6 });
	ilistb.insert(ilistb.begin(), { 1,2,3,4,5,6 });
#endif
}
#endif
//系统list
#include<list>

#if 0
int main()
{
	int ar[10] = { 1,2,3,4,56,67,7,8,9,10 };
	int len = sizeof(ar) / sizeof(ar[0]);
	list<int> ar1;
	list<int>ar2(ar,ar+len);
	list<int>ar3(10, 23);
	ar3.insert(ar3.begin(), 24);
	for (auto it = ar3.begin(); it != ar3.end(); it++)
	{
		cout << *it << " ";
	}
}
#endif
#if 0
#include<initializer_list>//初始化列表列表
std::initializer_list<int>fun()
{
	int a = 1, b = 2, c = 3;
	return { a,b,c };//每个值都以以常引用方式返回的
	//因此返回值不能为局部变量
}
class object
{
	int val;
public:
	object(int x=0):val(x){}
};
int main()
{
	//一次返回多个值
	std::initializer_list<int>ar1 = fun();
	std::initializer_list<int> ar = { 12,23,34,45,56,67,78 };
	//int n = sizeof(ar) / sizeof(ar[0]);//注意initializer_list不可以利用下标进行访问，因为没有重载此运算符
	int n = ar.size();
	for (auto it = ar.begin(); it != ar.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
	object a(10), b(20), c(30);
	//先利用构造函数将其构造
	//利用拷贝构造，将其放入初始化列表
	std::initializer_list<object> ar3 = { a,b,c };
}
#endif
#if 0
//等价
typedef int* Pint;
using Pint = int*;
#endif