C++ list 容器类的模拟实现

 前言：

我们不仅仅要熟悉使用c++标准库中的 list 容器，我们更要学习了解标准库是如何将 list 容器实现出来的，这就是我们常说的知其然也要知其所以然，学习源码中优秀的部分，将 list 容器进行模拟实现出来，使得我们对标准库中的 list 容器的使用更加深刻。下面我就通过这篇文章来介绍 list 容器的模拟实现，希望能够给大家带来不一样的收获，如有问题，欢迎大家在评论区进行指正。

文章摘要：

文章内容包括 模板节点类的实现、模板迭代器的实现、模板list类的实现，以及三者相互作用所模拟实现的lsit容器的思路介绍

list的模拟实现通过三个部分的框架来实现，分别是节点类、迭代器类、list类三部分来构成。下面我先将这三个基本框架搭建出来

节点类

我们为什么会想到去创建一个节点类呢？？？

我们知道链表是通过节点之间的链接构成，节点类是为了创建节点供list类使用

这里我们根据带头双向循环链表的结构定义出 data  prev  next，通过构造函数进行其初始化，其中构造函数中提供参数的含义为 通过一个匿名对象来调用 T 类型的构造函数去进行赋值给 x ，通过绑定x,延长匿名对象的生命周期，通过 x 将匿名对象的值赋给数据域。

节点类的定义就是为了list 类的使用，因此节点类的定义我们没有用class 而是用了struct 是为了方便使用节点类，struct 和class 的区别就是struct中的所有数据都是公有的便于访问。

这里我们为什么要将 list_node 进行 typedef 一下呢，也没有提供多少遍历啊？？当我们看到下文时我们就会理解，list类是会频繁调用节点类和迭代器类的，类名+模板参数T才是类型，如果没将其typedef,非常容易漏掉模板参数T代码的可读性也比较差

迭代器类

list的底层就是带头双向循环链表，list与vector不同的是list是通过指针进行将各个存储数据节点进行链接，我们要想进行链表的数据的遍历，不能像vector那样仅仅通过原生指针的++来实现数据的访问，因为链表存储的数据在物理结构中不是连续的不能通过简单的原生指针++来实现

指针分为原生指针和封装指针，迭代器就是封装指针，通过对原生指针的封装，使得迭代器具有和指针一样的功能，这也就是封装的意义所在，用户不必了解底层是如何实现的情况下，也能够很好的去使用

迭代器类成员变量是一个指向节点的指针，构造函数通过传参将 _node进行初始化，指向我们想要指向的节点

通过对原生指针的封装，迭代器应该具有 指针的解引用、指针的移动、！=等用法。

• 模板参数

• 迭代器类的构造函数

通过传过去的节点进行初始化，使得迭代器能够指向对应节点

• 解引用

这里返回值本来应该是T, 通过用模板参数Ref进行替代的原因如下

当我们想使用用const修饰的迭代器进行遍历容器时，我们使用const_iterator进行访问遍历容器本质原因就是不希望容器中存储的数据能够在访问遍历的过程中被修改，希望将容器中的数据进行保护起来，那么我们想到将迭代器中的解引用函数的返回值类型通过const 进行修饰就可以达到我们的目的，最容易想到的就是在定义一个const迭代器类，将上面迭代器类中的各种函数进行复制过来，然后将operator*（）的返回值换成const T,其余都没有变化，而且这两个类的结构完全相似，通过观察STL下的源码，我们发现我们写STL的大佬是通过在模板中又增加了一个参数将代码进行了优化，通过在模板中增加参数，我们在使用正常迭代器时将Ref给成T&,要是使用const迭代器时将Ref给成const T&即可

• 前置++

前置++将迭代器所指向的位置向节点的下一个位置进行移动，然后返回移动后的位置

• 后置++

后置++通过传入的参数 int 进行函数重载，我们在进行使用时，不用进行传参区分，编译器的底层已经通过汇编进行实现好了，我们只需要站在前人的肩膀上看世界就好了，通过拷贝将原来节点的值拷贝给temp，然后将指针进行移动，返回之前拷贝的值。

• 前置--

• 后置--

• ！=

将迭代器指针和我们将要比较指针的地址进行比较，如果不相等则返回ture，反之返回false.

• ==

• ->

这里Ptr和上面operator*()中的Ref有异曲同工之妙，通过模板参数Ptr，当我们使用const迭代器时迭代器的类模板参数Ptr就是const T*，使得容器中的内容也不能通过指针进行改变；当我们使用的是普通迭代器时，类模板参数Ptr就是T*,允许通过指针对容器中的内容发生改变。

当我们要通过迭代器进行访问打印自定义类型中的数据时，迭代器相当于传入模板参数类型的指针，这里我们定义了一个自定义类型AA，迭代器相当于指向这个类的指针，我们要进行访问这个类中的元素时，需要先将迭代器指针进行解引用拿到这个结构体，然后通过 . 进行访问结构体中的元素。这样进行访问的可读性是非常差的，我们根据上面访问数据的步骤，通过运算符重载->,便于访问自定义类型下的数据。

operator->的实现

list 类

基本框架

通过多传两个类模板参数从而巧妙的将const迭代器进行实现出来，当我们使用的迭代器是普通迭代器时,类模板参数Ref就是T&，Ptr就是T*；当我们使用的是const迭代器时,类模板参数Ref就是const T&，Ptr就是const T*

list的构造函数

• 默认构造

• 迭代器范围构造

这里注意一定要加上初始化节点

• 拷贝构造

赋值重载

插入删除操作

• 任意位置插入

• 任意位置删除

• 尾插

• 尾删

• 头插

• 头删

迭代器

• 普通迭代器

• const迭代器

一些其他函数

• swap

• clear

clear是清除头节点以外的节点，不会将头节点清除，清除头节点是析构函数的功能。

传统写法的思路介绍

通过一个节点指针cur，从头节点的下课一个节点开始，记录cur的下一个位置，方便删除cur指向的节点后找到下一个要删除的节点，通过指针的遍历进行删除。

现代写法一

思路同上，这里要进行解释的是删除it指向的位置后在进行后置++难道不会出现迭代器失效问题吗？答案是不会的，原因如下，后置++是将原来位置进行拷贝下来，删除的是it指针的拷贝，并不是真正的it指针。

现代写法二

通过返回值保留 it 指针的的下一个位置然后删除it指针的指向。