昨天我们完善了单链栈,今天我们开始实现一个双向链表的旅程!
我们前面实现了一个不可变的持久性链表,现在我们来将它变成可变的,也就是使用内部可变的方式,另外我们还准备将它拓展成一个双链的队列(张emo: 是不是很大胆?.jpg)。
老规矩,src
下搞一个fourth.rs
的文件并在lib.rs
中引入。
上来自然就是调整结构,因为当前是不可变的,不能满足要求。
这个时候就需要使用到RefCell
,也就是内部可变,它的核心是下面俩方法:
正如它俩的名字一样,就是返回一个内部的引用&
和可变引用&mut
。
不过他俩是在runtime
的,当然,还是得满足rust
定义的借用规则,borrow_mut
仅只能有一个,如果有问题,会直接panic
终止程序。
现在我们支持可变
了,然后我们来拓展下我们的类型,让它变双向
所谓双向
,就是当前节点保有前一个节点的指针的同时,还保有后一个节点的指针
。
这个代码编译是没问题的,但是有一个致命
的问题,这里先不说,等会就会遇到了。
然后我们来补充下一些方法:
new
还是那样,只是多一个tail
然后我们来实现push
,因为我们现在有头尾两个入口♂,所以我们得写两个方法用来添加节点:
如果是空的,那么需要同时初始化头尾两个指针
,如果不是,那我们只需要维护头
即可,将当前的头的prev
指向新的节点,将新的节点的next
指向头
,然后将head
指针指向这个新的节点,也就是更新头
的指向。
不过这个代码报错了
因为new_head
和old_head
是一个Rc<RefCell<Node<T>>>
的类型,并不能直接访问它内部的数据。
回看我们之前的代码,是可以直接访问
的,但是现在因为RefCell
的问题,我们失去了
直接访问内部数据的资格!
貌似前面还没描述过RefCell
,只是说了它可以内部可变。。
A mutable memory location with dynamically checked borrow rules
具有动态检查借用规则的可变内存位置。
有点难懂,但是关键字我们认得:动态
,借用规则
,可变
,内存位置
(为什么搭配在一起就看不懂了)
runtime
,编译器
管不了(当然,管不了是管不了,该panic
还是会panic
)内部数据
的借用
,可变和不可变都可以(符合借用规则)我们可以更具体点:module-level documentation
简单地说就是一个共享的可变容器(shareable mutable containers
)
其实RefCell<T>
还有一个兄弟Cell<T>
,他俩都是差不多,提供内部可变性,区别在于Cell<T>
需要T
实现Copy
,而不能实现Copy
的类型只能使用RefCell<T>
。
换句话说,Cell<T>
里的T
实现了Copy
,那么它实际上可以直接copy
一份数据,所以它的俩方法非常直接,get
和set
。没有引用参与。
回到RefCell<T>
,这货是使用生命周期
的规则来实现动态借用(dynamic borrowing)
。
那么什么时候需要使用到内部可变呢?一般有以下三种:
Introducing inherited mutability roots to shared types.
)logically-immutable
)的方法细节时(?)Clone
共享智能指针类型(包括 Rc 和
一般我们都是把一个可变引用放到RefCell<T>
里面来重写它的可变性。
最后说一下,这货是单线程的,多线程是Mutex
。
Rc
和RefCell
搭配,Arc
和Mutex
搭配。
ok,回到我们的代码
这回就没问题了。
有进就有出,有push_front
自然就有pop_front
。逻辑差不多
但是这里有点问题,old_head
没进入到数据里,还是之前RefCell
的问题。
你的第一想法应该是如下:
但是这里还有个问题,那就是这个数据的Copy
,我们是返回Option<T>
,泛型是不可能支持Copy
的,所以这么改是没办法跑通的,喜提
报错如下:
借给你的,结果你直接戴着跑了??(阿三行为)
但是你这是废弃的节点啊,我拿你数据怎么了我?(理直气壮)
你说废弃就废弃啊,我不用 其它人也不用?(别忘了Rc
)
我不管,我就是要拿(突然掏出小镰刀:RefCell::into_inner
,这个方法可以直接拿到内部的T
,我已经受够繁文缛节了
.jpg)
暗月骑士(编译器)出警!(太dark啦~)
但说正经的,如果真的想要呢?
这个时候只能是尝试,如果拿不到只能是返回None
(?)
还是try_unwrap
,不过我们这里还多了个ok
,这个方法简单地说就是将Result<T, E>
变成Option<T>
,否则为None
。至于为什么不能直接unwrap Result<T, E>
,因为我们的类型没有实现Debug
,至于Result
为什么要求要实现Debug
,因为要支持错误输出。
然后我们从我们之前的代码中偷几个测试用例,然后微调下:
搞定(了吗)(Nailed it)
其实我们这里还是有问题的,存在两个引用计数以上,我们就拿不到pop_front
出来的数据。
drop
也是比较复杂的事情,因为可能会遇到循环引用
的问题,目前我们先简单的实现一个
让节点的计数 - 1。
要珍惜编译的报错,因为接下来编译成功也不一定可以运行成功π_π。。
我们现在实现了pop_front
和push_front
,那么接下来自然轮到peek_front
,应该还算是简单。
对...对吗?(戴佳伟.jpg)
回想一下,我们要的效果是获取头节点的数据引用
但是你会遇到一个奇怪的报错:
returns a value referencing data owned by the current function
有点摸不着头脑,为了解决这个问题,我们得会看下borrow
方法:
这里有两个类型Ref
和RefMut
,它俩大部分时候都和&、&mut
差不多,但是不完全一样。
其实我们之前学过这俩,这里权当复习,Ref
实现了Deref
,而RefMut
实现了DerefMut
, 所以我们可以通过*
的方式去进入数据内部,这和&
以及&mut
表现是一致的。
但是,这就导致生命周期不一致问题,我们通过borrow().elem
拿到的数据的生命周期和Ref
是一致的,而不是RefCell<T>
。
所以会有上面这个问题,知道原因了,那我们咋整呢?
简单,让borrow
的内容和node
生命周期一致就行,我们直接把Ref
抛出去
当然,这是有问题的:
类型不对,我们borrow()
返回的类型是Ref<Node<T>>
(&
其实是ref
,因为用了as_ref
)。
这个也简单,和Option::map
类似,Ref::map
也是可以将T
类型变成U
:
正好可以用来将我们的Ref<Node<T>>
变成Ref<T>
。
搞个测试用例:
跑的通!
既然front
的都搞完了,我们接下来就来同步back
的,逻辑基本上一样的
以及测试用例
迭代这块在搞懂RefCell
和Rc
等一系列知识之后现在反而简单了一些
这货简单,就是从头pop
,直接调用内部的pop_front
即可。
好像少了什么,诶,我们是双向队列诶,为什么只有从头next
的。
因为我们是实现的Iterator
,它只有一个next
方法,当然也有双向的DoubleEndedIterator
,它多一个next_back
的方法。
测试用例:
然后轮到Iter
这货还是非常麻烦。。。
我们的先来将引用类型变成Ref
然后毫无意外的遇到问题:
Ref
试图逃逸我们抛出的ref
的生命周期和node_ref
一样,但是这货活的不够长,等会可能被销毁,所以我们得想个办法把数据拆出来,而不是使用Ref
包裹,因为Ref
生命周期不够长。
那么我们就不能使用map
,幸运的是这里还有个map_split
的方法:
居然可以拆分两个Ref
。
我们来试下:
ok,就剩下这货了
emmm,我们还需要重新借助Ref::Map
来让我们的生命周期正常,但是Ref::Map
又返回一个Ref
,但是我们需要Option<Ref>
,但是我们又需要通过Ref
来map
我们的Option
.....
stares into distance for a long time
??????
然后又报错了,太好啦!
拿到的是一个RefCell
,然后当我们继续尝试borrow
的时候,我们。。。进入了死循环。
太好啦!大快人心,喜大普奔,奔走相告,普天同庆
然后我们尝试拿走RefCell
这个万恶之源,谁说我们需要用RefCell
的,我们只是需要返回元素的引用,甚至引用都不用,Rc::clone
天然返回指针。
写到这突然不知道咋写了,类型定义为&T
还是Ref<T>
?
都不行,因为我们生命周期莫得了
,然后我们再花力气给它加回去?
然而就算我们把生命周期给它加回去,我们返回的都会引用到迭代器。。。
慢着!借用个毛,我们直接返回Rc<T>
?!
然而不支持,即使支持了,我们还有一个大问题:Iter
是不可变的,我们返回了个Rc
, 那意味着别人并不会引用链表,这意味着人们可以在将指针伸入列表的同时开始调用推送并弹出列表!
我......我TM放弃!
正如前面我们peek
只能尝试去“看“一样,这个方案基本可以宣告死亡,到处捉襟见肘不得不降低自己的预期。
失败了!
我们要尝试别的方案
Rc
和RefCell
可能太**“安全”
**了,导致需要和各种限制互搏
,也可能我们的步子迈的太开(怎么可能承认是自己的问题,笑)
我们可能需要尝试触碰那幽邃的unsafe
,终究还是火灭了,进入深海时代...
难搞,开始有些复杂了,也是从这里开始,我的思维乱了。。。
接下来我们准备接触unsafe
!