STL？list！！！

一、引言

        之前我们一起完成了STL库中的vector，本期我们将一起完成list这一容器，在本期学习中，我们会更加加深对于模板的认识，让我们更加能感受到模板的魅力！

二、list的介绍与相关接口

        list是STL库中提供的一个链表容器，它是一个带头双向循环链表，事实上它的结构比较复杂，但是接口的实现相对简单，在实现该容器时，我们的重点将是如何正确、高效的使用模板的相关知识来简化代码、提升代码可读性

        在本文接下来的部分会介绍list的常用接口，事实上借助这些接口就可以解决平常所能遇到的大部分问题，如果还需要了解list提供的更多接口及使用方法的话，可以跳转到以下网页：

        list - C++ Reference

三、手撕一个list

        1、list的基本框架及其成员变量

        list是一个带头双向循环链表，对于list本身来讲我们只需要一个指向哨兵位的指针就可以管理整个链表，但是对于一个链表来说，我们还需要一个一个的节点来存储相关的数据，所以我们首先需要定义两个类，一个类用来管理链表的相关方法，另一个类用来管理一个一个的节点：

        在上面我已经完成了list_node的构造函数，在后面使用时我们只需要传给它一个T对象，它就可以帮助我们构造出一个节点

        2、构造函数

        库中的函数头：

        在这里说明一下，alloc是一个内存池，上面的缺省参数是STL库中提供的一个内存池，正常情况下是够用的，在以后的内容中我们会实现一个内存池，当下我们先忽略掉这个部分

        同时，构造函数还有其它重载，有的在这里不实现，在后面的插入函数实现之后我们通过复用来实现，有的不做实现

        对于一个带头双向循环链表来说，它天生一定不为空，在最开始的时候就一定、有一个哨兵位，同时该哨兵位的向前指针和向后指针都指向自己，天然的是一个双向循环链表：

        3、头插与尾插

                (1).头插函数：在链表的哨兵位之后插入一个节点

                库中的函数头：

                在实现插入相关函数的时候，一定要注意指针变向的顺序：

                (2).尾插函数：在链表的末尾，也就是哨兵位之前插入一个节点

                库中的函数头：

                实现：

        4、构造函数

        库中的函数头：

        在实现了插入函数之后，我们就可以实现上面使用n个T对象构造链表的构造函数了：

        5、拷贝构造函数

        库中的函数头：

        实现该函数，我们可以直接复用之前实现过的插入相关函数，直接对一个新对象不断尾插即可：

        6、交换函数

        库中的函数头：

        实现该函数可以借用一下算法库中实现的swap函数实现深层次的交换：

        7、赋值运算符重载

        库中的函数头：

        实现：

         对于赋值运算符重载，我们复用了上面的swap函数，同时我们的实现与库中的实现略有差异，在传参时我们采用了传值传参，这时候形参是实参的拷贝，调用我们刚才实现过的拷贝构造函数实现深拷贝，接着将*this与形参x交换，最后借助析构函数(后文会实现)对形参完成释放

        8、迭代器的实现及相关运算符重载和迭代器相关函数

                (1).迭代器类的定义

                list是一个带头双向循环链表，在物理结构上数据与数据之间并不是连续的，对于平常的指针来讲，我们不能通过++、--等运算符直接跳到下一个数据的位置，所以对于list来讲我们不能直接使用指针来充当迭代器，但是很显然Node*类型的指针是实现迭代器的最佳选择，所以我们要封装这个指针，从而让它来充当迭代器，由于C++中并不喜欢使用内部类来实现类内定义类型，所以我们采用封装一个迭代器类同时在list类中实现typedef，接下来我们一起完成这样一个迭代器类：

	template 
	struct list_iterator
	{
		typedef list_node Node;
		//成员变量
		Node* _node;
		//构造函数
		list_iterator(Node* node):
			_node(node){}
		//运算符重载
		//前置++
		list_iterator& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//后置++
		list_iterator operator++(int)
		{
			list_iterator tmp = *this;
			_node = _node->_next;
			return tmp;
		}
		//前置--
		list_iterator& operator--()
		{
			_node = _node->_front;
			return *this;
		}
		//后置--
		list_iterator operator--(int)
		{
			list_iterator tmp = *this;
			_node = _node->_front;
			return tmp;
		}
		//+操作符重载
		list_iterator operator+(int x)
		{
			list_iterator tmp = *this;
			while (x--)
			{
				tmp++;
			}
			return tmp;
		}
		//-操作符重载
		size_t operator-(list_iterator it)
		{
			size_t ret = 0;
			while (it._node != _node)
			{
				ret++;
				it._node = it._node->_next;
			}
			return ret;
		}

                对于正常的使用来说，上面的迭代器类已经可以正常的跑通范围for了，但是，接下来的问题是，我们怎么样定义出const_iterator呢？显然的方法是将上面的类复制以下，将‘*’操作符的重载返回值改变以下，再将‘->’操作符重载的返回值改变以下即可，但是对于两个如此相像的类，我们如果采用这样的方法代码复用率过低，这时候我们便可以想到使用模板的知识，在类模板参数部分多给几个参数：

template 
struct list_iterator
{
	typedef list_node Node;
	//成员变量
	Node* _node;
	//构造函数
	list_iterator(Node* node):
		_node(node){}
	//运算符重载
	//前置++
	list_iterator& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	//后置++
	list_iterator operator++(int)
	{
		list_iterator tmp = *this;
		_node = _node->_next;
		return tmp;
	}
	//前置--
	list_iterator& operator--()
	{
		_node = _node->_front;
		return *this;
	}
	//后置--
	list_iterator operator--(int)
	{
		list_iterator tmp = *this;
		_node = _node->_front;
		return tmp;
	}
	//+操作符重载
	list_iterator operator+(int x)
	{
		list_iterator tmp = *this;
		while (x--)
		{
			tmp++;
		}
		return tmp;
	}
	//-操作符重载
	size_t operator-(list_iterator it)
	{
		size_t ret = 0;
		while (it._node != _node)
		{
			ret++;
			it._node = it._node->_next;
		}
		return ret;
	}
	//!=操作符重载
	bool operator!=(list_iterator it)
	{
		return it._node != _node;
	}
	//==操作符重载
	bool operator==(list_iterator it)
	{
		return it._node == _node;
	}
	//*操作符重载
	Ref operator*()
	{
		return _node->_val;
	}
	//->操作符重载
	Ptr operator->()
	{
		return &_node->_val;
	}
};

                在定义完成上面的迭代器类之后，我们只需要在list类中再将两种迭代器分别进行typedef即可：

typedef list_iterator iterator;
typedef list_iterator const_iterator;

                (2).迭代器相关函数

//迭代器相关函数
iterator begin()
{
	return head->_next;
}
iterator end()
{
	return head;
}
const_iterator begin() const
{
	return head->_next;
}
const_iterator end() const
{
	return head;
}

        9、在指定位置插入函数--insert

        库中的函数头：

        insert函数可以在pos之前位置插入val：

        10、将指定位置的元素删除--erase

        库中的函数头：

        erase函数可以将pos位置的元素删除：

        11、将链表中的元素清空--clear

        库中的函数头：

        clear函数可以将链表中的元素清空：

        12、析构函数

        由于析构函数的特殊性，在这里就不再展示库中的函数头：

四、list

        下面就是我们今天实现的list了：

namespace bea
{
	template 
	struct list_node
	{
		//成员函数
		
		//构造函数
		list_node(const T& val = T())
			:_val(val)
			,_front(nullptr)
			,_next(nullptr)
		{}
		//成员变量
		list_node* _front;
		list_node* _next;
		T _val;
	};
	template 
	struct list_iterator
	{
		typedef list_node Node;
		//成员变量
		Node* _node;
		//构造函数
		list_iterator(Node* node):
			_node(node){}
		//运算符重载
		//前置++
		list_iterator& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//后置++
		list_iterator operator++(int)
		{
			list_iterator tmp = *this;
			_node = _node->_next;
			return tmp;
		}
		//前置--
		list_iterator& operator--()
		{
			_node = _node->_front;
			return *this;
		}
		//后置--
		list_iterator operator--(int)
		{
			list_iterator tmp = *this;
			_node = _node->_front;
			return tmp;
		}
		//+操作符重载
		list_iterator operator+(int x)
		{
			list_iterator tmp = *this;
			while (x--)
			{
				tmp++;
			}
			return tmp;
		}
		//-操作符重载
		size_t operator-(list_iterator it)
		{
			size_t ret = 0;
			while (it._node != _node)
			{
				ret++;
				it._node = it._node->_next;
			}
			return ret;
		}
		//!=操作符重载
		bool operator!=(list_iterator it)
		{
			return it._node != _node;
		}
		//==操作符重载
		bool operator==(list_iterator it)
		{
			return it._node == _node;
		}
		//*操作符重载
		Ref operator*()
		{
			return _node->_val;
		}
		//->操作符重载
		Ptr operator->()
		{
			return &_node->_val;
		}
	};
	template 
	class list
	{
		typedef list_node Node;
		//成员函数
	public:
		typedef list_iterator iterator;
		typedef list_iterator const_iterator;
		//迭代器相关函数
		iterator begin()
		{
			return head->_next;
		}
		iterator end()
		{
			return head;
		}
		const_iterator begin() const
		{
			return head->_next;
		}
		const_iterator end() const
		{
			return head;
		}
		//构造函数
		//空构造
		explicit list()
		{
			head = new Node;
			head->_front = head;
			head->_next = head;
		}
		//用n个对象构造
		explicit list(size_t n, const T& val = T())
		{
			if (head == nullptr)
			{
				head = new Node;
				head->_front = head;
				head->_next = head;
			}
			int ntmp = n;
			while (ntmp--)
			{
				push_back(val);
			}
		}
		//拷贝构造函数
		list(const list& x)
		{
			Node* cur = x.head->_next;
			while (cur != x.head)
			{
				if (head == nullptr)
				{
					head = new Node;
					head->_front = head;
					head->_next = head;
				}
				push_back(cur->_val);
				cur = cur->_next;
			}
		}
		//头插函数
		void push_front(const T& val)
		{
			Node* newnode = new Node(val);
			newnode->_front = head;
			newnode->_next = head->_next;
			head->_next = newnode;
			newnode->_next->_front = newnode;
		}
		//尾插函数
		void push_back(const T& val)
		{
			Node* newnode = new Node(val);
			newnode->_next = head;
			newnode->_front = head->_front;
			head->_front = newnode;
			newnode->_front->_next = newnode;
		}
		//insert函数
		iterator insert(iterator pos, const T& val)
		{
			Node* x = pos._node;
			Node* newnode = new Node(val);
			newnode->_front = x->_front;
			newnode->_next = x;
			x->_front = newnode;
			newnode->_front->_next = newnode;
			return (iterator)newnode;
		}
		//erase函数
		iterator erase(iterator pos)
		{
			Node* eaim = pos._node;
			Node* ret = eaim->_next;
			eaim->_next->_front = eaim->_front;
			eaim->_front->_next = eaim->_next;
			delete eaim;
			return ret;
		}
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
		//交换函数
		void swap(list& x)
		{
			std::swap(x.head, head);
		}
		//赋值运算符重载
		list& operator=(const list x)
		{
			swap(x);
			return *this;
		}
		//打印函数
		void Print()
		{
			Node* cur = head->_next;
			cout _next;
			}cout