list容器&&模拟实现函数解析

一、list容器使用介绍

(1)list介绍:

概念：
list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。 list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。list指针使用类来封装的。
对比：
list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能向前迭代，已让其更简单高效。与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第1个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息。
(2)list使用：

1.list的构造

list (size_type n, const value_type& val = value_type()) ：构造的list中包含n个值为val的元素。
list() ：构造空的list。
list (const list& x) ：拷贝构造函数。
list (InputIterator first, InputIterator last) ：用[first, last)区间中的元素构造list。

2.list iterator 起始终止使用

begin +end：返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器。
rbegin +rend：返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置。

3.list增删查改

push_front ：在list首元素前插入值为val的元素
pop_front： 删除list中第一个元素
push_back ：在list尾部插入值为val的元素
pop_back ：删除list中最后一个元素
insert ：在list position 位置中插入值为val的元素
erase ：删除list position位置的元素
swap ：交换两个list中的元素
clear ：清空list中的有效元素
find ：查找（这个是算法库函数里的，不是容器接口）

4.list空间增长和个数接口

size ：获取数据个数
capacity ：获取容量大小
empty ：判断是否为空
resize： 改变vector的size
reserve ： 改变vector的capacity

二、list容器模拟实现及函数解析

2.1 list结构体创建

     template<class T>
	 struct list_node
	  {
		 list_node<T>* _next;
		 list_node<T>* _prev;
		 T _data;
		list_node(const T& x =T())
			:_next(nullptr)
			, _prev(nullptr)
			, _data(x)
		{}
	};

因为它是一个带头的双向循环链表，里面啊穿件一个next指针和一个前驱指针，以及数据data变量，并在里面构建默认构造函数，里面提供匿名对象，因为有可能传的是自定义类型。

2.2 迭代器封装

这里的list迭代器本质上是自定义类型对原生指针的封装，模拟指针的行为，因为list物理结构是不连续的啊，迭代器有++或者–这时候需要对它进行重新定义，需要进行运算符重载。为了它行为像指针一样，只能通过一个类来描述它。所以list的迭代器是一个类对象，这里为了能直接访问我们用struct来定义类。
先拿取部分代码如下：

template<class T,class Cst,class P>
	struct list_iterator
	{
		typedef list_node<T> node;
		typedef list_iterator<T,Cst,P> self;
		node* _node;
		list_iterator(node* n)
			:_node(n)
		{}
		P operator->()
		{
			return &(_node->_data);
		}
		Cst operator *()
		{
			return _node->_data;
		}
		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;
		}
		bool operator!=(const self& s)
		{
			return _node != s._node;
		}
		bool operator==(const self& s)
		{
			return _node == s._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;

		list()
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}
		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);
		}
	}

在代码里面无论是返回类型还是创建的临时变量，都需要写一个很长的一个类型名，为了使用方便，在list中把list中的结点结构体类型list_node<T>和普通迭代器list_iterator<T,T&,T*> 及const迭代器list_iterator<T, const T&,const T*>还有迭代器中的list_node<T>和list_iterator<T,Cst,P>进行重定义。增加的另外俩个模板参数下面会分析。

2.21 构造函数：

里面必须得有构造函数，因为编译器自动生成的满足不了我们的需求。要把_node初始化为我们想要的。

2.22 前置++和后置++及- -

前置++返回的是加加后的结果，直接先更新_node,再直接返回this指向的内容，因为这里的迭代器不会销毁，用引用返回。返回的还是一个迭代器直接替换为self&。下面也同理。
后置++返回的是加加之前的结果，所以需要一个临时变量，存放++之前的结果，然后再进行加加。因为这里是一个临时对象，出了作用域会销毁，所以这里使用引用返回。
前置- -，和后置- -出了更新不同，它使用的是前驱指针，其他逻辑和++相同。

2.23 解引用

解引用就直接返回它的数据，由于以后会对list中的数据进行访问，所以这要引用返回T&。

2.24 判断相等

直接返回的时候 判断相等，也就是this指向的迭代器和右面传回来的迭代器进行比较。

2.25 箭头重载

普通指针，原生指针，内置类型的指针就用解引用就可以，如果是实例化一个结构体，打印的时候，自定义类型还需要流插入运算符重载，如果是私有必选重载，现在里面是公有不想重载，这就要用到箭头，所以在迭代器里面重载一个operator箭头，打印写的时候只需要写一个箭头，是了为了提高可读性，编译器进行了简化，省略一个箭头。
而箭头访问成员变量左面必须得是指针，也就是结构指针访问成员，而（*）.是用于结构体变量访问成员，在迭代器箭头重载里面，通过箭头拿到数据，再引用拿到数据的地址即可，再加上编译器的增加箭头就可访问具体成员。

2.26 第二个和第三个模板参数以应对const情况

第一个模板参数：
使用begin函数时候，如果是const对象的时候会发生什么，比如下面代码：

void input_list(const nza::list<int> & v)
{
	nza::list<int> ::iterator p = v.begin();
	while (p != v.end())
	{
		(*p) *= 2;
		cout << *p << " ";
		++p;
	}
	cout << endl;
}

这里编译报错，这里权限放大，对象调用成员函数得传递this指针，这地方的对象是const，取地址是const list int* ，不能传给普通的this。这里要重载两个函数，在begin，end成员函数后面加const。就能编译成功。

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

为什么const能构造普通的迭代器：按理说这里加了const后，它所指向内容就不能修改，这里变成可读可写的普通迭代器了，但迭代器所因为这里的const修饰的this即this指向的内容，它指向的内容是_head指针，修饰的是_head指针本身，也就是说在const情况下修饰的是_head不能被改变，并不是_head指向的内容不能改变，所以这个结点的指针是它本身不能改变，但是能拷贝给别人。
这里的记结果最终不仅能遍历还能修改它的数据，能修改就是因为构造了普通迭代器，普通迭代器是可读可写的。
解决：
库里面是这样做的，如果是一个const对象的时候，对它进行了限制，const对象调用的是const begin，返回的是一个const迭代器。
const迭代器和普通迭代器的区别是指针指向的内容不可修改，不能用typedef const iterator const_iterator 这就相当于const修饰的是迭代器这个类，而成员变量不可修改，成员变量是指针，普通跌迭代器相当于T，而上面的是相当于T* const`，这个意思是保证迭代器本身不会被修改，内容可修改，我们想要的是指向的内容不可修改。

只需要在解引用前面加上const，控制这个返回值不一样，但是不能在同一个类中增加一个const& 函数，因为返回类型不同不能重载，这时候思路是再创建一个const_iterator迭代器，但是又太冗余。

这时候为了使代码更简洁，，使代码适应性更强，在迭代器的类模板增加一个模板参数Cst，而在list类中，给迭代器类不同类型的模板的参数，如果是普通迭代器传T&，如果是const迭代器就传const&。使用哪种迭代器，就会使用哪种模板参数进行实例化，就是用这个类型的时候，编译器就会把T替换对应的类型。
第三个模板参数：
在箭头运算符重载函数中，返回类型是T*，如果来一个const对象，继续使用不符合const的性质，const T 类型无法构成重载，所以在迭代器模板参数里面再增加一个参数P就能解决，把T换成P，在list把iterator，const_iterator分别增加一个T和一个const T，就能解决，让编译器根据具体情况去实例化

2.3 在pos位置插入

	   void insert(iterator pos,const T& x)
		{
			node* cur = pos._node;
			node* prev = cur->_prev;
			node* Newnode = new node(x);
			prev->_next = Newnode;
			Newnode->_next = cur;
			Newnode->_prev = prev;
			cur->_prev = Newnode;

		}

如果不用struct用class 去加私有封装，在这要么用友元要么getnode，所以迭代器一般用struct，在里面用这个迭代器去取这个指针，这里用pos迭代器取取出当前指针，在pos前插入，再定义一个前驱指针，然后开一个结点，进行链接。后面四部是链接过程。

2.4 头插

       void push_front(const T& x)
		{
			insert(begin(), x);
		}

直接复用插入函数，就是在第一个结点的前面进行插入，begin位置进行插入。

2.5 尾插

       void push_back(const T& x)
		{
			/*node* newnode = new node(x);
			node* tail = _head->_prev;
			tail->_next = newnode;
			newnode->_prev=tail;
			newnode->_next = _head;
			_head->_prev = newnode;*/
			insert(end(), x);

		}

这里可以用传统的方法也是直接复用插入函数，就是在end的前面插入也即end指向前面的下一个。

2.6 删除pos位置

       iterator erase(iterator pos)
		{
		    assert(pos!=end());
			node* net = pos._node->_next;
			node* prev=pos._node->_prev;
			prev->_next = net;
			net->_prev = prev;
			delete pos._node;
			return iterator(net);
		}

先加一个断言，头结点不能删除。定义一个net指针表示当前位置的下一个位置，再定一个前驱指针表示当前位置的前面的，然后直接把它俩进行链接，释放当前结点，因为考虑到迭代器失效，要给一个返回值，也就是删除位置下一个结点，不然无法遍历。

2.7 尾删

       void pop_back()
		{
			erase(--end());
		}

直接复用删除函数，因为尾删，删的是头结点上一个，里面返回的是一个迭代器对象直接调用前置- -。

2.8 头删

        void pop_front()
		{
			erase(begin());
		}

也是复用删除函数，头删就是删第一个也即是删除begin位置。

2.9 析构和清理函数

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

		}
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{

				erase(it++);
			}
		}
		

在clear函数如果直接erase(it)，迭代器会失效，最好返回当前位置的下一个位置，两种方法，一种是是接收一下，二种是在里面it++，因为这是后置++，返回的是临时变量，是it的拷贝，所以这里删除的是it的拷贝。但是clear函数不删除头结点。
析构函数先调用clear函数把head以后的结点删除，再释放头结点，在把头结点置空。

3.1 swap交换函数

        void swap(list<T>& tmp)
		{
			std::swap(_head, tmp._head);
		}

3.2 拷贝构造函数

        list(const T& it)
		{
			/*init();
			for (auto e : it)
			{
				push_back(e);
			}*/
			init();
			list<T>tmp(it.begin(), it, end());
			swap(tmp);
		}

拷贝构造使用第一种方法，就可以拷贝嵌套list和string等自定义类型，如果里面是一个list，用init函数解决了外部的拷贝，里面开了一个新的头结点的空间，而在push_back的时候，调用insert里面开除新结点，最重要的点是新结点中的_data，它存的是拷贝的自定义类型，这个新_data变量的地址和旧结点的地址是不一样的，因为开新结点，就意味着T _data,进行实例化，变量是新空间开的是新地址，而在释放结点摧毁里面的变量时或改变里面其中一个内容不会互相影响，或者说就不存在指向同一块的空间的问题即深拷贝问题。如土_data地址不一样已得到验证：

使用第二种方法：先在内部进行创建一个头结点，之后调用迭代器初始化构造tmp对象，里面形成了一个新的初始化的链表，最后用swap函数交换tmp的头指针和刚刚创建的头指针也即是this指向的头指针。

3.3 使用迭代器进行初始化构造

        template<class Iterator>
		list(Iterator first, Iterator last)
		{
			init();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

也就是先初始化，把某种迭代器的区间的内容进行尾插到实例化对象的空间中去。

3.4 构造的list中包含n个值为val的元素

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

先初始化，再用一个for循环，进行尾插n个val。

3.5 赋值重载函数

	  list<T>& operator=(list<T> it)
		{
			swap(it);
			return *this;
		}

这里是用swap的时候在里面要传值，如果传引用，交换的时候等号右边的内容会发生变化，我们需要传值，就会调用拷贝构造，it就是等号右边的拷贝，拷贝是等号左边想要的不是右边想要的的，不能让右变的发生变化。所以交换后直接返回*this。

三、list迭代器失效

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
在insert时这里的迭代器pos不会失效，因为这里pos始终指向这个结点，并且这个位置关系不会变，不像vector插入删除数据就算不扩容，也要挪动数据，因为数据相对位置已经发生改变，他已经不是指向之前的位置了。它俩形成鲜明对比。如图：


而在使用**erase()**函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值如图：

四、list模拟实现代码

(1)simulate_list

#pragma once
#include<assert.h>
namespace nza
{

	

	template<class T>
	struct list_node
	{
		 list_node<T>* _next;
		 list_node<T>* _prev;
		 T _data;
		list_node(const T& x =T())
			:_next(nullptr)
			, _prev(nullptr)
			, _data(x)
		{}
	};


	template<class T,class Cst,class P>
	struct list_iterator
	{
		typedef list_node<T> node;
		typedef list_iterator<T,Cst,P> self;
		node* _node;
		list_iterator(node* n)
			:_node(n)
		{}
		P operator->()
		{
			return &(_node->_data);
		}
		Cst operator *()
		{
			return _node->_data;
		}
		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;
		}
		bool operator!=(const self& s)
		{
			return _node != s._node;
		}
		bool operator==(const self& s)
		{
			return _node == s._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;
		void init()
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}
		list()
		{
			init();
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;

		}
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{

				erase(it++);
			}
		}
	    template<class Iterator>
		list(Iterator first, Iterator last)
		{
			init();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		void swap(list<T>& tmp)
		{
			std::swap(_head, tmp._head);
		}
		list(const list<T>& it)
		{
			init();
			for (auto e : it)
			{
				push_back(e);
			}
			/*init();
			list<T> tmp(it.begin(), it. end());
			swap(tmp);*/
		}

	    list (size_t n, const T& val = T())
		{
			    init();
				for (size_t i = 0; i<n; ++i)
				{
					push_back(val);
				}
		}
		list<T>& operator=(list<T> it)
		{
			swap(it);
			return *this;
		}
		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);
		}
		void push_back(const T& x)
		{
			/*node* newnode = new node(x);
			node* tail = _head->_prev;
			tail->_next = newnode;
			newnode->_prev=tail;
			newnode->_next = _head;
			_head->_prev = newnode;*/
			insert(end(), x);

		}
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		void insert(iterator pos,const T& x)
		{
			node* cur = pos._node;
			node* prev = cur->_prev;
			node* Newnode = new node(x);
			prev->_next = Newnode;
			Newnode->_next = cur;
			Newnode->_prev = prev;
			cur->_prev = Newnode;

		}
		iterator erase(iterator pos)
		{
			assert(pos != end());
			node* net = pos._node->_next;
			node* prev=pos._node->_prev;
			prev->_next = net;
			net->_prev = prev;
			delete pos._node;
			return iterator(net);
		}
		void pop_back()
		{
			erase(--end());
		}
		void pop_front()
		{
			erase(begin());
		}
		
	private:
		node* _head;
	};
}

(2)test.cpp

#include<iostream>
#include"simulate_list.h"
#include<list>

using namespace std;
void test1()
{
	nza::list<int> v;
	v.push_back(9);
	v.push_back(5);
	v.push_back(3);
	nza::list<int> ::iterator p = v.begin();
	for (auto n : v)
	{
		cout << n << " ";
	}
	cout << endl; 
}
void input_list(const nza::list<int> & v)
{
	nza::list<int> ::const_iterator p = v.begin();
	while (p != v.end())
	{
	/*	(*p)*= 2;*/
		cout << *p << " ";
		++p;
	}
	cout << endl;
}
void test2()
{
	nza::list<int>l;
	l.push_back(4);
	l.push_back(6);
	l.push_back(8);
	input_list(l);

}
struct M
	{
		int _a1;
		int _a2;
		M(int a1 = 0, int a2 = 0)
			:_a1(a1)
			, _a2(a2)
		{}
	};
void test3()
{
	
	nza::list<M> q;
	q.push_back(M(3, 7));
	q.push_back(M(22, 22));
	q.push_back(M(44, 66));
	nza::list<M> ::iterator p = q.begin();
	while (p != q.end())
	{
	cout << p->_a1 << " ";
	++p;
	}
	cout << endl;
}
void test4()
{
	nza::list<int> l;
	l.push_back(99);
	l.push_back(88);
	l.push_back(77);

	for (auto e : l)
	{
		cout << e << " ";
	}
	cout << endl;

	l.push_back(66);
	l.push_front(55);

	for (auto e : l)
	{
		cout << e << " ";
	}
	cout << endl;

	l.pop_back();
	l.pop_front();

	for (auto e : l)
	{
		cout << e << " ";
	}
	cout << endl;
	l.clear();
	for (auto e : l)
	{
		cout << e << " ";
	}
	cout << endl;
}
void test5()
{
	nza::list<std::list<int>> v3(3,{1,2,3});
	for (auto e : v3)
	{
	/*	cout << e << " "*/
	}
	//cout << endl;
	nza::list<std::list<int>> v4(v3);
	for (auto e : v4)
	{
		/*cout<<e<<" ";*/
	}
	//cout << endl;
}
int main()
{
	test1();
	test2();
	test3();
	test4();
	test5();
}

(3)测试结果

五、vector和list容器对比

底层结构：
vector是动态顺序表，一段连续空间，list是带头结点的双向循环链表。
随机访问：
vector支持随机访问，访问某个元素效率O(1)，而list不支持随机访问，访问某个元素效率O(N)。
插入与删除：
任意位置插入和删除效率低，需要挪动元素，时间复杂度为O(N)，插入时有可能需要扩容，扩容就需要开辟新空间，拷贝元素，释放旧空间，导致效率更低，而list任意位置插入和删除效率高，不需要诺丁元素，时间复杂度为O(1)。
迭代器：
vector是原生态指针，这不能绝对例如VS是封装的，list对原生态指针即节点指针进行封装。
空间利用率：
vector底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高，而list底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低。
使用场景：
vector需要高效存储，支持随机访问，不关心插入删除效率，而list大量插入和删除操作，不关心随机访问。
迭代器失效：
在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效，而list插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响

六、总结与补充

总结：
原生指针只是一个偶然，用来类去封装才是常态，底层的本质都可以认为是指针，只是说嵌入了一个自定义类型，去封装它，语法这个行为就把他识别为自定义类型，自定义用这个运算符就是重载运算符，比如解引用，++等到底是怎么样的行为是另回事，因为函数是我们实现的。const在定义对象的那一下是没有const属性的，这是编译器的特殊处理。
补充：
list<int>::iterator p =v.begin(),这里要调用一个拷贝构造，这里没有写拷贝构造，编译器默认生成了一个拷贝构造，它是一个浅拷贝，begin返回一个临时对象包含了开始结点的指针，把这个结点的位置赋值给p，也是期望这里有个p对象，对象里面有个结点指针也就是指向首位置，不是有结点指针就得深拷贝。
同时指向了一个位置，但并没有报错，因为迭代器没有写析构函数，不需要释放结点，虽然有结点指针，这不属于迭代器，只是给迭代器进行封装，帮助它实现遍历链表++修改链表，不支持释放，释放是链表的事,另外结点也不是它创建的，总来的的说浅拷贝没问题。