【C++】list的模拟实现来咯

一、整体框架

list的本质就是带头双向循环链表，我们直接来看一看整体框架：

第一个要实现测试的是push_back，后面可以直接复用insert()：

尾插就是把新结点和原来的尾结点和头结点进行链接，这是我们很熟悉的了，直接动手实现：

image-20221210091750913

这个接口是最基础的，有了这个接口，我们对于后面的实现更加容易。

二、迭代器

1、list迭代器的引入

把原生指针直接命名为迭代器？迭代器的价值在于封装底层的实现，不具体暴露底层的实现细节，提供统一的访问方式。

对于vector和string类而言，物理空间是连续的，原生的指针就是迭代器了（不一定哦，只是可能，版本可能不同），解引用就是数据了。但是对于这里的list而言，空间是不连续的，我们知道，迭代器有两个特征：1.解引用2.++ /–

此时如果解引用是拿不到数据的（空间不连续），更不用说++指向下一个结点了。所以，对于list的迭代器，原生指针已经不符合我们的需求了，我们需要去进行特殊处理：进行类的封装。我们可以通过类的封装以及运算符重载支持，这样就可以实现像内置类型一样的运算符。

2、迭代器的区分

const迭代器需要在这里重新说明一遍：

灵魂拷问：const迭代器是p1还是p2？p1

const迭代器类似p1的行为，保护指向的对象不被修改，迭代器本身可以修改

3、list迭代器的实现

迭代器的实现我们需要去考虑普通迭代器和const迭代器。这两种迭代器的不同，也会带来不同的接口。我们可以分别单独去进行实现，我们先来看一看简单的构造迭代器，只需要提供一个结点即可,看一看实现的基本框架：

注意：对于迭代器的拷贝构造和赋值重载我们并不需要自己去手动实现，编译器默认生成的就是浅拷贝，而我们需要的就是浅拷贝，这也说明了，并不是说如果有指针就需要我们去实现深拷贝。另外，迭代器通过结构体指针访问修改链表，所以，对于迭代器我们并不需要构造函数，结点的释放由链表管理。

下面，我们来看看迭代器所需要的重载运算符：

重载*

这个比较简单，就是要获取迭代器指向的数据，并且返回数据的引用：

重载++、–、！=

如果按照上面的做法，我们在来看看此时普通迭代器和const迭代器的区别：

如果是这样子去实现的话，我们就会发现，这两个迭代器的实现并没有多大的区别，唯一的区别就在于operator*的不同。const迭代器和普通迭代器的唯一区别就是普通迭代器返回T&，可读可写，const迭代器返回const T&,可读不可写，上面的代码存在很大的问题：代码冗余，所以我们应该去解决这个问题：我们可以参考源码的实现：类模板参数解决这个问题，这也是迭代器的强大之处

4、模板

同一个类模板，此时我们传递不同的参数实例化成不同的迭代器了！！！这解决了我们刚刚所说的代码冗余问题。

重载->问题：

对于内置类型我们可以通过*解引用访问数据，但是如果是自定义类型，我们访问其中的成员，就需要重载->:

对于内置类型（如上面的int），我们自然可以通过解引用访问。对于结构体指针，我们也可以（*it）对象.去进行访问成员，但是想通过->访问成员，我们就需要去进行重载了：

image-20221208102139457

实际上本来应该是it->->_row，但是这样写可读性太差，也不好用，所以编译器做了优化，省略了一个->。

三、增删查改

1、insert和erase

insert：在pos位置上一个插入，返回插入位置的迭代器，对于list的insert迭代器不会失效，vector失效是因为扩容导致pos位置造成野指针问题。

image-20221210092443015

erase:这里的带头（哨兵位）头结点不可删除，返回值是删除位置的下一个，对于list的erase迭代器是失效的

2、push_back和push_front

push_back我们前面已经实现过了，这个地方只需要复用insert即可

对于end和begin的位置：

image-20221210093213762

3、pop_back和pop_front

尾删和头删，复用erase即可

这里的尾删刚好用上了我们的重载–

四、list的接口

1、构造

默认构造

我们可以用empty_initialize()来封装初始化，方便复用，不用每次都写：

迭代器区间构造

拷贝构造

传统写法

用范围for进行尾插，但是要注意要加上&，范围for是*it赋值给给e，又是一个拷贝，e是T类型对象，依次取得容器中的数据，T如果是string类型，不断拷贝，push_back之后又销毁。

现代写法

2、析构

对于list，有单独的clear()接口，list的析构可以直接复用clear()，同时还需要我们去释放掉头结点：

3、赋值重载

传统写法

现代写法

类名和类型问题

查看官方文档，我们可以看到list没有类型：

image-20221210084548413

对于普通类：类名等价于类型,对于类模板：类名不等价于类型（如list模板，类名：list 类型：list）

类模板里面可以用类名代表类型，但是并不建议，在类外面则必须要带模板参数list

五、list和vector的对比

vector:vector的优点在于下标的随机访问，尾插尾删效率高，CPU高速缓存命中高。而缺点在于前面部分插入删除数据效率低O(N)，扩容有消耗，还存一定空间浪费。

list:list的优点在于无需扩容，按需申请释放，在任意位置插入删除O(1)。缺点在于不支持下标的随机访问，CPU高速缓存命中低。

vector和list的关系就想是在互补配合！

而对于string的insert和erase迭代器也会失效跟vector类似。但是我们并不太关注。因为string的接口参数大部分是下标支持，迭代器反而用得少。

list.h