C++——list

作者：几冬雪来

时间：2023年9月24日

内容：C++板块list知识讲解

目录

前言： 

什么是list： 

遍历list： 

insert：

find：

insert与erase：

merge： 

unique： 

remove：

splice： 

list迭代器： 

构造迭代器： 

begin/end： 

operator*： 

operator++： 

operator！=： 

结尾：

---

前言： 

上几篇博客中，我们讲解了C++博客中vector的知识，并且也了解了很多vector的接口，和其接口在头文件的写法，同时也交代了vector和string的相似和不同之处，对其进行了改进与分析，而今天我们来讲解C++中的另外一个模板——list。

什么是list： 

要学习list就需要先了解list。

list在C++中是一个顺序容器，也是一个双向链表。

list里面的许多的接口，在vector和string中也有存在，可以说在list我们已经学习了许多的接口了，但是在list中，它还加入了一些新的接口，这就要等到以后学习的时候慢慢了解了。 

遍历list： 

既然说list中有许多vector和string拥有的接口，那么接下来我们将简单的将list进行一次遍历。

书写到这里的时候，我们要注意一个点。

在C++中list遍历的时候有区别于string和vector，在遍历list的时候，我们并不使用下标方括号的遍历方法，因为它不是连续的空间，最好用的方法是迭代器。 

在这里用遍历就是用迭代器进行遍历，又或者可以使用范围for进行遍历，这是因为范围for的底层就是迭代器。

在遍历list的时候不使用下标方括号的遍历方法，但是并不是代表不能用，只是在遍历的时候下标方括号的方法效率极低，因此系统不做这个选择。 

insert：

insert在string和vector中均有了解和学习到，它代表的意思是在某个位置插入某一个值或者某一串字符串，而且string和vector接口的写法是一样的。（要reserve情况另说） 

类似上边的代码就是string或者vector中insert的写法。

找到这段原代码的起始位置begin，然后加上想插入值的位置就能成功的在这个位置中插入我们想要的值。

但是list和vector根string有根本上的区别，list并不能使用这种方法来进行inset的操作。 

从代码的结果可以看出来如果我们使用vector和string中insert的写法来书写list的代码，程序是会报错的。 

还记得我们上面所说的list在C++中是一个顺序容器，也是一个双向链表。它不像string和vector一样，每个空间都是连续的，可以实现开始位置加查找的位置。

list是一个双向指针，因此它的空间并不是连续的，所以用string会vector那种找位置的代码，并不能找到我们想要插入值的位置。

如果要在第五个位置处加入想要的值，在list中我们就只能依靠一个一个加上去得到后再去insert。

出现这种情况的原因是因为，list的迭代器实现和string等有所区别。 

find：

接下来就来讲解list的find接口，这里有人就要问了，在讲解string和vector的时候也有涉及到了find接口。

在list板块为什么还要再讲一遍？

这是因为list的find接口相较于前两者有些许的不同。 

从代码来看，list的find接口对比string和vector板块，多了一个end的选取。

这就意味着在使用list的find接口的时候，我们可以选择它的区间查找。 

在这里要注意find的一个细节，通常在find选取区间的时候，区间一般都是左闭右开的（类似[begin(),end())）。这是为了在后面如果查找不到的时候返回end使用做铺垫。 

insert与erase：

既然有find就有erase，在讲解string和vector的时候我们又讲过，代码在进行insert扩容的时候，可能会发生迭代器失效的结果。

但是list中insert并不会产生迭代器实失效的结果，反倒是在erase的时候，因此底层是双向指针，因此在erase的时候直接删除数据，这里就肯定会有野指针的出现和迭代器问题的发生。 

merge： 

接下来讲解的是list中出现的新的接口。

首先就是merge接口，它的作用是将两个链表归并到一起去，但是在实际显示中我们书写代码的时候并不经常用merge。 

然后下来看一看merge代码的书写。 

这段代码就是我们两个链表归并的代码。

merge前后的first和second是可以进行交换的。

同时在进行merge归并的时候要注意其中的一个点，那就是两个链表在归并之前必须要先经过sort的操作进行排序后才能执行。 

unique： 

接下来讲解的是list博客的第二个新街口——unique。

unique在C++中所代表的意思是去重，简单来说就是去掉链表中相同的数据。

那么unique的代码又应该怎么样去书写呢？ 

这就是list中的unique接口，它和merge一样，在使用这个接口之前有一个硬性条件，那就是必须要将数据sort排序一次才能正常使用。

不过在写语言的时候我们也极少去使用到这一个接口。

remove：

再下来讲解一下list中的remove接口。

remove看着像是一个全新的接口，但是从底层看它的原理，它其实就是find和erase接口的一个结合体。

也就是说remove接口的作用是找到我们想要删除的值再对其进行删除。 

在这里我们就可以通过remove来删去数据中想删除的值，就如同上面的代码，我们就可以成功的删除4这个值。

这里有人就要问，假如这个地方remove的值不存在，那会发生什么呢？这里可以告诉大家，如果要删除的值不存在，那我们的代码则什么都不会做。 

splice： 

再然后就是list中的splice接口。

splice的意思是粘接，在C++的list中，我们可以使用它将两个链表进行一个链接，但是这种连接方式有区别于merge。

在splice接口中，我们可以选择在原链表的某个位置插入我们的另一个链表而不是单纯的进行尾插链表的操作。

而且splice转移的位置是它的前面。  

这里就是list中splice中会被使用的3种不同形式的代码。

第一种是全部转移，也就是将mylist的链表全部转移到it的前面。第二种是转移某个值，而且第三种则是转移一个区间。 

list迭代器： 

在介绍完了list的作用，list与string和vector的区别，相比较string和vector的接口list又多了哪些接口之后，接下来我们就来讲解list迭代器的实现了。

首先要先写list的迭代器就需要将迭代器的底子铺好。

一开始需要我们将双向链表中的next，prev和val数据标记好，接下来要去对数据进行一个初始化，初始化在这个地方，next和prev指向为空，val这里就给val的值。

再然后因为迭代器需要有一个头结点，因此在私有数据处要有一个头结点。

在这里我们链表的迭代器不能使用内置类型的结点的指针，但是结点的指针还是数据基础。

构造迭代器： 

首先，迭代器是一个自定义类型，这个自定义类型的成员是一个结点的指针。 

在这个地方我们就使用结点的指针构造出来了一个迭代器，因为一个迭代器里面数据存储的函数一个结点的指针。 

begin/end： 

接下来我们就需要来我们就来写一写在链表中begin和end的使用方法。

在这里就先看一下迭代器中begin的代码书写。

这里有人就要问了，这不是迭代器为什么可以返回结点的指针。

这是因为单参数的构造函数支持隐式类型的转换。 

同样的我们的end接口的代码也是这样书写。 

operator*： 

在list的迭代器中，要获取结点中的指针，解引用是必不可少的操作。 

结点默认的解引用是结点，但是在这个地方我们不想要结点，我们需要的是结点中的数据，那么在这个条件下代码有应该怎么去写呢？ 

同时要记得加上&符合，这样就不会导致要return的数据丢失结点还在，val也还存在，做到可读可改。 

operator++： 

再接下来讲解的是list中的operator++，为什么要讲解operator++呢，这是因为对比string和vector的++不同。

因为链表不是连续的空间，因此就需要我们的++接口来处理这种情况。

 

因为在这里我们是迭代器进行++操作，因此它的返回还是迭代器。

然后_node->_next则是指向原结点的下一个位置的值。 

operator！=： 

再然后就是operator！=，这个也是会被使用到了，在判断停止条件的时候就会使用到operator！=来进行我们的条件。

接下来就来看看operator！=代码是如何书写的。

像这里就是判断结点是否相等，因为是判断结点是否相等。因此这里更合适使用bool来作为返回的判断。

同时只是判断两个结点是否相同，因此要对其加入const防止被修改。 

结尾：

到这里我们的list的知识就有了一个初步的了解了，在list迭代器的后面我们将会list中的const迭代器，list的const迭代器相较于我们之前的迭代器，难度有了一个质的提升，希望这篇粗略的博客能帮到各位吧。