在上一篇文章中我们详细讲解了list的使用，希望大家在了解list的实现之前一定要知道list怎么使用，链接如下：
【C++】STL基础必备：深入解析list容器的使用

一、list的结构

vector的底层本质上是一个双向带头循环链表，也就是平常所说的双链表，它的结构和各种方法的实现都和我们之前初阶数据结构写的双链表都差不多，如下：

namespace TL
{
	//list中一个节点的结构
	template<class T>
	struct list_node
	{
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;
		
		//提供一个构造函数，在new节点的时候就可以直接使用
		list_node(const T& x = T())
			:_data(x)
			,_next(nullptr)
			,_prev(nullptr)
		{}
	};
	//list宏观上的结构
	template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		//这里是list各种方法的实现
	private:
		//头结点
		Node* _head = nullptr;
		//方便记录节点个数
		size_t _size;
	}
}

总体上来说list的结构还是比较简单的，首先有一个节点的结构，然后再来一个list类来实现整个链表的管理，这样的好处就是我们以后可以非常方便的申请节点，因为我们可以在new节点的时候直接调用节点的构造，而不需要自己填充

二、list的默认成员函数

为了方便后面的讲解，我们先把list的默认成员函数实现一下

准备工作

我们都知道list是一个双链表，它有一个头结点(不保存数据，只是占位)，所以我们在支持构造为我们的链表插入数据之前，需要一个函数为我们申请这个头结点，这个头结点最开始时默认指向自己，如下：

void EmptyInit()
{
	_head = new Node;
	_head->_next = _head->_prev = _head;
}

其次我们至少需要一个尾插函数为我们提供构造的插入功能，这里我们直接给出这个尾插函数，具体实现我们在初阶数据结构就讲解过了，如果还不会的小伙伴可以参考这篇文章：【初阶数据结构与算法】线性表之链表的分类以及双链表的定义与实现

void push_back(const T& x)
{
	Node* newnode = new Node(x);
	Node* ptail = _head->_prev;
	//此时ptail就是尾结点
	ptail->_next = newnode;
	_head->_prev = newnode;
	newnode->_next = _head;
	newnode->_prev = ptail;
	_size++;
}

1. n个value的构造

顾明思义，我们需要给我们的list提供一个n个value的构造，其实就是给list插入n个相同元素，非常简单，如下：

list(size_t n = 0, const T& x = T())
{
	EmptyInit();
	for (size_t i = 0; i < n; i++)
	{
		push_back(x);
	}
}

2. initializer_list的构造

之前我们在vector的实现中介绍了一下initializer_list，编译器会将大括号中的元素用来初始化它，我们可以通过它的迭代器取出其中的元素进行尾插，这样就实现了使用大括号初始化list，如下：

list(const initializer_list<T>& il)
{
	EmptyInit();
	for (auto& e : il)
	{
		push_back(e);
	}
}

3. 一段迭代器区间的构造

在list和vector的构造中还有一个比较特殊的构造，就是使用某个容器的一段迭代器区间的元素给我们的list对象初始化， 由于我们不知道这个容器到底是什么容器，所以我们可以使用模板来接收传来的迭代器
然后再由于迭代器都支持了接引用和++，所以我们可以直接使用循环将迭代器区间中的元素取出，然后尾插到list对象中，如下：

template<class InputIterator>
list(InputIterator it1, InputIterator it2)
{
	EmptyInit();
	//迭代器区间使用左闭右开
	while (it1 != it2)
	{
		push_back(*it1);
		it1++;
	}
}

拷贝构造

拷贝构造其实就是将另一个list对象的元素全部依次插入当前对象，如下：

list(const list& lt)
{
	EmptyInit();
	Node* cur = lt._head->_next;
	while (cur != lt._head)
	{
		push_back(cur->_data);
		cur = cur->_next;
	}
	/*for (auto& e : lt)
	{
		push_back(e);
	}*/
}

它的大致遍历过程如下：

赋值重载

赋值重载也查不多和拷贝构造差不多，可以就像拷贝构造那样写，但是要注意释放当前对象之前的节点，这里我们还是写另一个巧妙的方式，那就是利用swap函数
我们可以把当前对象和形参作交换，拿到形参的头结点，除了作用域之后形参就带着之前的节点一起被释放了，如下：

//交换两个节点只需要交换它们头结点的指向和size
void swap(list& lt)
{
	std::swap(_head, lt._head);
	std::swap(_size, lt._size);
}

list& operator=(list lt)
{
	swap(lt);
	return *this;
}

析构函数

析构我们可以采用之前的遍历方式，先将有数据的节点释放掉，最后再释放头结点，如下：

~list()
{
	Node* cur = _head->_next;
	while (cur != _head)
	{
		Node* del = cur;
		cur = cur->_next;
		delete del;
	}
	delete _head;
	_head = nullptr;
}

三、list的迭代器

list的迭代器相对于vector和string就要难一些了，因为string和vector的底层其实都是数组，可以直接使用指针操作数据，迭代器也是类似于指针的操作，所以我们当时就直接将指针当作迭代器使用了
但是list不一样，它的底层是一个双链表，它的数据并不是连续存放的，并且也不能对节点进行解引用和++，这该怎么办呢？给大家2分钟的时间思考一下
这里我们就直接给出答案了，既然节点不能解引用和++，那么我们可以将节点再封装成为一个类，因为类可以重载运算符，解引用*和++都是可重载的运算符，这个类就是我们的迭代器
可能这么说大家并不是很好懂，接下来我们实操演练一下，我们先来看看这个迭代器类大致长什么样子，如下：

//将类设计为struct，默认开放出来
template<class T>
struct list_iterator
{
	typedef list_node<T> Node;
	//使用一个节点指针可以构造一个迭代器类对象
	list_iterator(Node* node)
		:_node(node)
	{}
	
	//这个类的对象只存放一个节点的指针
	//这个类可以进行解引用拿到这个节点里面的数据
	//也可以++
	Node* _node;
};

其实现在看到了结构了会好很多，本质就是节点不能解引用和++，但是我们可以把节点封装为一个类，这个类重载运算符就可以实现节点解引用和++
接下来我们思考一下节点解引用和++的本质应该会是什么，其实也不难，节点解引用其实就相当于_node->_data，因为解引用的本质就是拿到地址中的数据，而++的本质上其实就是_node = _node->_next，让内部封装的节点往后走一步
其实这样分析下来是不是没有那么难了呢？接下来我们将它们分别实现一下，如下：

template<class T>
struct list_iterator
{
	typedef list_node<T> Node;
	typedef list_iterator<T> Self;

	list_iterator(Node* node)
		:_node(node)
	{}
	
	//解引用就是返回节点中的数据
	T& operator*()
	{
		return _node->_data;
	}
	
	//这是一种特殊写法，记住就好
	T* operator->()
	{
		return &_node->_data;
	}

	//接下来是++和--的重载
	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}

	Self operator++(int)
	{
		//利用构造
		Self tmp(_node);
		_node = _node->_next;
		return tmp;
	}

	Self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}

	Self operator--(int)
	{
		//利用拷贝构造
		Self tmp(*this);
		_node = _node->_prev;
		return tmp;
	}
	
	//我们需要判断迭代器之间是否相等
	//迭代器相等其实就是内部它们内部存放的节点指针相等
	bool operator==(const Self& it)
	{
		return _node == it._node;
	}

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

	Node* _node;
};

上面就是迭代器的大致实现，最后还有一点需要更正的地方，就是我们的迭代器应该有两个版本，一个版本是普通迭代器，一个是const迭代器，它们唯一的区别就是解引用和调用->的时候一个正常返回T&和T*，而一个要返回const T&和const T*
当然我们可以直接复制粘贴再写一份const版本的，但是它们只有这两个地方不同，有没有什么办法解决呢？其实是有的，我们可以通过模板传参实现，如果传T&和T就是普通迭代器，传const T&和const T就是const迭代器，如下：

template<class T, class Ref, class Ptr>
struct list_iterator
{
	typedef list_node<T> Node;
	typedef list_iterator<T, Ref, Ptr> Self;

	list_iterator(Node* node)
		:_node(node)
	{}

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

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

	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}

	Self operator++(int)
	{
		//利用构造
		Self tmp(_node);
		_node = _node->_next;
		return tmp;
	}

	Self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}

	Self operator--(int)
	{
		//利用拷贝构造
		Self tmp(*this);
		_node = _node->_prev;
		return tmp;
	}

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

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

	Node* _node;
};

在上面的优化中，我们使用模板参数Ref和Ptr来替换两个有不同的地方，我们只需要在传参的时候做一下区别就好了，如下：

typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;

这样我们就成功将一个迭代器类封装成功了，接下来我们就实现普通迭代器和const迭代器的begin和end，我们将第一个保存数据的节点当作begin，而头结点当作end，如下：

iterator begin()
{
	//匿名对象
	return iterator(_head->_next);
}

iterator end()
{
	//隐式类型转换
	return _head;
}

const_iterator begin() const
{
	//匿名对象
	return const_iterator(_head->_next);
}

const_iterator end() const
{
	//隐式类型转换
	return _head;
}

那么我们的迭代器就实现好了，比起vector的迭代器确实难了不少，所以必须自己去写一遍才能弄懂，当然如果还有什么疑问也可以直接问我

四、修改函数

尾插、尾删、头插、头删

list的尾插、尾删、头插、头删我们在初阶数据结构那里就讲过了，这里我们不过多重复，直接给出链接，不会的小伙伴可以去看看，我们等下着重讲之前没有讲过的，链接如下：【初阶数据结构与算法】线性表之链表的分类以及双链表的定义与实现

void push_front(const T& x)
{
	Node* newnode = new Node(x);
	Node* next = _head->_next;
	_head->_next = newnode;
	next->_prev = newnode;
	newnode->_next = next;
	newnode->_prev = _head;
	_size++;
}

void pop_front()
{
	assert(_size > 0);
	Node* del = _head->_next;
	Node* next = del->_next;
	_head->_next = next;
	next->_prev = _head;
	delete del;
	_size--;
}


void push_back(const T& x)
{
	Node* newnode = new Node(x);
	Node* ptail = _head->_prev;
	//此时ptail就是尾结点
	ptail->_next = newnode;
	_head->_prev = newnode;
	newnode->_next = _head;
	newnode->_prev = ptail;
	_size++;
}

void pop_back()
{
	assert(_size > 0);
	//del是尾节点
	Node* del = _head->_prev;
	Node* newTail = del->_prev;
	_head->_prev = newTail;
	newTail->_next = _head;
	delete del;
	_size--;
}

clear

clear就是清空链表，但是要注意只是清空链表，我们的头结点不能删除，同时我们发现它和析构函数有点像，只是析构函数需要删除头结点，那么我们就把它们两个互相结合一下，如下：

//clear不删除头结点
void clear()
{
	Node* cur = _head->_next;
	while (cur != _head)
	{
		Node* del = cur;
		cur = cur->_next;
		delete del;
	}
}

~list()
{
	//析构复用clear删除除头结点以外的节点，然后删除头节点
	clear();
	delete _head;
	_head = nullptr;
}

resize

list的resize比起vector的resize更加简单，如果n比size小，那么一直删除节点，直到n等于size，如果n比size大，就一直尾插这个值，直到n等于size，如下：

void resize(size_t n, const T& x = T())
{
	if (n <= _size)
	{
		while (n != _size)
		{
			pop_back();
		}
	}
	else
	{
		while (n != _size)
		{
			push_back(x);
		}
	}
	_size = n;
}

insert

list的insert和erase与vector有点不同，它的位置只能用迭代器表示，如下：

所以我们需要利用迭代器实现insert，虽然有点不同，但是其实本质一样的，因为我们知道list的迭代器其实就是封装了一个节点，迭代器使用struct封装的，所以我们可以直接操作迭代器中封装的节点，如下：

iterator insert(iterator pos, const T& x)
{
	Node* newnode = new Node(x);
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	newnode->_next = cur;
	newnode->_prev = prev;
	prev->_next = newnode;
	cur->_prev = newnode;
	_size++;
	return iterator(newnode);
}

iterator insert(iterator pos, size_t n, const T& x)
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* newnode = new Node(x);
	//在外面将第一个插入的新节点记录下来
	Node* ret = newnode;
	for (int i = 0; i < n; i++)
	{
		//插入一个节点的逻辑
		newnode->_next = cur;
		newnode->_prev = prev;
		prev->_next = newnode;
		cur->_prev = newnode;
		//此时插入了一个节点之后，cur的前一个节点prev是newnode
		//但是cur不变
		prev = newnode;
		//申请新的节点
		newnode = new Node(x);
	}
	_size += n;
	return iterator(ret);
}

erase

erase和insert同理，除了使用迭代器，和我们初阶数据结构那里讲的一样，如下：

iterator erase(iterator pos)
{
	assert(_size > 0);
	assert(pos._node != _head);
	Node* cur = pos._node;
	Node* next = cur->_next;
	Node* prev = cur->_prev;
	next->_prev = prev;
	prev->_next = next;
	delete cur;
	_size--;
	return iterator(next);
}

五、容量接口

容量接口分别有判空和获取size，如下：

	bool empty()
	{
		return _size == 0;
	}

	size_t size()
	{
		return _size;
	}

六、访问接口

访问接口有front和back，如下：

T& front()
{
	return _head->_next->_data;
}

T& back()
{
	return _head->_prev->_data;
}

const T& front() const
{
	return _head->_next->_data;
}

const T& back() const
{
	return _head->_prev->_data;
}

七、源码

#pragma once

#include <iostream>
#include <cassert>
#include <initializer_list>
#include "Reverse_iterator.h"
using namespace std;

namespace TL
{
	template<class T>
	struct list_node
	{
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;

		list_node(const T& x = T())
			:_data(x)
			,_next(nullptr)
			,_prev(nullptr)
		{}
	};

	template<class T, class Ref, class Ptr>
	struct list_iterator
	{
		typedef list_node<T> Node;
		typedef list_iterator<T, Ref, Ptr> Self;

		list_iterator(Node* node)
			:_node(node)
		{}

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

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

		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		Self operator++(int)
		{
			//利用构造
			Self tmp(_node);
			_node = _node->_next;
			return tmp;
		}

		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		Self operator--(int)
		{
			//利用拷贝构造
			Self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

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

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

		Node* _node;
	};

	template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		typedef list_iterator<T, T&, T*> iterator;
		typedef list_iterator<T, const T&, const T*> const_iterator;

		iterator begin()
		{
			//匿名对象
			return iterator(_head->_next);
		}

		iterator end()
		{
			//隐式类型转换
			return _head;
		}

		const_iterator begin() const
		{
			//匿名对象
			return const_iterator(_head->_next);
		}

		const_iterator end() const
		{
			//隐式类型转换
			return _head;
		}

		void EmptyInit()
		{
			_head = new Node;
			_head->_next = _head->_prev = _head;
		}

		list(size_t n = 0, const T& x = T())
		{
			EmptyInit();
			for (size_t i = 0; i < n; i++)
			{
				push_back(x);
			}
		}

		template<class InputIterator>
		list(InputIterator it1, InputIterator it2)
		{
			EmptyInit();
			while (it1 != it2)
			{
				push_back(*it1);
				it1++;
			}
		}

		list(const initializer_list<T>& il)
		{
			EmptyInit();
			for (auto& e : il)
			{
				push_back(e);
			}
		}

		void swap(list& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}

		list(const list& lt)
		{
			EmptyInit();
			Node* cur = lt._head->_next;
			while (cur != lt._head)
			{
				push_back(cur->_data);
				cur = cur->_next;
			}
			/*for (auto& e : lt)
			{
				push_back(e);
			}*/
		}

		list& operator=(list lt)
		{
			if (this != &lt)
			{
				swap(lt);
			}
			return *this;
		}

		void clear()
		{
			Node* cur = _head->_next;
			while (cur != _head)
			{
				Node* del = cur;
				cur = cur->_next;
				delete del;
			}
		}

		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		void push_front(const T& x)
		{
			Node* newnode = new Node(x);
			Node* next = _head->_next;
			_head->_next = newnode;
			next->_prev = newnode;
			newnode->_next = next;
			newnode->_prev = _head;
			_size++;
		}

		void pop_front()
		{
			assert(_size > 0);
			Node* del = _head->_next;
			Node* next = del->_next;
			_head->_next = next;
			next->_prev = _head;
			delete del;
			_size--;
		}


		void push_back(const T& x)
		{
			Node* newnode = new Node(x);
			Node* ptail = _head->_prev;
			//此时ptail就是尾结点
			ptail->_next = newnode;
			_head->_prev = newnode;
			newnode->_next = _head;
			newnode->_prev = ptail;
			_size++;
		}

		void pop_back()
		{
			assert(_size > 0);
			//del是尾节点
			Node* del = _head->_prev;
			Node* newTail = del->_prev;
			_head->_prev = newTail;
			newTail->_next = _head;
			delete del;
			_size--;
		}

		iterator insert(iterator pos, const T& x)
		{
			Node* newnode = new Node(x);
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			newnode->_next = cur;
			newnode->_prev = prev;
			prev->_next = newnode;
			cur->_prev = newnode;
			_size++;
			return iterator(newnode);
		}

		iterator insert(iterator pos, size_t n, const T& x)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(x);
			//在外面将第一个插入的新节点记录下来
			Node* ret = newnode;
			for (int i = 0; i < n; i++)
			{
				//插入一个节点的逻辑
				newnode->_next = cur;
				newnode->_prev = prev;
				prev->_next = newnode;
				cur->_prev = newnode;
				//此时插入了一个节点之后，cur的前一个节点prev是newnode
				//但是cur不变
				prev = newnode;
				//申请新的节点
				newnode = new Node(x);
			}
			_size += n;
			return iterator(ret);
		}

		iterator erase(iterator pos)
		{
			assert(_size > 0);
			assert(pos._node != _head);
			Node* cur = pos._node;
			Node* next = cur->_next;
			Node* prev = cur->_prev;
			next->_prev = prev;
			prev->_next = next;
			delete cur;
			_size--;
			return iterator(next);
		}

		bool empty()
		{
			return _size == 0;
		}

		size_t size()
		{
			return _size;
		}

		T& front()
		{
			return _head->_next->_data;
		}

		T& back()
		{
			return _head->_prev->_data;
		}

		const T& front() const
		{
			return _head->_next->_data;
		}

		const T& back() const
		{
			return _head->_prev->_data;
		}

		void resize(size_t n, const T& x = T())
		{
			if (n <= _size)
			{
				while (n != _size)
				{
					pop_back();
				}
			}
			else
			{
				while (n != _size)
				{
					push_back(x);
				}
			}
			_size = n;
		}

	private:
		Node* _head = nullptr;
		size_t _size = 0;
	};

	template<class T>
	void swap(list<T>& lt1, list<T>& lt2)
	{
		lt1.swap(lt2);
	}
}

那么今天关于list的实现就讲到这里，有什么不懂欢迎私信问我，我会及时做出解答，下一篇文章开始我们学习栈和队列的使用和实现，敬请期待吧！
bye~