C++笔记-list

list即是我们之前学的链表，这篇主要还是讲解list的底层实现，前面会讲一些list区别于前面string和vector的一些接口以及它们的注意事项。

一.list的基本使用

和之前的string，vector一样，有很多之前见过的一些接口，经过前面两篇的讲解，很多接口不用讲解相信大家都会使用，主要就是Operations中的一些接口之前没有讲过，前面主要就是讲解这些接口。

这里主要讲splice，remove，unique和sort：

1.1splice：
splice的作用是将一个列表中的内容拷贝给另一个链表。

可以看出splice有三种传参的方式，每种方式都会产生不一样的结果：
1.1.1第一种传参

第一种传参中的两个参数：第一个参数就是从目标位置开始拷贝数据过去，第二个参数代表某个链表。

第一种传参方式就是把第二个参数中链表的所有数据都拷贝到第一个参数之前，结果如第二张图所示，lt1的所有数据都被拷贝到lt2的begin位置之前。

1.1.2第二种传参

第二种传参比第一种多了一个参数，意思就是把具体某个位置的值拷贝到目标位置之前，就比如上图所示的将lt1中的第一个数据拷贝过去。

1.1.3第三种传参方式

第三种传参就是把某个范围的数据拷贝过去，就比如上图中将lt1中的4到6拷贝过去。

这里可能会有人疑惑：为什么第三个参数直接写lt1.begin()+3呢？这样写不是更简洁吗？

这个问题我下面讲sort时会讲，这里先跳过。

splice还有一种玩法就是可以将自己的数据拷贝到某个位置之前，就比如将最后一个数据拷贝到第一个位置：

这样就将6放到了第一个位置，这种用法是要比前面的用法更为普遍的。

1.2remove

list中remove作用是将链表中所有和你要删除的值相同的数据一并删除。

如上图所示，这里就把所有的2都给删除了，remove的基本用法就是如此。

1.3unique

unique的作用就是删除一个有序链表中重复的数据。

通过unique就可以把重复的数据给删掉。

注意：一定要是有序的，如果不是有序的就无法做到删除重复的数据。

此时链表数据不是有序的，unique就没有发挥作用。

1.4sort

sort的作用相信就不用多说大家都知道，但是在这里我们要思考两个问题：

1.string和vector都没有实现sort接口，为什么list要单独实现？

2.list实现的sort效率怎么样？

先来解释第一个问题：
这个问题的答案也能解释上面splice出现的疑点，这就涉及到迭代器的分类。

迭代器分为三类(移动迭代方式)：

1.单向迭代器，如：forword_list/unordered_map...   ++

2.双向迭代器，如：list/map...   ++/--

3.随机迭代器，如：string/vector/deque.. ++/--/+/-

后面就是它们能够进行的移动迭代方式，而语法库中的sort参数是随机迭代器，list都是双向迭代器，所以不能使用语法库中的sort，而上面的splice出现的疑点也是因为双向迭代器不能+/-，所以不能那样使用。

中间蓝色的单词的意思就是双向迭代器。

这是string和vector的随机迭代器。

这是语法库中的sort的参数要求，上去就要求随机迭代器，所以list才需要自己实现。

而迭代器的分类和之前讲的权限放大和缩小的概念有些类似，就是如果函数参数要求是双向迭代器，此时我们传随机迭代器也是可以的，相当于权限的缩小，同理单向迭代器也是如此。

双向迭代器和随机迭代器就是特殊的单向迭代器。

再来说第二个问题：
我就直接说结论，list自己实现的sort效率不高，比起语法库中的sort效率低了很多。

不过在数量较少时，效率差不多，但是在数量较大时效率就会低很多，举个例子：

在数量较大时，把list中的数据拷贝到vector，调用语法库中的sort，再把数据传回list的效率都比直接调用list本身的sort高。

二.list的底层实现

2.1list框架的实现

链表我们之前在数据结构阶段都了解过，链表要把整个链表和单个结点区分开，所以这里也是同理。

这里定义哨兵位，相信大家都知道底层list其实就是双向带头循环链表。

可能有人会疑惑：为什么单个结点要用struct而不用class？

其实我们在实际应用中，想让别人使用的用class，不想别人访问的用struct，我们只想让别人用链表整体，而不能直接访问我一个结点中的变量。

在单个结点类中运用初始化列表进行初始化，这样在list类中初始化哨兵位时就不需要传数据，直接创捷一个哨兵位，并让prev和next都指向自己即可，和之前讲链表是一样的。

2.2push_back尾插

思路和之前讲链表是一样的，创建一个节点，并更新哨兵位，原尾节点和新建结点的next和prev即可。

2.3iterator迭代器的实现

之前在string中讲过迭代器并不就一定是指针，在list中印证了。

为什么在list中要单独实现iterator迭代器呢？

因为在之前的string和vector中，它们两个底层都是数组，它们的原生指针就能完成解引用和++等操作，而链表我们知道解引用是访问一个结点，而一个结点不止有数据，还有prev和next，而迭代器我们要求解引用就是直接拿出其中的数据。

包括++等操作，链表底层并不是数组，每个结点的地址并不是连续的，所以通过++等操作是不能找到相邻的结点的。

基于以上两点，所以在list终究要我们自己实现iterator迭代器，而自定义类型的迭代器其实执行的还是指针的作用，所以成员变量依旧还是单个结点的地址。

其中里面所实现的各种比较我就不过多赘述了，之前都讲过，这里主要讲解一下为什么多加了一个类型Ref。

因为不仅有iterator，还有const_iterator，两者的区别无非就是解引用的值能不能修改的问题，但是如果我们没有多加Ref这个类型，那我们是不是还要写一个函数重载？

但是从之前学过的函数重载中我们知道，是不能以返回值不同而进行函数重载的，程序会报错，

那要解决这个问题就只能在单独写一个const_iterator类，内容和iterator一样，除了解引用符号的重载这一个不同而已。

这样写代码就太冗余了，有很多重复代码，但是我们加一个类型Ref就可以解决这个问题，根据传过去的参数不同将其分为iterator和const_iterator：

可能有人会疑惑：iterator类不需要实现析构函数吗？

我们所实现的iterator只是用于解引用和遍历链表而已，不能使用后直接把这个节点给销毁了，所以不能实现析构函数，相应的也不需要实现拷贝构造函数。

上面的结点类也是一样，析构操作只需要在list类中实现即可。

另外其中的!=，==等符号的重载是因为现在iterator是自定义类型，不再是原生指针，所以如果要比较自定义类型，就要重载相应的符号。

2.3begin和end

实现了迭代器iterator，接下来就要实现begin和end，也是分为普通和const版本，注意返回值是需要调用iterator类并进行传参的，头结点是哨兵位的下个结点，end返回就是哨兵位。

2.4insert

insert实现逻辑和之前一样，找到目标结点的prev和next，并更新三个结点的next和prev即可。

2.5erase

 

相信现在看到这个返回值大家就知道erase会出现什么问题了，没错，还是迭代器失效的问题，所以还是要在erase后更新指针。

需要注意的地方有两个：

1.目标结点不能是哨兵位

2.删除当前结点后，要更新指针的位置，指向下个结点

2.6push_front，pop_back和pop_front

这三个包括之前实现的push_back就都可以通过复用insert和erase来实现，要注意的就是尾删不能直接传end，要让end--才是尾结点的位置。

2.7clear

clear的作用就是销毁除哨兵位之外的所有结点，实现起来也较为容易，遍历整个链表挨个销毁即可。

2.7拷贝构造函数

实现拷贝构造函数也是为了深拷贝做准备，一样也要创建哨兵位，不过这和构造函数的代码一样，所以其实可以将这段代码封装成一个函数也可以，这里因为就几行代码所以我就没整。

下面就是遍历目标链表，把相应的节点push_back进去即可。

2.8=符号重载

以及是需要用到std标准库中的swap函数进行操作，最后=符号重载复用即可。

我们再看最后一种情况：

当传进去的参数类型是自定义类型时，我们要访问其中的数据要用到->符号，但是vector是可以直接用的，因为它用的是原生指针，而list不能使用，因为是自定义类型迭代器，所以在这里我们要自己实现->符号。

和上面的解引用重载一样，这里我们引进一种类型Ptr，代表要输出的数据的地址，所以也分为普通和const版本，作用也就和vector原生指针作用是一样的。

此时就不再会报错，但是可能有人会觉得很奇怪：不应该是两个箭头吗？

第一个箭头返回的是指针，应该还有一个箭头才能指向数据啊。

这个想法没错，出现这现象的原因是为了可读性高，编译器把另一个箭头给省略了。

以上就是list的内容。