list的底层：

我们之前讲解了list，今天我们来看一下list的底层：

list底层是一个双向带头循环的链表，之前我们学习数据结构的时候，我们就学过。

迭代器的封装：

我们看这个图片，我们的链表的指针可以达到链表的迭代器能力吗？

达不到的，只有在数组里面，连续地数据的时候，指针才可以是看作迭代器。

迭代的两个核心的能力就是：++和*。

在链表里面，数据是不连续的，对于迭代器的++，是实现不了的，得不到下一个数据的位置。*解引用的话，得到的也是这个节点，得不到里面的数据，这就和数组里面的迭代器是不一样的。

在数组里面，数据是连续的，我们的迭代器++就可以到下一数据的个位置。*解引用就可以直接得到这个数据的。

但是：

我们在list里面我们是可以使用迭代器完成++和*的操作的，那么底层是怎么实现我们的迭代器的呢？

我们看一下我们的库里面是怎么干的。

我们的底层使用一个自定义的类来把我们的指针封装起来；

我们使用封装来实现我们的迭代器的功能：

对于我们的迭代器的++和解引用*，我们可以直接使用函数重载来实现，我们直接实现在类里面。

这个类就是我们的迭代器，我们给类的名字就叫做list_iterator；

insert的底层：

我们看这个insert的底层：

我们看insert，我们的插入是把数据插入到，迭代器position位置的前面。

我们看这个代码，我们是申请到介蒂安以后，我们的tmp的next指向position.node;

在这里可能会有疑惑，为什么是.，这个不应该是类，结构体调用里面的成员才使用的吗？

是的：

我们在封装我们的指针的时候，我们把我们的node结点也给封装进去了，因为我们的后面要实现函数的重载，我们要调用node。

我们说我们的string和vector的迭代器使用的就是我们的原生指针，list使用的迭代器就是把我们的指针进行封装，在内部实现函数重载，但是string和vector也不一定是要使用原生指针，也可以封装他们的指针来进行。

list的底层的实现：

迭代器的实现：

我们把我们的结点的指针封装到我们的类里面，这个类就是我们的list的迭代器。

然后我们在这个类里面，我们实现迭代器的++，*解引用等一些列的操作。

迭代器失效：

我们之前讲解vector的时候，我们的insert函数和erase函数都发生了迭代器失效的问题，我们的插入函数失效的原因是我们的数组进行了扩容，但是我们的pos位置没有进行更新，发生了迭代器失效，我们的erase函数失效的原因是我们的vs会对他进行强制的判断，删除数据以后这个迭代器就失效了。

这个是我们的list底层实现的insert函数，我们的list没有扩容的问题，这里的insert是没有迭代器失效的问题的。

这个是我们的list的删除函数erase，这个函数和我们的vector一样，都是会发生迭代器失效的问题的，我们的erase函数，在把pos位置的数据删除以后，迭代器pos指向的结点就被销毁了，这时候pos就失效了，所以我们的这个函数还是要返回下一个数据的迭代器来及时的更新我们的迭代器，来避免迭代器的失效。

这样我们就可以向vector那样，删除数据以后，更新我们的迭代器；

（几乎所有的容器的erase都会失效，至于insert会不会失效，这个就要看情况）；

const修饰迭代器：

我们看这个代码，我们在实现拷贝构造的时候，我们的参数传的是const修饰的参数类型，这时候我们进到函数里面的话，我们使用范围for就会报错，因为范围for的底层是我们的迭代器，我们的迭代器是普通的类型。

但是我们的链表被const修饰，我们使用迭代器对他进行遍历的话，我们就需要const类型的迭代器来。

我们看下面的图片：

我们的这个图片我们看我们的上面的两种被const修饰的指针，我们的const放在*前面的时候，我们的指针指向的数据不能被修改，但是我们的指针的指向可以修改。

当我们的const在*的右边的时候，这时候表示我们的指针指向的数据可以被修改，但是我们的指针的指向不能被修改。

我们的const迭代器其实就是和我们的上面的第一种是一样的，我们的迭代器指向的数据不能被修改，但是我们的迭代器的指向可以被修改；

所以，对于这种情况，我们就创建两种迭代器来进行应对：一种普通的迭代器，再来一种const修饰的迭代器；

我们把const迭代器封装成一个新的类，我们的const修饰的迭代器和普通的迭代器是两个不同的类；

这个是我们的const修饰的迭代器；

这个是我们的普通的迭代器；

这两个类的本质的却别其实就是解引用*的实现，const修饰的迭代器我们的返回值加上const，不能让他修改数据；

迭代器的合并：

我们实现我们的迭代器的封装，我们封装了两个类，分别是我们的普通的迭代器iterator的封装和const修饰的const_iterator的封装，但是其实这两个类的话，我们看了我们上面的const修饰的迭代器，其实主要的区别就是解引用函数的返回值是否是被const修饰的。

我们就可以再加一个模板参数，把我们的解引用函数的返回值换成我们的模板参数，然后我们调用我们的迭代器的时候，我们需要什么类型的迭代器，我们直接传参就可以了。

补充：

我们看这个图片，我们看我们对我们的vector进行初始化的状态。

v1.push_back({ 1,1 }); 等尾插操作涉及隐式类型转换。

AA 结构体定义了带有默认参数的构造函数 AA(int a1 = 1, int a2 = 1) 。当执行 v1.push_back({ 1,1 }); 时，花括号初始化列表 {1, 1} 没有直接对应的 AA 类型对象。此时，编译器会利用 AA 的这个构造函数，将 {1, 1} 隐式转换为 AA 类型临时对象，再调用 push_back 插入到 vector<AA> 容器 v1 中。这符合隐式类型转换的特征，即编译器自动利用构造函数进行类型转换。

我们来看这个函数，我们上面使用vector容器，我们看vector里面使用了这个容器：

我们看这个，我们使用迭代器进行遍历然后使用箭头->解引用得到数据打印；

这个原理是什么呢？因为我们的vector的迭代器就是他的原生指针，我们的vector是一个顺序表，里面的每个元素的都是AA类型的对象，我们的迭代器指向某一个位置，这个位置的数据就是一个AA对象，那么这个迭代器就是指向这个位置的指针，那么这个指针就相当于是一个结构体struct指针，我们使用指针->得到结构体里面的数据a1和a2。