「前言」文章的大致内容是 list 的介绍及使用。

一、list的介绍

有数据结构作为基础，STL 上手很快，学习成本也低，本文也是讲解 list 常用重点接口，其它有需要再查询文档，重点也是放在 list 的模拟实现上面

list 文档介绍

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

class Alloc = allocator 是空间配置器（内存池），暂时不用理会，它也给了缺省值，目前不用我们自己传，使用默认缺省值就可以了

使用 list 要包含 list 的头文件：

#include <list>

list 要重点使用迭代器了，因为 list 不能支持随机访问了，即不能使用 “[]” + 下标 进行访问

二、list的使用

 list 也是掌握一些常用的接口，其它有需要在查询文档

先说一下成员变量

value_type 就是第一个模板参数 （T）；size_type 与 size_t 的用法一致，无符号

2.1 Construct

 接口简单说明：

构造某个类型的 list 

list<int> l1;//构造int类型的list
list<double> l2;//构造double类型的list

测试代码

void Test_list()
{
	list<int> l1;                         // 构造空的l1
	list<int> l2(10, 3);                 // l2中放10个值为3的元素
	list<int> l3(l2.begin(), l2.end());  // 用l2的[begin(), end()）左闭右开的区间构造l3
	list<int> l4(l3);                    // 用l3拷贝构造l4
	 //以数组为迭代器区间构造l5
	int array[] = { 1,2,3,4 };
	list<int> l5(array, array + sizeof(array) / sizeof(int));
}

2.2 operator=

测试代码

void Test_list()
{
	list<int> l1(10, 3);// l1中构造10个值为3的元素
	list<int> l2;
	l2 = l1;//赋值重载
}

析构函数不解释了，程序结束自动调用 

2.3 Iterators

list 的迭代器不再是简单的原生指针了，指针要经过封装和重载才能支持 list 的迭代器的使用，范围 for 的底层就是迭代器。此处可暂时将迭代器理解成一个指针，该指针指向list中的某个节点，到 list 模拟实现再细讲

常用接口

示意图

注意：遍历 list 只能用迭代器和范围for 

 测试代码

void Test_list()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	list<int>::iterator it = l.begin();

    //迭代器判断结束只能使用 !=
	while (it != l.end())
	{
		cout << *it;
		++it;
	}
	cout << endl;

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

运行结果

注意：迭代器判断结束条件只能使用  != ，因为 list 的每个节点的空间的大小是不确定的，不能使用 it < l.end()；之前 vector 和 string 的迭代器结束可以使用 < 判断迭代器结束，因为它们的空间是连续的

反向迭代器使用

void Test_list()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	list<int>::reverse_iterator it = l.rbegin();

	//迭代器判断结束只能使用 !=
	while (it != l.rend())
	{
		cout << *it;
		++it;
	}
	cout << endl;

}

注意

  1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
  2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动 

 运行结果

2.4 Capacity

 常用接口

不演示，直接使用即可

2.5 Element access

常用接口

测试代码

void Test_list()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	cout << l.front() << endl; //1
	cout << l.back() << endl; //0
}

 运行结果

1
0

2.6 Modifiers

常用接口

测试代码

void Test_list()
{
	list<int> l;
	l.push_back(1);//尾插数据
	l.push_back(2);
	l.push_back(3);
	l.push_back(4);
	for (auto e : l)
		cout << e;
	cout << endl;

	l.pop_back();//删除 4
	for (auto e : l)
		cout << e;
	cout << endl;

	l.push_front(0);//头插0
	for (auto e : l)
		cout << e;
	cout << endl;

	l.pop_front();//头删
	for (auto e : l)
		cout << e;
	cout << endl;
}

 运行结果

erase

测试代码

void Test_list()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));

	list<int>::iterator pos = find(l.begin(), l.end(), 2);
	l.erase(pos); //删除2
	for (auto e : l)
		cout << e;
	cout << endl;
}

运行结果

134567890

insert

测试代码

void Test_list()
{
	int array[] = { 1, 2, 4, 5, 6, 7, 8, 9 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));

	list<int>::iterator pos = find(l.begin(), l.end(), 4);
	l.insert(pos, 3); //在4的位置的前一个插入3
	for (auto e : l)
		cout << e;
	cout << endl;
}

 运行结果

123456789

 list 的迭代器失效问题

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

所以 insert 并不会造成迭代器失效，而 erase 之后则会造成 pos 迭代器失效，因为 pos 迭代器指向的空间已经被释放了

测试代码

void Test_list()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值
		l.erase(it);
		++it;
	}
}

 运行结果

修改代码

void Test_list()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		l.erase(it++); // it = l.erase(it);
	}
}

 修改之后，程序就可以正常运行了

2.7 Operations

 这些接口不怎么使用，就不介绍了，有需要再查询文档，其中的 sort 排序数据量大的时候，效率低，也不怎么使用

--------------- END ---------------

「 作者 」 枫叶先生
「 更新 」 2023.2.3
「 声明 」 余之才疏学浅，故所撰文疏漏难免，
          或有谬误或不准确之处，敬请读者批评指正。