一、list简介

list的使用与我们之前学习过的vector的使用相似，只是说它们的底层不同，一个是双向带头循环链表，一个是顺序表，但是使用类似，所以推荐大家也可以看看vector的使用，链接如下：

我们常说的list其实是一个双向带头循环链表的类模板，它属于STL库，并且它的接口和vector一样看起来更加规范，所以如果学懂了vector，学习list就简单多了，只是学习底层时稍有不同，接下来我们就开始正式学习吧！

二、list的默认成员函数

默认构造

list的默认构造和vector的默认构造差不多，默认为空，也就是一个只有头节点的双向带头循环链表，没有存储数据，如下：

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

int main()
{
	vector<int> lt;
	//查看list对象lt的容量，和vector接口类似
	cout << lt.capacity() << endl;
	//查看有效数据个数
	cout << lt.size() << endl;
	return 0;
}

我们来看看代码运行结果：

可以看到确实按照我们所料，list的默认构造不会插入任何数据，但是其实list的底层已经申请了头结点，到时候我们讲到底层才知道

普通构造

list的普通构造和vector一样也只掌握两个，分别是n个val的构造，以及支持initializer_list的构造，我们大概了解了initializer_list这个数据结构，所以在这里我们学起来就简单多了，如下：

接下来我们简单用一用就好了，因为这个接口类似于我们之前讲的string类的n个字符c的构造，有了string类的基础我们讲vector的使用就轻松很多，如下：

int main()
{
	//默认给lt1插入3个4
	list<int> lt1(3, 4);
	//给lt2插入后面大括号中的元素
	//后面的大括号会被自动识别成initializer_list
	list<int> lt2 = { 1, 2, 3, 4 };

	return 0;
}

我们来看看代码调试结果：

拷贝构造和赋值重载

list的拷贝构造和赋值重载也是采用的是深拷贝，如果不知道深拷贝的同学可以看这篇文章，里面详细讲到了深浅拷贝：【C++】揭秘类与对象的内在机制（核心卷之深浅拷贝与拷贝构造函数的奥秘）
这里我们也就不再演示使用了，因为比较简单，到时候我们在底层部分再来细讲它们

析构

list的析构稍微比vector的析构复杂一点，它需要先把除头结点外的其它节点都释放掉，最后释放掉头节点即可，我们在底层实现部分再讲具体细节

三、元素访问接口

从这里开始其实list和vector的使用是差不多的，这也正是STL模板库的目的，学习一个容器后学习另一个容器就会非常简单了，因为它们的接口使用都具有相似性，可以自行尝试一下通过查阅文档学习list的使用
但是为了完整性，我们还是从头来学学list的使用，首先我们来看看list的元素访问接口有哪些：

很明显list的元素访问接口比vector少一些，因为vector的底层是数组，支持使用下标访问数据，也就是支持随机访问，而list则不行，所以它只提供了获取头尾元素的方法， 如果要查找某个值，则需要使用find进行查找，接下来我们演示一下front和back的使用，如下：

int main()
{
	list<int> lt = { 1, 2, 3, 4 };
	cout << lt.front() << endl;
	cout << lt.back() << endl;
	return 0;
}

四、容量相关接口

我们来看看list容量相关的接口：

可以看到list相应的容量接口也变少了，resize也被移到了modify接口里面去了，由于底层是双链表，所以只有size而没有capacity，接下来我们简单使用一下这两个接口，不必多说，如下：

int main()
{
	list<int> lt = { 1, 2, 3, 4 };
	cout << lt.empty() << endl;
	cout << lt.size() << endl;
	return 0;
}

五、list的迭代器

list和vector迭代器的使用方法相同，因为我们之前就讲过，迭代器的出现就是为了给每个容器一个统一的遍历和访问的方式，所以自然每个容器的迭代器的使用方法相同了，如下：

int main()
{
	list<int> lt = { 1, 2, 3, 4 };
	list<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	return 0;
}

当然，list迭代器的实现方式就和vector大相径庭了，是一种对我们来说比较新鲜的方式，我们在后面的实现部分为大家揭晓谜题，接下来我们再试试范围for，如下：

int main()
{
	list<int> lt = { 1, 2, 3, 4 };
	for (auto& e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

代码运行结果如下：

可以看到list迭代器和范围for的使用和vector几乎没有差别

六、list的修改接口

list的修改接口非常简单，大部分和vector的差不多，如下：

push_back与pop_back

在list中也没有string中append之类的接口来干扰我们，我们还是简单使用一下push_back以及pop_back，分别是尾插和尾删，如下：

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

	lt.pop_back();
	lt.pop_back();
	return 0;
}

push_front和pop_front

push_front和pop_front是vector中没有的修改接口，因为vector底层是数组，不方便在头部删除和插入数据，时间复杂度都是O(N)级别的，所以没有单独实现头插和头删的接口
而list不一样，它是双向带头循环链表，无论是头插还是头删都是O(1)的时间复杂度，只需要更改链表指针的指向，我们在底层实现的时候细讲，接下来我们来使用这两个接口，如下：

int main()
{
	list<int> lt;
	lt.push_front(1);
	lt.push_front(2);
	lt.push_front(3);
	lt.push_front(4);

	lt.pop_front();
	lt.pop_front();
	return 0;
}

insert

接下来我们来看看insert，它的接口如图：

可以看到list的插入和vector的insert基本都差不多，因为list和vector一样，都是指定一个迭代器的位置，将元素插入到这个迭代器的位置上，我们来演示一下，如下：

int main()
{
	list<int> lt = { 1, 2, 3, 4 };
	list<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		if (*it == 2)
			lt.insert(it, -1);
		it++;
	}
	for (auto e : lt)
		cout << e << " ";
	return 0;
}

我们的预期是在元素2的位置上插入一个元素-1，我们来看看代码运行结果，看看是否如我们所料，如图：

我们可以发现，代码成功运行了，如果看过之前我写过的vector的使用，那么就会发现这里的情况和vector不同，vector进行插入后不接收insert更新后的迭代器就会直接报错，而list不会
这是因为它们的底层数据结构不同，vector的插入可能导致扩容，整个数组都被更新了，导致迭代器失效，而list则不会，因为它的底层是双链表，链表的插入就是申请一个新节点，然后用指针链接起来就好了，不会造成迭代器失效
所以list的插入不会造成迭代器失效，但是list还是可能迭代器失效的，因为删除一个节点会释放这段空间，如果我们再去访问这个迭代器，就会造成越界行为，这就是list的迭代器失效，我们在讲解erase之后再说一遍

erase和迭代器失效

我们来看看erase的接口：

这两个接口分别是删除一个迭代器位置上的元素以及删除一段迭代器区间，我们就以第一个接口为例讲解，我们还是简单写一下，如下代码

int main()
{
	list<int> lt = { 1, 2, 3,4 };
	auto it = lt.begin();
	while (it != lt.end())
	{
		if (*it == 2)
		{
			lt.erase(it);
		}
		it++;
	}
	for (auto e : lt)
		cout << e << " ";
	return 0;
}

我们来看看代码是否会出错，如下：

可以看到代码确实有问题，就是迭代器失效的问题，但是这时候我们就需要分析一下了，为什么会造成迭代器失效呢？因为节点被释放之后，我们不能再访问，也不能对迭代器进行++和解引用，所以我们删除一个节点就会导致迭代器失效
再加上VS的判断很严格，即使我们删除节点后并不对这个迭代器作修改，VS也会报错，所以结论就是只要list用erase删除了节点，就一定要接收返回值，否则会报错，接下来我们接收返回值使用一下，如下：

int main()
{
	list<int> lt = { 1, 2, 3,4 };
	auto it = lt.begin();
	while (it != lt.end())
	{
		if (*it == 2)
		{
			//lt.erase(it);
			it = lt.erase(it);
		}
		it++;
	}
	for (auto e : lt)
		cout << e << " ";
	return 0;
}

代码运行结果如图：

可以看到确实是迭代器失效的问题，我们接收返回的迭代器继续使用就没有问题，在底层部分我们也会反复强调

clear

最后一我们来认识最后两个比较简单的接口，其中一个就是clear，clear就是清空数据，其实就是直接把整个链表的有效数据节点都删除了，只剩下头结点了，在下一篇的底层部分会比较好懂，接下来我们简单使用一下，如下：

int main()
{
	list<int> lt = { 1, 2, 3,4 };
	lt.clear();
	cout << lt.size() << endl;
	return 0;
}

resize

list的resize和vector以及string的resize都是差不多的，如果小于当前的有效数据个数就是删除，如果多于有效数据个数就是尾插数据到目标大小，我们分别测试一下，首先是小于当前有效数据个数，如下：

int main()
{
	list<int> lt = { 1, 2, 3, 4 };
	lt.resize(2);
	for (auto& e : lt)
		cout << e << " ";
	return 0;
}

代码运行结果如下：

接下来是大于有效数据个数，如下：

int main()
{
	list<int> lt = { 1, 2, 3, 4 };
	lt.resize(6, -1);
	for (auto& e : lt)
		cout << e << " ";
	return 0;
}

代码运行结果如下：

那么关于list的使用我们今天就讲到这里，如果大家有什么疑问欢迎私信我，下一篇文章我们就开始将list的实现了，敬请期待吧！
bye~