📝个人主页🌹: Eternity._ ⏩收录专栏⏪: C++ “ 登神长阶 ” 🤡往期回顾🤡: 初步了解 list 🌹🌹期待您的关注 🌹🌹
@TOC
在软件开发中,数据结构和算法的选择与实现是每一个开发者都必须面对的问题。标准模板库(STL)为我们提供了一系列高效且通用的数据结构和算法模板,极大地简化了C++编程中的许多常见任务。然而,了解这些数据结构和算法背后的实现原理,不仅有助于我们更深入地理解STL,还能提升我们的编程能力和解决问题的能力。
前言: 在STL中,list是一种双向链表,它支持在序列的任何位置进行快速插入和删除操作。与此同时,迭代器是STL中非常重要的一个概念,它使得我们能够以统一的方式遍历和访问STL容器中的元素。在深入了解STL的过程中,模拟实现list和迭代器无疑是一个极有价值的学习过程。
本节我们将从基本的链表结构开始,逐步构建出完整的list类,并实现相应的迭代器类。
📒1. list的基本结构
list是一个个带头双向循环链表,这意味着每个元素(通常称为节点)都有两个指针:一个指向前一个元素,另一个指向后一个元素,因此我们需要单独再定义一个类来表示节点结构,每个节点再串联起来构成list
节点定义(示例):
而在构建list时,我们成员变量只需要一个头节点。
list定义(示例):
📕2. list的模拟实现
注意:关于
erase
和insert
这两个函数的模拟我们依然作为补充放在末尾
🌈构造函数
在拥有一个list我们只需要将它的头节点初始化一下
list构造(示例):
🌞析构函数
关于析构函数,我们需要的是将所有节点一 一释放就ok啦!
在模拟析构函数之前,不得不先介绍一下clear
这个函数,因为clear
可以删除出头节点以外的所有节点,我们可以利用这一点帮助我们优化析构函数
list析构(示例):
🌙拷贝构造函数
在学习list时,我们发现list不会因为空间不够而需要扩容,因此在使用模拟list时,不用考虑是否会发生浅拷贝
list拷贝构造函数(示例):
⭐赋值运算符重载
这里我们以让后传统写法和现代写法两种方法
list赋值运算符重载(示例):
在介绍完list基本的结构后,让我们来看看今天的重点:迭代器
📚3. list的迭代器
在我们模拟实现string
,vector
时,我们认为迭代器就是一个原生指针,但是在list
中迭代器底层不是简单的指针,因此我们要独立定义一个新的类
🍂迭代器的基本结构
迭代器定义(示例):
我们将迭代器单独写作一个类,能解决更多的问题,以及避免其他麻烦
🍁迭代器的运算符重载
因为这些函数和前面差不太多,我们简单看看代码,带过了
代码(示例):
而今天着重要强调以下两个运算符重载,因为const
和非const
下这两个是有区别的:
在定义完迭代器类之后,我们可以实现begin()
和end()
来实现list
的范围for
🌸list的迭代器
迭代器代码(示例):
当然我们这里还没有实现
const迭代器
很多需要调用const对象
的函数还无法使用,那么接下来让我们来模拟实现const迭代器
,见证新的神奇
📙4. list的const迭代器
关于这个list的const迭代器其实有两种写法,常规的写法就是在定义一个新的
const迭代器
的类,虽然这样可以解决问题,但是会造成代码的冗余,让操作繁琐。而另一种方法就是在原有的迭代器类上进行修改,让它能具有两个迭代器都能使用的特点
🎩方法一
const迭代器实现(示例):
🎈方法二
如果我们将这两个差异的内容单独表示出来归于模板中,因为在const与非const之间
,无非就是T&,T*上能否读写的区别
,不影响其他的函数实现,因此我们可以在模板上加上两个参数
模板参数 | 实例化类型 |
Ref | T&,(const 变量时) const T& |
Ptr | T*,(const 变量时) const T* |
const迭代器实现(示例):
关于list的模拟实现我们就讲到这里,让我看看如何以统一的方式遍历和访问STL容器中的元素
📜5. 统一的方式访问STL容器中的元素
在完成对list的模拟实现后,我们试着用来遍历和访问list中的元素
代码实现(示例):
编译器不知道 list::const_iterator 是内嵌类型,还是静态成员变量,但是如果实例化成int
后,有需要一个成员是string
的列表这时我们有犯难了,这时我们就要用到typename
,typename
就是告诉编译器,这是一个类型,等list实例化之后再去取
代码实现(示例):
但是更离谱的来了,这时又有人要求我们打印vector
的值,容器都换了我们该怎么办呢?这时模板的作用又双体现出来了,这也体现了模板的本质,让我们能省的活交给编译器完成
代码实现(示例):
它使得我们能够以统一的方式遍历和访问STL容器中的元素
📔6. list与vector的对比
我们可以发现list与之前学的竟然有那么多的差异,我们结合上节学的vector
来分析一下它们的差异:vector
与list
都是STL中非常重要的序列式容器,由于两个容器的底层结构不同,导致其特性以及应用场景不同
vector | list | |
底 层 结 构 | 动态顺序表,一段连续空间 | 带头结点的双向循环链表 |
随 机 访 问 | 支持随机访问,访问某个元素效率O(1) | 不支持随机访问,访问某个元素效率O(N) |
插 入 和 删 除 | 任意位置插入和删除效率低,需要搬移元素,时间复杂度为O(N),插入时有可能需要增容, | 任意位置插入和删除效率高,不需要搬移元素,时间复杂度为O(1) |
空 间 利 用 率 | 底层为连续空间,不容易造成内存碎片,空间利用率高,缓存利用率高 | 底层节点动态开辟,小节点容易造成内存碎片,空间利用率低,缓存利用率低 |
迭 代 器 | 插入删除时触发条件会导致迭代器失效 | 删除元素时,只会导致当前迭代器失效,其他迭代器不受影响 |
使 用 场 景 | 需要高效存储,支持随机访问,不关心插入删除效率 | 大量插入和删除操作,不关心随机访问 |
📖7. 总结补充
💧补充:insert和erase的模拟实现
代码实现(示例):
🔥总结
通过本次对STL中list和迭代器模拟实现的探索,我们深入了解了双向链表的基本结构、操作原理以及迭代器在遍历和访问链表元素中的重要作用。模拟实现的过程不仅让我们对STL中的list容器有了更深刻的理解,也锻炼了我们的编程能力和解决问题的能力
- 在模拟实现的过程中,我们学习了如何设计并实现一个双向链表结构,包括节点的定义、链表的插入、删除和遍历等操作。同时,我们也掌握了迭代器的基本概念和实现方法,理解了如何通过迭代器来统一访问和遍历不同的容器类型。
- 模拟实现STL中的list和迭代器是一个既有趣又富有挑战性的过程。它让我们更加深入地理解了数据结构和算法的基本原理,也为我们日后在实际项目中高效应用STL容器打下了坚实的基础。
最后,感谢大家的耐心阅读和学习。希望本次介绍能够为大家在STL学习和编程实践中提供一些帮助和启示。在未来的学习和工作中,让我们继续深入探索STL的奥秘,不断提升自己的编程能力和解决问题的能力
谢谢大家支持本篇到这里就结束了,祝大家天天开心!