个人主页 : zxctscl 如有转载请先通知
在前面一篇博客中分享了list的相关介绍 【C++】list介绍,这次来模拟实现一下list。
成员变量:
无参构造:
插入:
在库里面定义节点需要全部公有时用到的就是struct:
这里我们也用相同方法自己定义出一个节点:
然后在写list类时候就要用到上面结构体。
list类里面成员变量就有:
先来一个无参构造,实现的双向带头循环链表,先定义哨兵位节点,让它的next和prev都指向自己:
链表的拷贝构造,先写一个初始化链表的函数:
就直接在初始化的基础上,遍历拷贝的数据,再把数据全部插入到新链表就可以了:
测试一下:
直接复用swap,出了作用域lt之前的数据会销毁,再返回*this就可以了。
析构在clear的基础上,要把哨兵位也删除
怎么判断要不要析构? 如果需要析构,一般就需要自己写深拷贝 如果不需要析构,一般就不需要自己写深拷贝,默认浅拷贝就可以
这里原生指针不能充当迭代器,list物理空间不连续,这里Node*
加加不能到下一个节点,而且解引用Node*
是Node也不能找到数据。这时Node*已经不能满足需求了,这里就得封装一个类。内置类型不能满足需求,就自定义类型。
来看看库里面是怎么实现的:
来实现一下:
实现加加,加加就到下一个位置,需要迭代器去访问
代码实现:
前置加加:返回的是加加之前的node,所以得先记录下数据(拷贝构造一份),再加加,然后返回之前记录下的节点。
后置减减和后置加加类似:
前置减减和前置加加类似:
这里*it返回的是什么值? 要返回的时节点里面的data
!=
和==
比较两个迭代器相不相等,比较的是节点的指针
重载==:
begin执行第一个节点,也就是head的next
这里是用来匿名对象来构造迭代器:
还可以写成: 单参数的构造,支持隐私类型转换
end指向的是head
不能直接在原来的迭代器上面加上const,会导致普通迭代器就不能修改了。 const迭代器,需要是迭代器不能修改,还是迭代器指向的内容? 迭代器指向的内容不能修改!const iterator不是我们需要const迭代器,所以不能在普通迭代器的前面加const。
使用就增加一个重载的const迭代器:
那么就得单独搞一个类ListConstIterator,让const迭代器*it不能修改:再把相同的操作符重载一下
发现普通迭代器和const迭代器里面很多运算符都是一样的,而const迭代器里面就直是不能修改指向的内容,代码显得冗余。就可以用模板来修改这两个类,把他们两个融成一个类。
就是返回值的类型不同,就用模板变,用一个模板参数:template<class T, class Ref, class Ptr>
:
本质上相当于我们写了一个类模板,编译器实例化生成两个类。
从而在list类里面就修改为:
insert实现在某一个位置之前插入一个节点 先搞一个节点,然后记录原链表pos位置的指针,然后一前一后改指向
新开一个节点,然后让原链表的tail指向新节点,让新节点的prev指向tail,再把head的prev改为新节点,新节点的next改为head。
代码实现:
来测试一下:
push_back用erase来实现会更简单:在end位置插入一个数
头插就是在begin插入一个数:
测试一下:
先记录下要删除的节点,和它前一个节点prev 还有它的后一个节点next。然后让prev的_next 指向next;next的_prev 指向 prev。 删除会导致迭代器失效的问题,为了避免,就返回删除节点的下一个位置。
尾删复用erase,而尾是在end前面的一个位置,所以先减减end再删除
因为begin所在的位置就是头节点,所以直接删除begin就可以:
用户自定义一个类型:
调用push_back插入数据,可以是匿名对象,也可以多参数进行隐式类型转换:
但是要把数据输出到屏幕上,使用*it是不可以的:
A是一个自定义类型,A不支持流插入,要想指出就得自己写一个重载一个。如果不想写,可以换个方式,这里的数据是公有的可以直接访问。 就直接*it返回的是A,再拿到a1和a2的数据就可以:
这里A*的一个指针访问数据是先解引用,返回A对象,再来.对象里面的成员变量:
迭代器就是想要模仿A*的行为,所以迭代器就重载了一个->:it->,它返回的是data的地址。
访问它里面的就是这样:
其实是编译器为了可读性,省略了一个箭头:第一个箭头是运算符重载,就返回data里面的地址也就是A*,第二个箭头就能访问A里面的数据了。
原生指针的行为就是:
测试一下都能使用:
直接调用库里面的swap来交换:
clear清理掉所有数据,直接复用迭代器来把数据全部删除,但是没有清理掉哨兵位head