当前位置：首页 > news >正文

手撕 STL 之—— list

news 来源：原创 2025/9/16 19:53:21

引言

1, list_node类及其构造函数

2, list类的创建

3, list基本功能函数

3_1，构造函数

3_2，push_back

3_3，push_front

3_4， pop_back

3_5，pop_front

4，迭代器 (重点)

4_1，如何设计list迭代器

4_2，begin() end()

4_3，operator != () operator == ()

4_4，operator++() operator--()

4_5， operator *()

4_6，const_iterator（超重点，难点）

4_6，operator->()

5，list 功能完善

5_1，拷贝构造函数

5_2，赋值运算符重载

5_3，clear()

5_4，析构函数

5_5，insert

5_6，erase

不足

结束语

革命尚未成功，同志仍须努力

引言

上一期咱们手撕了 string，这一期我就带着大家手撕 list

1, list_node类及其构造函数

在C语言阶段，我们用宏定义粗略处理了 list 存储不同类型数据的问题，前期我们学习了模板，模板功能的强大之处在这里就能很好体现。

对于list_node 的构造函数，参数必然是 T 类型的 data，用 data 创建结点，但是哨兵位的头结点中的 data 是步存放数据的，那我们该怎么处理呢？给他初始化为 0 ？那 T 如果是自定义类型呢？不卖关子了，这里我们要一个知识叫做 “匿名对象”

T( ) 是一个匿名对象，对于内置类型，会根据类型的不同特性进行不同的初始化，例如 int（）会初始化为 0 ，指针类型会初始化为 nullptr；对于自定义类型，会去调用它的默认构造函数进行初始化工作

2, list类的创建

在 STL 中 list 是双向带头循环链表，那这里我们与 STL 保持一致。

首先也是用模板处理不同数据类型。在 list 这个类里面，成员变量仅需一个头结的指针 head 就OK了，因为链表嘛，咱知道一个头节点就可以通过链式关系找到其他的结点

3, list基本功能函数

3_1，构造函数

咱们要知道咱们的 list 是带哨兵位的头结点的，所以在构造函数中，我们要创建哨兵位的头节点，并创建一个双向带头循环链表的雏形。

3_2，push_back

尾插在链表中是非常基础的一个功能，完成尾插就三步

1，创建新结点

2，将新结点连入链表

3，更改原链表的链接关系

3_3，push_front

头插与尾插的操作思想大致一样

3_4， pop_back

尾删在链表中是非常基础的一个功能，完成尾删也就三步

1，标记带删除结点

2，更改链表的链接关系

3，删除结点

3_5，pop_front

头删的操作思想与尾删大致一样

头插，尾插，头删，尾删就是 list 里面基础的功能函数啦，写到这里， list 就可以跑起来啦。

4，迭代器 (重点)

4_1，如何设计list迭代器

我们先看看我们在使用的时候是怎么样的

在vector中，迭代器就是 T* typedef 得来的，因为vector是一块连续的空间，我们可以通过++，--等运算来控制迭代器的走向，但是再list中，空间不是连续的，我们好像不能像vector那样直接设计迭代器。那我们该怎么设计list的迭代器呢？

我们可以创建一个类，在类里面通过运算符重载来实现迭代器的各种操作。

4_2，begin() end()

有了list_iterator这个类之后，我们在 list 里面，将list_iterator typedef 一下，就完成了iterator的创建啦。

然后就是begin(), end() 函数啦，注意：begin() / end() 是list 的对象调用的，所以begin() / end()是list的成员函数

这里有一个小知识点就是隐式类型的转换，返回值的类型是 iterator 这个类，但我们 return 的是一个 Node* 类型的。单参数的构造函数支持隐式类型的转换，这里发生了隐式类型的转化。

4_3，operator != () operator == ()

iterator 中较为简单的运算符重载，成员变量是 list_node<T>* 的指针，要判断俩迭代器是否相同，直接比较这俩个指针就可以啦

4_4，operator++() operator--()

成员变量是链表结点的指针，我们可以根据链表的链接关系 _next, _prev来找到该结点的下一个和上一个结点。

4_5， operator *()

这个直接起来就很简单啦，返回结点中的data就ok啦

4_6，const_iterator（超重点，难点）

但是有一个问题勒，迭代器不仅有 iterator 还有 const_iterator 啊，但是要是我们在 list_iterator 前面加上一个const，那么这一个类就被const修饰，成员变量就不能进行++，--操作，所以这样设计const_iterator是不可行的。

有些同学可能想到我在创建一个const_iterator的类不就好了吗，就把opertor*（）前面加上const 修饰就ok了，这是可行的，但是设计比较冗余。

我们可以再加上一个类模板参数，在模板的那一块我们可以知道，类模板会根据不同类型的参数创建不同的类，我们就可以用这个特点来创建const_iterator

那我们的 operatior* 也需要改一下

我们的从const 的版的begin() / end() 也出来了

根据我们使用的迭代器类型， iterator / const_iterator，类模板会接收不同的参数从而创建不同的类，如果我们使用的是const_iterator，那么Ref 就是 const T& ，operator*()返回的数据就不会被改变。

4_6，operator->()

如果当 T 是一个自定义类型的时候，例如 piar<int, int>，我们希望可以通过 -> 直接访问pair 的成员变量，如下图

那我们就要对 -> 进行重载，而重载的时候我们遇见了相同的问题，就是operator->()返回的数据的修改问题，iterator 可以修改，而const_iterator 不可以修改，其解决方法也是和operator*()一样，增加一个类模板参数

注意：

准确的来说，这里应该写出 it6->->first ，因为 operator->（）返回的是 data(这里是pair) 的地址，T* 的一个指针，应该在再对 T* 进行 -> 操作才能访问到 T 的成员变量，这里编译器进行了优化处理

5，list 功能完善

5_1，拷贝构造函数

拷贝构造函数，我们可以根据被拷贝对象的每个结点的data new出新结点，再通过被拷贝对象的链接关系对正在拷贝的list进行结点的链接。

当然哈，还有更好的方法，我们复用我们之前的代码，利用push_back来完成结点的创建和链接

5_2，赋值运算符重载

这里咱们介绍一种现代写法，在传参过程中我们不传引用，这个时候拷贝构造函数帮我们拷贝一份，作为operator=()的参数，我们再把他俩的头结点换一下就可以了。

5_3，clear()

清理函数就比较简单了，把链表的结点都删除，只留下头结点即可

5_4，析构函数

我们可以复用clear的代码来清理链表的结点，再清理头结点

5_5，insert

和头插尾插操作思想大致一样

1，创建新结点

2，将新结点连入链表

3，更改原链表的链接关系

5_6，erase

它也和头删尾删的操作思想大致一样

1，标记带删除结点

2，更改链表的链接关系

3，删除结点

不足

虽然咱们手撕了一个 list 但是咱们撕的只能说是一个简易版，我只是把 list 里面常用，经典的函数带着大家手撕了一下，库里面的 list 的功能是非常强大的，而且大多数函数都有多种重载。

结束语

大家可以通过这篇博客感受一下list 的创建，也可以继续完善咱们自己的list

引言

1, list_node类及其构造函数

2, list类的创建

3, list基本功能函数

3_1， 构造函数

3_2，push_back

3_3，push_front

3_4， pop_back

3_5，pop_front

4，迭代器 (重点)

4_1，如何设计list迭代器

4_2，begin() end()

4_3，operator != () operator == ()

4_4，operator++() operator--()

4_5， operator *()

4_6，const_iterator（超重点，难点）

4_6，operator->()

5，list 功能完善

5_1，拷贝构造函数

5_2，赋值运算符重载

5_3，clear()

5_4，析构函数

5_5，insert

5_6，erase

不足

结束语

革命尚未成功，同志仍须努力

相关文章：

3_1，构造函数