C++STL之List的实现

发布时间:2023年12月17日

首先我们要实现List的STL,我们首先要学会双向带头链表的数据结构。那么第一步肯定是要构建我们的节点的数据结构。

首先要有数据域,前后指针域即可。

再通过模板类进行模板化。

然后再写List的构造函数,这个地方用T&,通过引用就可以减少一次形参拷贝的发生,提高性能。

其次const可以提高安全性和扩展性,这样const T&和T&就都能传引用,但是又保证了数据的不可修改。

然后我们再写List类和迭代器。

迭代器的作用其实就是将容器内容的访问与修改进行包装,使得使用的程序员可以不直接对底层数据进行修改,这样不仅提高了数据的安全性,并且提高了使用者的规范性和代码的可读性。也通过屏蔽底层实现增加了移植性。

首先我们先分析迭代器和List的类的基本成员和模板的使用。

迭代器中实际的成员仍然是我们的原生节点指针,但通过迭代器的包装,就避免了我们直接使用节点,更避免了我们直接操控节点的数据域和指针域,起到多重包装的作用。

List本质是一个对节点操作的工具,所以只需要携带一个size统计数量和锁定头节点(这里是哨兵卫节点)就可以了,本身不携带数据节点的内容。

然后就是分析模板的使用,先对List进行分析。

首先定义出我们的模板T,然后为了实现const迭代器和普通迭代器,正常情况下我们要实现两遍,但是由于存在模板我们可以将这个重复的工作交给编译器。

本质就是通过List<>先锁定T模板是什么类型再通过::域限定符去调用里面的常量迭代器的类模板参数列表并且通过()调用构造函数。

于是我们通过模板实现了两个类型的迭代器,借助编译器进行实现。

理清楚了我们的模板用法,剩下的工作就驾轻就熟了

首先实现插入,这样我们的头插,尾插就可以复用insert了。

同样我们可以先写erase,这样后面头删,尾删就可以复用erase了。

其他实现也非常简单,主要要讲的就是list的析构函数和=的运算符重载。

析构函数就是先清除数据再抹掉头节点即可,没有很大难度。但是一定要分清楚顺序,不要先抹除头节点或者忘记抹除。

运算符重载的写法是现代写法,主要可以方便,形参的lt会被编译器自动回收,而不用自己去操作内存,减少代码量。

然后我们来研究list的构造函数,首先我们要写一个空链表的构造,也就是头节点的构造函数,可以为我们的无参构造和初始化提供方便。那么无参构造就可以直接复用了,而有参构造也可以直接利用其进行头节点的初始化。

当我们完善了List,接下来我们就可以继续完善我们迭代器。

主要就是实现各个运算符的重载,难度不大。

但是我们要注意的是各个重载的返回类型!

首先对于+,-这种移动显然返回类型应该也是相应的迭代器类。

然后就是对迭代器解引用显然就是要获取对应的数据,所以返回的是其数据内容(数据的引用)

而->其实外层会有一个->所以我们实现的时候不能直接把数据内容传出去,而是要返回数据的地址,不然就是错误的。本质可以写出(&(-node->data))->data。

==和!=显然返回bool值就没有其他内容了。

文章来源:https://blog.csdn.net/qq_35639854/article/details/134955403
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。