引言：

北京时间：2023/3/12/21:30，周末摆烂两天，该，刚开完班会回来，CS这个游戏真的很快乐，特别是玩狙，CS给我的快乐，大部分都是来自狙，而且是瞬狙，就是那种狙不中，但是有时候又能狙中的感觉，并且最爽的是，跟别人对狙的时候，因为我们是瞬狙，开完镜就躲，那种别人打不到我们的感觉，但是我们却有一定的概率可以打中他的感觉，真的特别爽；但是有时候也很搞笑，就是当敌人就在你脸上的时候……，OK，快乐时间结束了，咱们得干正经事了，下个周末相信我，不再摆烂，哈哈哈！相信我好吧！所以接下来，我们就继续深入STL的学习，看一下list的实现和一些有关list的小知识。

list的实现

首先STL中list类的函数大部分无论是数据结构中我们所学的有关单链表、双向循环链表（尾插、头插、任意位置插、任意位置删），还是我们前不久学的string类、vector类（构造函数、析构函数、运算符重载），通过这些知识，我们都可以很好的解决list类中的公有成员函数的使用，所以这里我们对list类中的成员函数不多做了解，我们直接进入list类的实现；

从看STL源码到list实现

文章结构大致和之前实现vector类的结构差不多，我们先一起去看一看源码中list的实现，看看大佬是如何实现list的，俗话说的好，看的东西高级了，自己写的东西也会变高级（反正意思差不多就是这样），如下图：

正式list实现

从上图我们可以知道非常多的东西，并且对我们自己实现list是有非常大的作用，例：

1. 我们知道了此时list的迭代器是自己通过封装一个__list_iterator的类来实现的，原因：list不具有像vector一样的地址连续的空间，list如果想要找下一个数据或者上一个数据，只能依靠该结点中的next、prev指针，所以我们需要通过指针的形式去封装list的迭代器；目的：就是为了让list的迭代器和vector类、string类、中的迭代器一样具有遍历、查找数据、插入、删除数据的能力。
2. 我们还可以明白，此时的list的数据结构是一个带头双向循环链表（不是不带头的单向非循环链表），并且哨兵位的头结点的初始化，是通过自己指向自己实现。
3. 我们还可以发现，上述的list在源码中是通过封装成3个基本的类（结点、迭代器、链表）实现（简易实现）。
4. 最后可以发现，在实现lis迭代器，使用模板的过程中，模板参数从以前的一个template<class T>，变成了三个template<claee T, class Ref,class Ptr>。

所以此时就让我们带着上述的现象深入到代码内部，一一看看为什么需要这样做吧！

首先根据第一点信息，并且结合第三点信息，我们可以知道，在实现list的时候，需要把list使用的迭代器给封装成一个类，所以我们就从这里入手，看一下list中的迭代器吧！

如下图：

如上图 ，我们可以发现，实现一个list迭代器，此时的迭代器实现原理已经不在是以前，但是在使用方法上却依然还是以前的使用方法，例：此时的前置++，使用目的：就是为了可以找到该数据的后一个数据，所以在list迭代器中，为了实现前置++的这个使用目的，我们就需要封装一个迭代器，然后使用list的结点类，获取结点，然后再通过next指针找到下一个位置的数据（同使用，不同实现）；可以发现和以前在vector类中迭代器的实现差异非常。当然，这也就是迭代器的好用之处，什么类型的数据结构，都可以通过封装迭代器的方式，来实现一个属于该数据结构的迭代器，获得一个匹配度超高的工具。

通过上述，我们去看一看list的结点是如何构建的，如下图：

搞定了上述两个list类中的结构体，此时我们正式进入list结构体

第一个注意点：
上述实现了list类的迭代器，所以我们在实现list结构体的时候，我们就可以直接调用迭代器，但是要注意的是，调用迭代器的规则应该要保持一致（string类、vector类），主要原因是使用方法是一致的，所以第一点注意点就是，在获取begin和end的时候，begin表示的是头结点的后一个位置，但是end表示的却是头结点的位置，因为迭代器要保持前闭后开的形式，所以end的位置就是最后一个数据的后一个位置（在带头双向循环链表）中也就是指head的位置。
如下图代码：

明白了这个，我们还需要明白一个点，就是上述的iterator、const_iterator类型都是通过我们自己实现的list迭代器结构体重定义得来的，如下图：

可以发现，我们在my_list类中，不仅可以使用迭代器类（__list_iterator），也可以使用结点类（list_node），这些都是经典的类中类的写法。

迭代器参数问题

无论是从上图，还是从list迭代器实现，我们都可以发现，迭代器的模板参数，此时和以前的模板参数不一样，不止一个，而是三个，如下图：

这是为什么呢？目的就是为了可以区分此时的迭代器是普通类型的迭代器，还是const类型的迭代器，第一个模板参数T，表示的是list中数据的类型，第二个模板参数T&/const T&，表示的就是该迭代器是普通类型，还是const类型，如下图：

如上图所示，此时我们就可以通过模板参数的形式来控制该迭代器的类型（const和非const），就不需要像下图一样，去实现两个不同类型的迭代器，如图：

很好的就减少了我们的代码量和代码冗余，实现代码更加的简洁。
但是，要注意：此时我们在理解的时候可以理解成是调用的形式，但本质上却不是，本质上是模板类实例化，构建模板之后，实现了该模板数据的代码，然后才允许使用（当然这是在编译过程中进行）

并且此时模板中的第三个参数同理

只是第二参数是供给给迭代器使用（const/非const），而第三个参数则是为了供给给指针解引用使用（同理，指针解引用时，也具有普通数据和const修饰的数据），反正就是涉及允许修改和不允许修改；

总：主要就是为了区别普通类型和const修饰的类型，防止代码冗余，使代码更加简洁

并且此时还涉及一个深浅拷贝问题

不需要在迭代器进行深拷贝的原因是：空间并不是在迭代器类中开辟的，所以不进行深拷贝也没有问题，空间是在my_list类中开辟

list较完整代码

#include<iostream>
using namespace std;

namespace wwx
{

	//第一个封装（封装结点）
	template<class T>
	struct list_node//给一个结点结构体
	{               //并且此时要注意的是：我们的这个结构体使用的也是模板参数的形式，所以在使用ListNode结构体的时候，一定要记得把它的模板参数跟上
		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 Ref,class Ptr>//此时虽然表示的就是再添加一个模板参数，但是实际上的作用是很大的（目的是为了解决const迭代器问题）
	struct __list_iterator//此时由于地址不连续，所以我们需要再封装一个迭代器（通过next）去找上一个位置和下一个位置，然后间接调用的时候，进而实现加加减减
	{
		typedef list_node<T> node;
		typedef __list_iterator<T, Ref,Ptr> iterator;

		node* _node;//此时的这个结点指针就使用来构造迭代器的
		__list_iterator(node* n)
			:_node(n)//此时要注意这个构造函数初始化，本质上是浅拷贝（由于我们这个迭代器的类中没有实现析构函数，所以并不会报错），因为并没有对同一块空间中的数据析构两次，所以浅拷贝也不怕
		{}                                                        // 本质没有析构函数是因为，结点并不是属于该迭代器的类，而是属于下面链表类，所以可以不要有析构函数
		Ref& operator*()//此时的这个Ref返回值就是这里非常经典的一个地方，怎么传，就怎么返回，如果传const类型的，就是const类型的返回值，是普通类型的，就是普通类型的返回值
		{
			return _node->_data;
		}
		Ptr operator->()//此时由于我们模拟的是指针，所以需要在重载一个->运算符
		{
			return &_node->_data;
		}
		iterator& operator++()//这边不敢傻傻分不清，知道是返回一个地址（迭代器），就是返回一个地址呗（怎么敢写成T&的，此时并不需要链表成员变量）
		{//并且此时还要分清楚类型和类名
			_node = _node->_next;//这个意思表示的就是加加
			//return _node;//妥妥的string没去实现，这里敢写成这个样子
			return *this;//注意这种没有参数的函数（可以这样写的原因都是因为有一个默认的参数this指针，所以才可以很好的找打是谁调用了这个函数，然后把返回值给给它）
			//并且由于此时这个函数表示的是前置++，所以前置加加，返回的是加加之后的值，也就是自己，所以这里可以返回*this(区别于后置加加，后置加加就不可以这样写)
		}
		iterator operator++(int)//编译器规定好了，后置加加，一定要重载的话，就是多家一个int类型的参数给给它重载，这样有利于编译器识别
		{
			iterator tmp(*this);
			_node = _node->_next;

			return tmp;//后置加加的意思：就是返回加加之前的值，所以需要把加加之前的值，先给拷贝构造一份，然后再去向后走
		}
		iterator& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		iterator operator--(int)//此时后置加加和减减不能给引用的原因是：后置加加和减减本身返回的就是一个临时的值（tmp），所以此时给不给引用都无所谓的
		{
			iterator tmp(*this);
			_node = _node->_prev;

			return tmp;//此时该变量自己本身就是一个临时变量，并不会影响到*this，所以怎么返回都行，无所谓
		}
		bool operator!=(const iterator& s)
		{
			return _node != s._node;//比较不相等，就是比较，此时结点的指针是否相等
		}//但是要注意的是：此时的_node是一个node*类型的，也就是list_node<T>*类型的，所以它里面是包含了三个成员变量的（data，_prev，_next）,所以不可依比较数据data，要比较两个指针是否相同
		bool operator==(const iterator& s)
		{
			return _node == s._node;
		}

	};

	//这个位置先浅谈一下const迭代器
	//首先我们要的是 const T* 不是 T* const
	//所以不敢写成：typedef const iterator const_iterator;//这样写就直接导致我们的迭代器不能被修改了，但是本质上我们的迭代器是地址，地址是需要改变的
	//本质上是为了地址中的数据不可以被改变而已
	



	//我终于意识到了C++的不好学，哈哈哈！头一次2

	//所以此时我们就自己实现一个const类型的迭代器

	//template<class T>   //可以看出，上面的普通迭代器类和下面的const迭代器类只要在*解引用的时候的返回值有一些不同，冗余了，所以可以直接从上面的迭代器改进
	//struct __list_const_iterator
	//{
	//	typedef list_node<T> node;
	//	typedef __list_const_iterator<T> const_iterator;

	//	node* _node;
	//	__list_const_iterator(node* n)
	//		:_node(n)
	//	{}                                      
	//	const T& operator*()//这样写，就可以让我的数据不被修改，就实现了const迭代器了
	//	{
	//		return _node->_data;
	//	}
	//	const_iterator& operator++()
	//	{
	//		_node = _node->_next;
	//		return *this;
	//	}
	//	const_iterator operator++(int)
	//	{
	//		iterator tmp(*this);																															
	//		_node = _node->_next;

	//		return tmp;
	//	}
	//	const_iterator& operator--()
	//	{
	//		_node = _node->_prev;
	//		return *this;
	//	}
	//	const_iterator operator--(int)
	//	{
	//		iterator tmp(*this);
	//		_node = _node->_prev;

	//		return tmp;
	//	}
	//	bool operator!=(const const_iterator& s)
	//	{
	//		return _node != s._node;
	//	}
	//	bool operator==(const const_iterator& s)
	//	{
	//		return _node == s._node;
	//	}

	//};	





// 从上述我们自己封装一个迭代器，我们发现了
// 1.迭代器要么就是原生指针（指针）2.要目就是自定义类型对原生指针的封装，去模拟指针的行为（如上述链表迭代器的封装），模拟的就是node*的行为（int*），本质地址不连续
















	//第三个封装（封装链表），所以前两个封装都是为了这第三个打基础而已
	template<class T>
	class my_list//此时不是那种无哨兵位的单向非循环链表，而是带头双向循环链表
	{
		typedef list_node<T> node;//此时为了防止每一次把这个模板参数T给写漏掉（是类型不是类名），此时我们就直接把它给typedef一下，这样就非常的方便

	public:
		typedef __list_iterator<T, T&, T*> iterator;//此时里面这个类和外面那个类的本质区别就是，里面这个类，属于内部类（表示封装的迭代器类本质是my_list类的类），并且没有把外面那个typedef写进来的原因是，私有成员变量有用到，并不是都是给公有函数使用的，所以定义成全局类，提供给整个类使用（而迭代器类，私有成员变量用不上，所以就可以写成内部类的写法）
		typedef __list_iterator<T, const T&, const T*> const_iterator;//通过这种多一个模板参数的形式来实现同一个迭代器实现两中类型的迭代器调用
		//typedef __list_const_iterator<T> const_iterator;//这样我们就自己实现了一个const类型的迭代器，这样const类型的begin和end函数就可以使用const迭代器了

		iterator begin()
		{
			//iterator it(_head->_next);//此时的这句代码就是在调用上述的那个迭代器（使用上面的迭代器去帮我们构造一个it出来）
			//return it;//此时要注意，只有当传上来的值和修改的值都是自己本身的时候，才return *this,而当传上来的值是自己，都返回的值不是自己的时候（是重新构造出来的），此时就应该返回那个重新构造出来的结点
			//这边反而是不喜欢上述的写法，喜欢直接使用经典的匿名对象就行替换
			return iterator(_head->_next);
		}
		const_iterator begin()const
		{
			return const_iterator(_head->_next);
		}
		iterator end()//此时这个位置我们的end给给哨兵位的意思是，我们的迭代器是左闭右开的，迭代器中最后一个位置是最后一个数据的后一个位置（所以此时表示的就是哨兵位的位置，所以不是给给_head->prev，而就是哨兵位，因为此时end是迭代器中的end）
		{
			return iterator(_head);//使用_head去构造一个迭代器对象（匿名），就是去调用上述迭代器中的构造函数，然后用括号里面的这个结点去初始化一个新的结点(这个结点就是我要的结点)
		}
		const_iterator end()const
		{
			return const_iterator(_head);//此时为什么_head是const类型，还可以改变呢？原因：表示的是_head不可以改变，但是_head中的指针（_next/_prev）是允许指向别的东西的（所以可以改变），并且由于此时是涉及拷贝问题，所以也是允许拷贝的
		}

		my_list()//带头双向循环链表 （明白此时的这个东西叫链表），所以遍历方式此时就只有使用迭代器，使用方括号和下标的方式纯属是搞笑的
		{//此时我们没有像源码一样，使用嵌套一个空初始化的函数，而是直接new
			_head = new node;//此时这个的意思表示的是开辟一个哨兵位的头结点出来(但是要注意，new后面跟的一定是一个类型，所以我们的ListNode是一个模板类型，那么此时就需要把它的模板参数给带上)
			_head->_next = _head;//然后此时让这个哨兵位的next指向自己
			_head->_prev = _head;//哨兵位的prev指针也指向自己
		}//注意：一定要把类名和类型给区分开来，类名是类名，类型是类型，类名加上模板参数就是类型
		void push_back(const T& x)//这种位置一定要搞清楚该函数的作用是什么，自然而然就知道了，我们传递的参数是什么，自然而然就知道怎么写了，最多就是多用了const+引用而已，并且一定要注意，此时的数据类型就是模板类型T
		{//这个就是普通的数据结构的写法，这边不需要太在意，带头双向循环链表，注意好头尾的位置就行
			node* tail = _head->_prev;//这句代码要注意，此时不是tail在控制_head->_prev,而是_head->_prev在控制_tail 
			node* new_node = new node(x);//注意好，此时的node是typedef过的（反正就是一个类类型的数据）例：string s1;

			tail->_next = new_node;//注意是双向循环
			new_node->_prev = tail;//注意是双向循环
			new_node->_next = _head;
			_head->_prev = new_node;//这样写就是一个经典的双向循环尾插（在哨兵位的前面找尾，然后插入，最快，根本不需要遍历）
		}
		void push_front(const T& x)
		{
			insert(begin(), x);//复用insert
			//如果是尾插的话，也是一个道理
			//insert(end(), x);//这里可以直接调用begin()或者end()的原因是，我们上述写了这两个函数，间接的通过_head获得了开始位置和最后位置
		}
		void insert(iterator pos, const T& x)
		{
			node* cur = pos._node;
			node* prev = cur->_prev;

			node* new_node = new node(x);

			prev->_next = new_node;
			new_node->_prev = prev;
			new_node->_next = cur;
			cur->_prev = new_node;
		}
		void erase(iterator pos)
		{
			assert(pos != end())//此时因为是带哨兵位的，所以不允许把哨兵位的头结点被删除(并且此时要注意的是，不可以用head去和pos比较，和pos比较需要是一个相同类型的迭代器才可以)

			node* prev = pos._node->_prev;
			node* next = pos._node->_next;

			prev->_next = next;
			next->_prev = prev;
			delete pos._node;
		}
		void pop_back()
		{
			erase(--end());//意思是end返回了一个迭代器对象，然后让这个对象去调用减减运算符，调用减减运算符的本质就是在找该结点的前一个结点
		}                  //减减的本质是因为，此时的end是迭代器中的end，是最后一个数据的下一个数据（_head），所以需要减减一下，表示的才是最后一个尾结点
		void pop_front()
		{
			erase(begin());
		}
	private:
		//struct ListNode* _head;//在C语言中正常的写法是这样的，但是在C++中的时候，就可以发现，我们不一定要跟上struct也可以
		//ListNode* _head;//记得因为是模板类型，所以要跟上模板参数
		node* _head;//看到这个就要注意是typedef过的
	};






	void print_list(const my_list<int>& lt)//此时最好是使用传引用的方式，不然一个一个数据的拷贝，代价很大
	{
		//要注意，此时的lt是一个const类型，导致权限放大了（解决方法，将begin和end函数重载一个const属性的）
		my_list<int>::const_iterator it = lt.begin();//此时还是类型和类名没有搞明白（类型就是类型，把它想象成一个类就行了，例：string）
		while (it != lt.end())
		{
		//	(*it) *= 2;//发现，此时就算是写成了const类型，此时该数据也允许被修改（所以是不对的），所以我们就需要再实现一个const类型的迭代器
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
	//测试
	void test_my_list1()//一定要记住，此时的这个链表叫做带头双向循环链表(这个链表是非常优秀的一个数据结构)，带头可以省事挺多的
	{
		my_list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);
		
	   // std::iterator it = begin();//数组使用迭代器由于空间连续所以非常的方便
	   //所以此时由于链表的地址是非连续的，就不可以使用地址加加减减
		//因为我们使用的是定义new，所有开辟的地址都是未知的、随机的
		// 
		//当我们自己封装了迭代器之后，就可以使用了
		my_list<int>::iterator it = lt.begin();
		while (it != lt.end())//此时还是类和对象的那个道理，end()不需要传参，但是默认是已经把我们的lt的地址传给了this指针，此时使用this指针就是在使用这个li对象
		{//所以此时是返回this指针，还是返回一个新的对象，就看你是否有二次用到传上去的这个对象了
			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto e : lt)//在迭代器的实现方面，vector和list差异可以说是天差地别，但是用起来却是非常的相识（原因：就是底层的封装不同）
		{
			cout << e << " ";
		}
		cout << endl;
	}

	struct AA
	{
		int _a1;
		int _a2;

		AA(int a1 = 0, int a2 = 0)
			:_a1(a1)
			, _a2(a2)
		{}
	};
	
	void test_my_list2()
	{
		my_list<AA> lt;
		lt.push_back(AA(1, 1));
		lt.push_back(AA(2, 2));
		lt.push_back(AA(3, 3));

		my_list<AA>::iterator it = lt.begin();
		while (it != lt.end())
		{
			//cout << (*it)._a1 << ":" << (*it)._a2 << endl;//这种先解引用，然后再访问的写法非常的不高级，所以我们最后是去重载一个箭头运算符出来
			cout << it->_a1 << ":" << it->_a2 << endl;//但是此时重载了箭头，会发现，此时使用起来非常的怪（感觉像是少了一个箭头，少访问了一层）, //此时就会因为运算符重载的目的是为了增强代码的可读性，所以可以省略一个箭头
			cout << it.operator->()->_a1 << ":" << it.operator->()->_a2;//上面那句代码的本质就是下面这样子的，只是把调用的过程给省略掉了
			++it;                                                
		}
		cout << endl;
	}
}

int main()
{
	wwx::my_list<int> list;
	wwx::test_my_list1();
	
}

总结：还有14分钟开始下午的第二节课，就这样吧！卡点谁有我专业。