C++：List的使用和模拟实现

小陈在拼命

发布于 2024-03-09 08:54:35

860

发布于 2024-03-09 08:54:35

文章被收录于专栏：C/C＋＋、数据结构、算法C/C＋＋、数据结构、算法

一、List的介绍

list的文档介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。

4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。

5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素) 要注意的是，list开始就不支持下标访问了，所以要访问都要以迭代器为准

二、List的使用注意事项

博主觉得跟之前vector的基本上差不了多少，如果不会看文档用库里面的list的可以去看博主只管关于string和vector的使用。

C++：String类的使用-CSDN博客

C++：Vector的使用-CSDN博客

下面直接介绍List使用中的易错点

2.1 List的迭代器失效问题

我们之前学习vector的时候，知道了insert和erase都有可能存在迭代器失效的问题，那list会出现这种情况吗？？下面来进行分析

insert插入新节点的迭代器，因此insert不可能会出现失效的问题。

而earse必然会失效，因为该迭代器对应的节点被删除了。如果我们想继续用的话，就得利用返回值去更新迭代器，返回值是被删除元素的下一个位置的迭代器。

2.2 List中sort的效率测试

我们用一段代码来测试一下list中sort的性能

会发现哪怕我先拷贝到vector排完再拷贝回去效率都比list的sort效率高，所以list的sort实际中意义不是很大！！

三、模拟实现的注意事项

还是跟之前模拟实现一样，先看看SGI版本的源码，list本质上是带头双向链表

第一部分链表节点

第二部分迭代器

第三部分、链表

这里我们可以先实现链表节点结构体这里用sturct把权限放开。

然后封装一个链表，将头结点作为自己的成员变量封装起来

下面开始进行我们的重中之重——迭代器

四、正向迭代器的实现

2.1 正向迭代器的封装

在学习Vector的时候，我们发现其实vector的迭代器就是一个原生指针，所以我们将他改了名字

这得益于vector空间连续的特点，所以对指针进行加和减再进行解引用可以访问到我们想要的元素，但是链表可以吗？

虽然看似我们好像用箭头连接起来了，但其实他们空间上是不连续的，那我们对一个节点指针进行加减，就很难说能不能找到下一个节点，更多的是找不到的情况

那我们思考一样，如果我们要搞一个迭代器，我们希望怎么去得到我们的数据呢？？我们希望我们解引用的时候，可以拿到他的data，希望++的时候，可以拿到他的next，--的时候，可以拿到他的prev。那我们怎么去改变原生操作符的行为呢？答案就是运算符重载！所以我们可以将迭代器单独封装成一个类去管理节点，改变运算符的行为！！

我们先进行实现，然后再慢慢分析

第一个模版参数是类型，第二个模版参数是引用，第三个模版参数是指针

Ref和Ptr是用来区分正常的迭代器和const修饰的迭代器，Ref是T&或者是const T&,这样可以在某些时候我们去限制data不能被修改。而Ptr是T*或者是const T*，重载箭头的作用是如果我们data存储的是一个自定义类型，这个时候如果直接解引用肯定是不行的，所以我们的箭头可以在解引用的时候先返回data的地址，然后我们就可以通过箭头去访问他不同的成员变量。

下面举个data存的是自定义类型的例子

2.2 迭代器的使用

这边我们用到了匿名对象。

思考：这里的const迭代器为什么不能直接用const修饰普通迭代器？？

因为typedef碰到const的话，就不是简单的字符串替换实际上你以为的const T* ，在这里变成了T*const ，因为迭代器我们是希望他可以进行++和--的，而我们只是不希望他指向的内容给改变，所以我们的const要修饰的是指针的内容，而不是修饰指针。

五、list相关的成员函数

3.1 构造函数

1、默认构造函数

因为无论如何都要有哨兵节点，所以我们直接封装一个

所以可以这么写

2、有参构造函数

3、迭代器区间构造函数

4、拷贝构造的传统写法

传统方法就是一个个拷贝过去

5、拷贝构造的现代写法+swap

现代写法就是，我先创建一个临时对象让他利用被拷贝对象的迭代器构造出来，然后再交换，窃取革命成功，被利用完后的临时对象会在栈帧结束后被清除（典型的资本家思维）

3.2 clear和析构函数

list不像vector一样，不能直接用头指针delete，因为空间不连续，所以要一个个节点去delete，所以在这之前，我们可以先实现clear，clear的作用是把链表清空，只剩一个头节点，然我们的析构函数再复用clear，然后再单独delete头节点就行了！！

3.3 赋值重载和assign

assign和=的本质上都是，先将原来的空间的内容给清空，换成的内容。只不过区别就是assign可以利用迭代器去控制被替换的范围，也可以自己去换成n个一样的元素。所以我们先实现assign，再实现=

1、assign直接替换

2、assign迭代器区间替换

3、assign直接替换重载（防止间接寻址）

思考：我们的本意是将lt2替换成5个2，我们发现我们调的竟然是迭代器区间构造的assign，为什么会这样呢？？？？？

因为重载类型会优先找最匹配的，assign的第一个版本的n是size_t类型，我们传的整数默认是int所以会发生强制类型转化，而第二个版本恰好可以变成两个int，所以他会走迭代器区间版本。所以此时有两个方案，第一个方案是我们要在第一个参数后面加u，但是这不符合我们的使用习惯，所以我们可以采用第二个方案，写个重载版本。