《STL--list的使用及其底层实现》

引言：

上次我们学习了容器vector的使用及其底层实现，今天我们再来学习一个容器list，
这里的list可以参考我们之前实现的单链表，但是这里的list是双向循环带头链表，下面我们就开始list的学习了。

一：list的介绍

list的介绍文档：

二：list的使用

1. 约定：

关于list的接口众多，下面我们只介绍一些比较常用的接口，其他接口同学们可以自行去list的介绍文档中学习。

2. list的构造：

1. list (size_type n, const value_type& val =value_type()):构造的list中包含n个值为val的元素。
2. list():构造空的list。
3. list (const list& x):拷贝构造函数。
4. list (InputIterator first, InputIterator last):用[first, last)区间中的元素构造
   list。

代码演示：

3.list iterator的使用

注：这里大家先将list的迭代器理解为指向节点的一个指针。

1. begin:返回第一个元素的迭代器。
2. end:返回最后一个元素下一个位置的迭代器。
3. rbegin:返回第一个元素的reverse_iterator,即end位置。
4. rend:返回最后一个元素下一个位置的reverse_iterator,即begin位置。

代码演示：

注：

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

4.list capacity的使用

1. empty:检测list是否为空，为空返回true，反之则返回false。
2. size:计算list中有效数据的个数。

代码演示：

5. list element access

1. front:返回list的第一个节点中值的引用。
2. back:返回list的最后一个节点中值的引用。

代码演示：

6. list modifiers

1. push_front:在list首元素前插入值为val的元素。
2. pop_front:删除list中第一个元素。
3. push_back:在list尾部插入值为val的元素。
4. pop_back:删除list中最后一个元素。
5. insert:在list position 位置中插入值为val的元素。
6. erase:删除list position位置的元素。
7. swap:交换两个list中的元素。
8. clear:清空list中的有效元素。

代码演示：

（1）push_back(front) pop_back(front)

（2）erase 和insert

swap和clear

7. list迭代器失效问题

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

这里想要解决迭代器失效的话，处理方式和之前是一样的，需要对其重新进行赋值：

三：list的模拟实现

1. 思考：

这里在模拟实现list时就和vector的实现有所区别了，之前实现的vector的本质上一个数组，其迭代器和原生指针没什么区别，对其迭代器解引用就可以拿到对应的数据，但是这里的list里面存储的是一个个节点，因此这里的迭代器并不是单纯的原生指针，你对节点指针解引用的话拿到的是一个节点，并不能直接拿到节点里的数据，但是这不是我们期望的，按照我们的逻辑是解引用节点指针是要拿到这个节点指针对应节点里面的数据，因此这里在模拟实现的时候就比之前要复杂一点，牵扯到迭代器的构造以及有关迭代器的一些重载。

2.基本框架：

（1）节点结构：

（2）迭代器结构：

（3）链表结构：

3. 迭代器结构完善

(1)* 重载：

(2) 前置++和后置++重载：

(3) 前置- - 和后置 - - 重载：

(4) 比较运算符重载：

4. 构造函数

注：这里在构造的过程中由于会对e进行解引用，因此这里要用引用。

5. begin 和 end

6. insert 函数

注：由于这里除了数据的申请，其他的逻辑和之前实现的双向链表没啥区别，就不细讲了。

7. push_back 函数

注：这里就直接复用insert即可。

8. push_front 函数

9. erase 函数

注：

1. 这里需要注意头结点我们是不能动的。（大哥动不得）
2. 为解决erase引起的迭代器失效问题，这里我们的erase给了返回值。

10. pop_back 函数

注：这里就是直接复用erase即可。

11. pop_front 函数

12. clear 函数

13. 析构函数

14. size 函数

注：为了避免重复遍历链表来计算个数，因此这里我们就来维护一个成员变量_size，因此之前的插入和删除都需要维护_size

15. swap 函数

四： 拷贝构造函数引起的问题及解决方案

1. 问题的引发

我们这里在实现拷贝构造函数的时候出现了以下问题：

那么为什么会出现这个问题呢？

2. 思考：

因为拷贝构造函数这里给的参数是const类类型，但是这里在构造的过程中用到了范围for，我们知道，范围for本质上就是迭代器的替换，并且因为需要进行解引用，所以这里的范围for我们用的是引用，但是由于传入参数是const类型，这里需要const类型的迭代器来支持，所以这里才会出现问题，因此我们就需要实现const类型的迭代器。

3. 解决方案：

这里由于const迭代器和普通类型的迭代器就一点不同，如果再封装一个类的话就太冗余了，因此这里就可以从模版下手：



这个时候就解决了上面出现的问题，而且这样使得我们在使用不同的迭代器时编译器能够自动推导类型。

4. 赋值运算符重载：

五：补充内容— -> 重载

1. 引入：

首先我们来看vector存储自定义类型时的访问：

下面再来看用list来存储自定义类型时的访问：

可以看到用list来存储自定义类型的时候就不能用->来访问，这是为什么呢？
还是回到前面提到的迭代器的区别，vector的迭代器就可以理解为原生指针，用->就可以拿到其里面的数据，而list这里的迭代器->的话拿到的是节点，而不是数据，因此，这里这样写就有问题，那么我们看一下标准库里面的list的-> ：

可以看到标准库里面的list就可以通过->来访问数据，这是因为标准库里的list对->进行了特殊处理，因此我们这里也需要对->进行重载才可以。

2. -> 重载：

注：这里->的重载看着就有点奇怪了，注意这里返回的是指向数据的指针（数据的地址）


注意这里的两种写法都可以，第一种方式只是编译器对其进行了特殊处理，其实第二种写法更符合我们理解的逻辑。

完结！！！