[数据结构与算法] 【C++初阶：STL —— list】list的介绍及使用 | list的深度剖析及模拟实现

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【C++初阶：STL —— list】list的介绍及使用 | list的深度剖析及模拟实现 | list与vector的对比 -> 正文阅读

[数据结构与算法]【C++初阶：STL —— list】list的介绍及使用 | list的深度剖析及模拟实现 | list与vector的对比

文章目录

【写在前面】

在学完 list，大家对 STL 中的迭代器的认知会进一步提高。list 用的虽然不多，但是它的底层有很多经典的东西，尤其是它的迭代器。list 的结构对我们来说应该问题不大，因为在《数据结构》时我们就已经了解过链表了，它的结构是一个带头双向循环链表，之前我们也实现过。

对于 list 没有 reserve 和 resize，因为它的底层不是连续的空间，它是用一个申请一个，不用一个就释放一个。也没有 operator[]，因为它不支持随机访问。同时它有头插、头删、尾插、尾删、任意位置的插入、删除。因为 list 是带头双向循环链表。

有了前面 string 和 vector 的铺垫，我们这里对于 list 的使用就大概过一下即可，因为它们比较类似，重点主要放在 list 的深度剖析及模拟实现。

其实来严格来说 C++ 的 list 有两个：
在这里插入图片描述

<list> 是带头双向循环链表，是我们本章需要学习的知识
<forward_list> 是单链表，它是 C++11 所增加的，它的使用场景一点也不多，查看文档，可以看到它不支持尾插、尾删，因为对于单链表效率很低。并且它的任意位置插入、删除是在当前位置之后，因为当前位置之前得找前一个，也是一个 O(N) 的实现。单链表对比双向链表的唯一优势就是每个节点少存一个指针。

一、list的介绍及使用

💦 list的介绍

list的文档介绍

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

💦 list的使用

1、list的构造

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

#include<iostream>
#include<vector>
#include<list>
using namespace std;

namespace std
{
	void test_list1()
	{
		list<int> lt1;
		list<int> lt2(10, 5);
		list<int> lt3(lt2.begin(), lt2.end());
		//同样支持用其它容器的迭代器区间去构造,因为它是模板,并且它可以支持如下写法
		vector<int> v = { 1, 2, 3, 4, 5 };
		list<int> lt4(v.begin(), v.end());	
		list<int> lt5(lt4);
	}
}
int main()
{
	std::test_list1();
	return 0;	
}

2、list iterator的使用

iterator	接口说明
begin + end	返回第一个元素的迭代器 + 返回最后一个元素下一个位置的迭代器
rbegin + rend	返回第一个元素的 reserve_iterator，即 end 位置，返回最后一个元素下一个位置的 reverse_iterator，即 begin 位置

#include<iostream>
#include<vector>
#include<list>
using namespace std;

namespace std
{
	void test_list1()
	{
		vector<int> v = { 1, 2, 3, 4, 5 };
		list<int> lt(v.begin(), v.end());
		
		list<int>::iterator it1 = lt.begin();
		//注意对于string和vector我们可以用小于或不等于做为判断条件,但是list只能用不等于做为判断条件,这时因为不同的容器中空间连续与否的原因
		while(it1 != lt.end())
		{
			cout << *it1 << " ";
			++it1;	
		}
		cout << endl;
		
		list<int>::reverse_iterator it2 = lt.rbegin();
		while(it2 != lt.rend())
		{
			cout << *it2 << " ";
			++it2;	
		}
		cout << endl;
	
		//list里已经不再支持operator[]
		for(auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}
int main()
{
	std::test_list1();
	return 0;	
}

3、list capacity

capacity	接口说明
empty	检测 list 是否为空，是返回 true，否则返回 false
size	返回 list 中有效节点的个数

4、list element access

element access	接口说明
front	返回 list 的第一个节点的中值的引用
back	返回 list 的最后一个节点中值的引用

5、list modifiers

modifiers	接口说明
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 中的有效元素

#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
#include<functional>
#include<time.h>
using namespace std;

namespace std
{
	void test_list1()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
	
		lt.push_front(10);
		lt.push_front(20);
		lt.push_front(30);
		lt.push_front(40);
	
		for(auto e : lt)
		{
			cout << e << " ";	
		}
		cout << endl;
	
		lt.pop_back();
		lt.pop_back();
		lt.pop_back();
		lt.pop_back();
		
		lt.pop_front();
		lt.pop_front();
		lt.pop_front();
		lt.pop_front();
		//lt.pop_front();//err,注意在头删、尾删时要保证list里还有数据,否则这里会报断言错误
		
		for(auto e : lt)
		{
			cout << e << " ";	
		}
	}
	void test_list2()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		
		//list里也没有提供find,所以这里使用algorithm里的
		list<int>::iterator pos = find(lt.begin(), lt.end(), 2);
		if(pos != lt.end())
		{
			lt.insert(pos, 20);
		}
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
		
		//clear并不会把头节点清除,这里还可以继续push_back
		lt.clear();
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		for(auto e : lt)
		{
			cout << e << " ";	
		}
		cout << endl;
	}
	void test_list3()
	{
		list<int> lt1;
		lt1.push_back(1);
		lt1.push_back(2);

		list<int> lt2;
		lt2.push_back(2);
		lt2.push_back(1);
			
		list<int> lt3;
		lt3.push_back(5);
		lt3.push_back(1);
		lt3.push_back(3);
		lt3.push_back(3);

		//对于swap,在C++98中建议使用容器里的,而不建议使用算法里的。它们效果一样,但是效率不一样,具体见如下说明
		lt1.swap(lt2);
		//swap(lt1, lt2);
		for(auto e : lt1)
		{
			cout << e << " ";	
		}
		cout << endl;
		for(auto e : lt2)
		{
			cout << e << " ";	
		}
		cout << endl;
	
		//注意所有的排序都满足,>是降序,<是升序,这里默认是升序
		//这个也是一个类模板,它是一个仿函数,所在头<functional>后面我们会实现,sort所在头<algorithm>
		/*greater<int> g;
		lt3.sort(g);*/
		lt3.sort(greater<int>());//同上,可以直接写成匿名对象
		for(auto e : lt3)
		{
			cout << e << " ";	
		}
		cout << endl;

		//unique的功能是去重,所在头<algorithm>,去重的前提是排序,升序降序都行,如果不排序它只去去相邻的数据
		lt3.unique();
		for(auto e : lt3)
		{
			cout << e << " ";	
		}
		cout << endl;
		
		//erase需要先find,而remove可以直接删除,有就全删,没有就不删,所在头<algorithm>
		lt3.remove(3);
		for (auto e : lt3)
		{
			cout << e << " ";
		}
		cout << endl;
	
		//reverse的功能是逆置,对于带头双向循环链表的逆置比单链表简单的多,所在头<algorithm>
		lt3.reverse();
		for (auto e : lt3)
		{
			cout << e << " ";
		}
		cout << endl;

		//merge的功能是合并
		//splice的功能是转移,它转移的是节点不是数据,很特殊的场景下才会使用到,我们以后在了解LRU可能还会再接触到
	}
	void test_OP()
	{
		srand(time(0));
		const int N = 10000;
		list<int> lt;
		vector<int> v;
		
		v.resize(N);
		for (int i = 0; i < N; i++)
		{
			v[i] = rand();
			lt.push_back(v[i]);
		}

		int begin1 = clock();
		sort(v.begin(), v.end());//vector用算法里的,它底层使用的是快排的三数取中法
		int end1 = clock();

		int begin2 = clock();
		lt.sort();//list用容器里的
		//sort(lt.begin(), lt.end());//err,本质sort会用两个迭代器相减,而list的迭代器不支持减
		int end2 = clock();
			
		cout << "vector sort：" << end1 - begin1 << endl;
		cout << "list sort：" << end2 - begin2 << endl;
	}
}
int main()
{
	std::test_list1();
	std::test_list2();
	std::test_list3();
	std::test_OP();
	return 0;	
}

📝说明

List item

为什么 C++98 建议使用各自容器里的 swap，而不建议使用算法里的 swap ?

如下可以看到算法里 swap 的 C++98 的实现，无论是 string、vector、list 使用它会涉及深拷贝问题，而且这里的深拷贝代价极大，需要深拷贝 3 次 —— 当 lt1 和 lt2 交换，这里会把 lt1 拷贝构造一份 c，然后把 lt2 赋值于 lt1，c 赋值于 lt2，完成交换。

而如果是容器里的 swap，需要交换 lt1 和 lt2，只需要头指针交换即可。假设是 vector，只要把 lt1 和 lt2 对应的 _start、_finish、_endofstorage 交换即可。相比算法里的 C++98 里的 swap，这里可以认为没有任何代价。

所以说，我们为什么在以后工作中多数不会去写数据结构，而还要学《数据结构》这门学科。因为如果你没有自己去实现数据结构，你不了解链表的结构，我跟你说这 2 个 swap 有深拷贝差异，你可能都听不懂，没有学过《数据结构》的人永远不能理解为什么 top-k 问题用了堆好像效率就高很多。所以我们从 C 语言一路走来，各种各样的模拟实现(小的有 strstr、strcmp；大的有二叉树、list)，其实不是为了造更好的轮子，而是能更好的理解并高效的使用。
List item

迭代器补充 ?

容器迭代器的分类：

a) 使用功能的角度可分为，(正向、反向) + const

b) 容器底层结构的角度可分为，单向、双向、随机

? 比如单链表迭代器、哈希表迭代器就是单向，特征是能 ++，不能 --；双向链表迭代器、map 迭代器就是双向，特征是能 ++、–；string、vector、deque 迭代器就是随机迭代器，特征是能 ++、–、+、-，一般随机迭代器底层都是一个连续的空间。

可以看到算法里的 sort、reverse 的声明，它的模板参数的命名不是 T，也不是 iterator，对于模板参数的命名可以任意，但是它的命名是有含意的。比如说你要用 sort 这个算法，你要用的是随机迭代器；你要用 reverse 这个算法，你要用的是双向迭代器。随机迭代器也可以使用 reverse，因为随机迭代器是一个双向迭代器，因为它满足双向迭代器的所有功能；同理，双向迭代器也是单向迭代器、随机迭代器也是单向迭代器。也就意味着这里模板参数的命令是单向迭代器，那么你的容器可以是单向、双向、随机；模板参数的命令是双向迭代器，那么你的容器可以是双向、随机；模板参数的命令是随机迭代器，那么你的容器可以是随机。后面学了继承，就可以知道它们满足一个继承关系。

所以这里要明白一个关系

6、list迭代器失效

前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点无效，即该节点被删除了。因为 list 的底层结构为带头结点的双向循环链表，因此在 list 中进行插入时是不会导致 list 的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

#include<iostream>
#include<algorithm>
#include<list>
using namespace std;

namespace std
{
	void test_list1()
	{
		int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
		list<int> lt(array, array + sizeof(array) / sizeof(array[0]));
		list<int>::iterator pos = find(lt.begin(), lt.end(), 5);
		if(pos != lt.end())
		{
			//不会失效
			lt.insert(pos, 45);
		}
		for(auto e : lt)
		{
			cout << e << " ";	
		}
		cout << endl;
	}
	void test_list2()
	{
		int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
		list<int> lt(array, array + sizeof(array) / sizeof(array[0]));
		list<int>::iterator pos = find(lt.begin(), lt.end(), 5);
		if(pos != lt.end())
		{
			//会失效,可以重新指定迭代器pos
			lt.erase(pos);
			//pos = lt.erase(pos);//ok
		}
		cout << *pos << endl;
		cout << endl;
	}
}
int main()
{
	std::test_list1();
	std::test_list2();
	return 0;	
}

📝说明
在这里插入图片描述

二、list的深度剖析及模拟实现

💨大概瞅下源码的大概框架

template <class T>
struct __list_node {
  typedef void* void_pointer;
  //其实感觉没必要搞成void*,后面还得强转
  void_pointer next;
  void_pointer prev;
  T data;
};
class list {
protected:
	typedef __list_node<T> list_node;
	typedef list_node* link_type;
protected:
	link_type node;
protected:
  	link_type get_node() { return list_node_allocator::allocate(); }
protected:
 	void empty_initialize() { 
 	//体现了带头双向循环链表的特性
    node = get_node();
    node->next = node;
    node->prev = node;
  }
public:
	 list() { empty_initialize(); }
}

💦 模拟实现list

💨 list.h

#pragma once

namespace bit
{
	template<class T>
	struct __list_node//一般前面使用__,表示给内部使用,为什么不使用内部类,因为不仅仅list要用它,迭代器也要用它(C++里还是比较少用内部类的)
	{
		__list_node<T>* _next;
		__list_node<T>* _prev;
		T _data;

		//这里支持无参的new Node,或者有参的new Node(x)
		__list_node(const T& x = T())
			: _next(nullptr)
			, _prev(nullptr)
			, _data(x)
		{}
	};

	//迭代器,用一个类去封装节点的指针,所以目前为止我们已知的迭代器的实现方式有两种:
	//a)原生指针(天然迭代器),它所指向的空间物理结构是连续的,也就是说只有string、vector才可以做天然迭代器(*就是当前位置的数据/++就是下一个位置/--就是下一个位置)
	//b)类(用一个类去封装原生指针,重载相关运算符,让这个类对象用起来像指针),它所指向的空间物理结构是不连续的(没有封装指针之前,*是结构体/++--的位置不明确)
	//这里使用类模板是因为里面需要使用__list_node节点,而它又是一个类模板
	//不适用const
	//template<class T>
	//struct __list_iterator
	//{
	//	typedef __list_iterator<T> self;
	//	typedef __list_node<T> Node;
	//	Node* _node;

	//	//这个类里包含一个节点的指针,然后就可以用一个节点的指针调用它的构造函数就可以构造一个迭代器,这里我们的迭代器begin()/end()是list里的成员函数,它们分别返回第一个有效节点和最后一个节点的下一个无效头节点
	//	__list_iterator(Node* node)
	//		: _node(node)
	//	{}

	//	//*it
	//	T& operator*()
	//	{
	//		return _node->_data;
	//	}

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

	//	//it++,tmp出了作用域销毁,传值返回,不能用引用
	//	self operator++(int)
	//	{
	//		//备份
	//		self tmp(*this);
	//		_node = _node->_next;
	//		return tmp;
	//	}

	//	//--it
	//	self& operator--()
	//	{
	//		_node = _node->_prev;
	//		return *this;
	//	}

	//	//it--
	//	self operator--(int)
	//	{
	//		self tmp(*this);
	//		_node = _node->_prev;
	//		return tmp;
	//	}

	//	//it+,它可以operator+(),但是效率很低,所以也就没有支持

	//	//lt.begin() != lt.end()
	//	bool operator!=(const self& it) const
	//	{
	//		return _node != it._node;
	//	}

	//	//lt.begin() == lt.end()
	//	bool operator==(const self& it) const
	//	{
	//		return _node == it._node;
	//	}

	//	//__list_iterator时有一个节点的指针,要不要去做深拷贝和析构函数呢?
	//	/*并不是说一个类里有节点的指针,就要做深拷贝和析构,要看这个空间是不是你的,你拿了一个指针构造了一个迭代器,这个节点是你迭代器的吗,节点是list的,不需要迭代器去析构,
	//	同时iterator it = begin();，这里需要的就是浅拷贝,begin()构造了一个迭代器对象(_head->_next),你把这个对象赋值给it,难道是要再深拷贝一个节点出来吗,所以说默认生成的浅拷贝也是有价值的
	//	所以我们不需要去写拷贝构造和赋值,因为默认生成的对于内置类型就会完成浅拷贝;不需要去写析构函数,因为节点是list的对象	*/

	//};

	//常规的写法就是实现一个专属的__list_const_iterator类,这两个除了类名称、operator*()不一样,其它完全一样
	//template<class T>
	//struct __list_const_iterator
	//{
	//	typedef __list_const_iterator<T> self;
	//	typedef __list_node<T> Node;
	//	Node* _node;

	//	__list_const_iterator(Node* node)
	//		: _node(node)
	//	{}

	//	//*it
	//	const T& operator*()
	//	{
	//		return _node->_data;
	//	}

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

	//	//it++,tmp出了作用域销毁,传值返回,不能用引用
	//	self operator++(int)
	//	{
	//		//备份
	//		self tmp(*this);
	//		_node = _node->_next;
	//		return tmp;
	//	}

	//	//--it
	//	self& operator--()
	//	{
	//		_node = _node->_prev;
	//		return *this;
	//	}

	//	//it--
	//	self operator--(int)
	//	{
	//		self tmp(*this);
	//		_node = _node->_prev;
	//		return tmp;
	//	}

	//	//it+,它可以operator+(),但是效率很低,所以也就没有支持

	//	//lt.begin() != lt.end()
	//	bool operator!=(const self& it) const
	//	{
	//		return _node != it._node;
	//	}

	//	//lt.begin() == lt.end()
	//	bool operator==(const self& it) const
	//	{
	//		return _node == it._node;
	//	}
	//};
	
	//仰望大佬
	//iterator:<T, T&, T*>
	//const_iterator<T, const T&, const T*>
	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef __list_iterator<T, Ref, Ptr> self;
		typedef __list_node<T> Node;
		Node* _node;

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

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

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

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

		//it++,tmp出了作用域销毁,传值返回,不能用引用
		self operator++(int)
		{
			//备份
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		//--it
		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		//it--
		self operator--(int)
		{
			self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

		//it+,它可以operator+(),但是效率很低,所以也就没有支持

		//lt.begin() != lt.end()
		bool operator!=(const self& it) const
		{
			return _node != it._node;
		}

		//lt.begin() == lt.end()
		bool operator==(const self& it) const
		{
			return _node == it._node;
		}
	};

	template<class T>
	class list
	{
		//这个不想让外面的人用,所以默认是私有的
		typedef __list_node<T> Node;
	public:
		//__list_iterator是什么名字并不重要,最终都会typedef为iterator,因为我们要用统一的方式去访问容器。比如vector<int>::iterator;你那个真正的迭代器是什么名称不重要
		//typedef __list_iterator<T> iterator;
		//typedef __list_const_iterator<T> const_iterator;
		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 iterator(_head);//最后一个节点的下一个位置,哨兵位
		}

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

		list()
		{
			//带头双向循环链表
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}
	
		//lt2(lt1)
		//传统写法
		/*list(const list<T>& lt)
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			
			for(const auto& e : lt)
			{
				push_back(e);	
			}
		}*/
		//现代写法,可以看到这里现代写法相比传统写法并没有讲到便宜,所以说现代写法也不一定是最优,需要灵活运用
		//它要先支持一个迭代器区间的才能写现代写法,同时这里支持其它容器的拷贝构造																																																																																																																																									
		template<class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;

			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		list(const list<T>& lt)
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;

			list<T> tmp(lt.begin(), lt.end());
			std::swap(_head, tmp._head);
		}
		
		//lt1 = lt2
		//传统写法
		/*list<T>& operator=(const list<T>& lt)
		{
			if(this != &lt)
			{
				clear();
				for(const auto& e : lt)
				{
					push_back(e);	
				}	
			}
			return *this;
		}*/
		//现代写法,对于赋值有一个原则,深拷贝现代写法一定非常简单(只要写了拷贝构造,赋值就一定能用现代写法,并且很简洁)
		list<T>& operator=(list<T> lt)
		{
			swap(_head, lt._head);
			return *this;
		}
		
		//对于~list,先实现clear
		~list()
		{
			clear();
			//清除头节点
			delete _head;
			_head = nullptr;
		}

		void clear()
		{
			iterator it = begin();
			while(it != end())
			{
				//不清除头节点,直接复用
				it = erase(it);
			}	
		}

		void push_back(const T& x)
		{
			//同insert(_head, x);,end()是最后节点的下一个位置_head
			insert(end(), x);
		}

		void push_front(const T& x)
		{
			//insert(_head->_next, x);,begin()是头节点的下一个位置
			insert(begin(), x);
		}

		void pop_back()
		{
			//同erase(_head->_prev);
			erase(--end());
		}

		void pop_front()
		{
			//同erase(_head->_next);
			erase(begin());
		}

		iterator insert(iterator pos, const T& x)
		{
			//备份;这里就体现了为啥我们在设计__list_node和__list_iterator时为什么是struct,如果用class,这里就得用友源,但没必要
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(x);

			//关联
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;

			//双向链表的insert是不会失效的,返回新插入的节点,这里同 __list_iterator<T> (newnode),且这里是一个匿名对象。
			return iterator(newnode);
			//同上,newnode是Node*(__list_node<T>)类型,而insert的返回类型是iterator(__list_iterator<T>)也可以,这是因为单参数的构造函数支持隐式类型转换,如 A aa = 1; 或 string s = "hello";。但因为不太明确,所以不太推荐
			//return newnode;
		}
		
		//虽然在外面调用list实例化了lt,但是list里面的函数编译器会按需实例化(外面调用了哪个成员函数,就实例化哪个)
		//erase不是模板?这里要注意类模板里的成员函数都是函数模板,erase的参数iterator就是typedef出来的模板
		iterator erase(iterator pos)
		{
			//空链表(只剩头节点)不能erase
			assert(pos != end());

			//备份
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			//释放
			delete cur;

			//关联
			prev->_next = next;
			next->_prev = prev;

			//返回删除元素之后的位置,注意这里的pos已经是野指针了
			return iterator(next);
		}

		size_t size()
		{
			size_t n = 0;
			iterator it = begin();
			while (it != end())
			{
				++it;
				++n;
			}
			return n;
		}

		bool empty()
		{
			return begin() == end();
		}
	private:
		Node* _head;
	};

	//const迭代器一般出现的场景是在传参的时候
	void print_list(const list<int>& l)
	{
		list<int>::const_iterator it = l.begin();
		while (it != l.end())
		{
			//*it += 2;//err,表达式必须是可修改的左值
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

	void test_list1()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

		print_list(lt);

		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			*it *= 2;
			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}
	
	struct TreeNode
	{
		struct TreeNode* _left;
		struct TreeNode* _right;
		int _val;

		TreeNode(int val = -1)
			: _left(nullptr)
			, _right(nullptr)
			, _val(val)
		{}
	};
	//ostream operator<<(ostream& TreeNode, TreeNode n){}
	
	void test_list2() 
	{
		list<TreeNode> lt;
		lt.push_back(TreeNode(1));
		lt.push_back(TreeNode(2));
		lt.push_back(TreeNode(3));
		lt.push_back(TreeNode(4));

		list<TreeNode>::iterator it = lt.begin();
		while (it != lt.end())
		{
			//*it调operator*,返回_node->_data;,_data是T类型,而这的T是TreeNode,是一个结构体类型的树节点,而*it后是TreeNode,我们说了内置类型可以直接cout输出,但是自定义类型不行,所以我们可以operator<<,或者不用重载(使用结构体的特性)
			//cout << *it << " ";
			//有些场景不适合用cout
			//cout << (*it)._val << " ";
			//这是结构体的访问方式(结构体和指针的访问方式,细节如下说明 3. List item)
			printf("val:%d,left:%p,right:%p\n", (*it)._val, (*it)._left, (*it)._right);
			//像指针一样就要去重载->,[int* p   *p] [TreeNode* p     p->_val]
			printf("val:%d,left:%p,right:%p\n", it->_val, it->_left, it->_right);
			++it;
		}
		cout << endl;
	}
	
	void test_list3()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		print_list(lt);
		
		lt.clear();
		
		lt.push_back(10);
		lt.push_back(20);
		lt.push_back(30);
		lt.push_back(40);
		print_list(lt);
	}
	
	void test_list4()
	{
		list<int> lt1;
		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);
		
		list<int> lt2(lt1);
		print_list(lt2);

		list<int> lt3(lt1.begin(), lt1.end());

		string s("hello");
		list<int> lt4(s.begin(), s.end());		
	
		for (auto e : lt3)
		{
			cout << e << " ";
		}
		cout << endl;
		for (auto e : lt4)
		{
			cout << e << " ";
		}
		cout << endl;	

		lt1 = lt4;
		for (auto e : lt1)
		{
			cout << e << " ";
		}
		cout << endl;	
																																
	}
}

💨 test.cpp

#include<iostream>
#include<stdbool.h>
#include<assert.h>
using namespace std;
#include"list.h"
int main()
{
	bit::test_list1();
	bit::test_list2();
	bit::test_list3();
	bit::test_list4();
	return 0;
}

📝说明

List item

list 迭代器 ?

在 string、vector 里我们实现的都是简单迭代器，用的是原生指针。而对于 list，现在要遍历它，你用原生指针是不能实现的(++操作不会指向下一个节点)，因为每个节点的地址是不连续的，并且毫无关联。

我们瞅下源码，看下是它的迭代器是怎么设计的：可以看到它的迭代器不再是一个 Node*，而用了一个 __list_iterator 的类去封装节点的指针，它有三个模板参数(先不管)。对于 string 是 char*，对于 vector 是 T*，对于 list 是自定义类型，所以我们说迭代器是像指针一样的东西。

这个类的核心成员是 Link_type node，Link_type 是 Node*

本身类(对象)不能 ++，但是我们可以去重载它的 ++，也就是说 __list_iterator 不是指针，但是我们可以让它像指针一样
List item

const 迭代器的实现，对于 const 迭代器的实现，我们一般人是再写一个专属的 __list_const_iterator 类，这两个除了类名称、operator*() 不一样，其它完全一样，非常的冗余。但是好像也没有更好的办法了呀，怎么让 operator*() 一个返回 T&，一个返回 const T& 呢？这里我们瞅下高手写的源码是怎么实现的：

可以看到如下源码的实现，它只实现了一个类，如是是普通迭代器 operator* 的返回值是 T&，如果是 const 迭代器，operator* 的返回值是 const T&
List item

list 的迭代器要像指针一样，除了需要重载 “*”，还需要重载 “->”。
List item

严格来说迭代器是分类型的，在我们的 STL 3.0 中找到 stl_iterator.h 文件，它里面把迭代器类型分为五种，并且它们构成继承关系：

这里涉及 “类型萃取” 的概念，有兴趣可以去了解下，这里就不细谈了。

💦 对模拟的bite::list进行测试

参考 test.cpp 文件

三、list与vector的对比

在 32 位的机器下 vector 和 list 的迭代器所占多少字节 ?

相比 vector 的迭代器，就逻辑上来说 list 的迭代器就要复杂一点，因为 vector 的迭代器是一个天然的迭代器，它是原生指针，但要注意原生指针要做天然迭代器的要求是指针指向的物理空间是连续的。而 list 不能做天然的迭代器，所以我们要将指针封装成一个类，让它完成指针的操作。而就物理层面上来说 vector 和 list 的迭代器没有更复杂，也就是它们所占用的空间是一样的。至此，我们就可以看到 C++ 运算符重载的能力。

所以在 32 位的机器下 vector 的迭代器占 4 个字节；list 的迭代器也占 4 个字节。

vector 与 list 都是 STL 中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景也不同，其主要不同如下：

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