Rust通过Box方式实现LinkedList
title: Rust通过Box方式实现LinkedList
date: 2022-10-01 10:40:19
tags:
- Rust
链表在rust中
别的语言,学习的差不多了。写个链表试试?
Rust,学习的差不多的,写个链表,逝世!
虽然rust是系统及编程语言,但那和safe代码没有什么关系,在safe代码中,你依旧不能灵活的操纵内存。
实现
我们要写一个泛型的链表。使用Option<Box<Node<T>>>
这样的形式,来组织一个最基本的链式结构。
Link
使用类型别名是由必要的。Link是如下的别名
type Link<T> = Option<Box<Node<T>>>;
这样可以避免冗长且不易阅读的代码。然后请你记住一个重要的,Link不是一个指针类型,你很可能基于C风格语言的习惯将Link看作一个指针——在我们这个例子中不是这样的。但可以做到这样,那是unsafe的事情了。在我们例子中,**Link是一个Option。**使用Option<Box<>>
可以模拟出类似指针的东西。但是你在处理LinkedList的时候大可将其当作一个指针来看待。
Node
我们需要一个T类型的数据,和一个next来“指向”下一个Node。
struct Node<T> {
data: T,
next: Link<T>,
}
LinkedList
只需要一个头指针,就可以找到整个LinkedList。这个head类似于C 中的Node*
,在构造的时候head = nullptr
,就是说,头指针不默认指向一个节点。
pub struct LinkedList<T> {
head: Link<T>,
}
为什么没有提供size?
对于单向链表的size相关操作,需要额外的维护成本。如果使用单项链表,不要求size操作。否则使用双向链表。
new
new关联方法,返回一个初始化的LinkedList,只需要将head初始化为None即可。
pub fn new() -> Self {
LinkedList {
head: None,
}
}
push_front
头插入一个节点。
在编码之前,我们需要想想如何进行节点的额移动。
-
首先,这个操作会改变链表,所以需要&mut self做参数。
-
在方法体中,新建一个节点,并赋予初值。
-
让新建节点的next指向头
-
头指向新建节点
这些操作,你在数据结构中已经看见过了,而且身经百战的你,在经历各种语言的摧残之后,心想:这还不简单?但是rust却给了你当头一棒。你试尽了你能想到的所有办法,却只写出一段自己都不愿意阅读的,撇脚的代码。这就是作者的真实经历。
“独学而无友,则孤陋而寡闻”。是时候看一看别人是怎样写的了。
pub fn push_front(&mut self, val: T) {
let new_node = Box::new(Node {
data: val,
next: self.head.take(),
});
self.head = Some(new_node)
}
我们来一点点分析
创建一个新的节点
let new_node = Box::new(Node {
data: val,
next: self.head.take(),
});
其中take方法会将Option设置为None,并返回原先的值。
这几行代码新建了一个节点,还有将head滞空(赋值为None)。
将head指向新建节点,这步只需要将被some新建节点赋值给head即可。
self.head = Some(new_node)
因为self是&mut, 所以这里直接使用=就可以完成。
peek
peek方法返回Option<&T>
。
- 如果head是一个None,返回None
- 否则返回Some<&T>
你可能会想到match匹配。可以这样做。
pub fn peek(&self) -> Option<&T> {
match &self.head {
None => None,
Some(node) => Some(&node.data)
}
}
&具有最低的优先级,即&(self.head)
&self.head
是必要的。match不会消费对象,但是结构SomeSome(node)
会转移所有权。就会得到一个编译错误。那是因为我们移动一个已经被借用的值Box obj
。这个值已经被self借用了,你却要把它移动给node。
peek_mut
与peek相同,但是返回可变引用
pub fn peek_mut(&mut self) -> Option<&mut T> {
match &mut self.head {
None => None,
Some(node) => Some(& mut node.data)
}
}
同理的,match
应当匹配&mut self.head
。
pop
pop究竟该如何操作,我想你在学数据结构的时候都已经快听的耳朵起茧子了额。但是在这里,还是要复述一遍。
- 如果head为空,什么也不做,返回一个具有空语义的对象
- 获取头的next名为node
- 头指向node
- 返回node中的值/进行其他的操作
用Rust语言来描述,可以用match来匹配head是否为None,如果是返回None,如果不是,会匹配出原来的head叫做node,然后更新head,返回node中的数据即可。
我们可以改变以下实现手法,使用take方法,取得head的所有权。然后再重新赋值head。
pub fn pop(&mut self) -> Option<T> {
match self.head.take() {
None => None,
Some(node) => { //node 为原来的head
self.head = node.next; //node.next: Link<T> 变为新头
Some(node.data)
}
}
}
drop
我们可以不实现drop,用编译器为我们实现的——调用head的drop。于是drop Box中的对象,然后Box中的对象是一个Node,Node中又含有Link,这会是一个尾递归?不是的,编译器生成的drop会含有其他的操作。这不是一个尾递归。
我们需要手动的为LinkedList实现drop这个trait。具体的做法是
把递归改为迭代,每次获得一个节点的所有权,让后让其离开作用域自动drop,因为是一个循环,所以不会出现栈溢出这种情况。
impl <T> Drop for LinkedList<T> {
fn drop(&mut self) {
let mut curr = self.head.take(); //获得head的所有权
while let Some (node) = curr { //让node绑定的对象离开作用域自动drop
curr = node.next;
}
}
}
Iterator
为LinkedList提供迭代器。他们分别是Iter
,IntoIter
,IterMut
。其中Iter
,IterMut
需要额外注意生命周期。
IntoIter
IntoIter是最好实现的。因为其再迭代的时候会消耗容器,所以只需要每次pop以下就好了。
struct IntoIter<T> {
list: LinkedList<T>,
}
impl <T> Iterator for IntoIter<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
self.list.pop()
}
}
Iter
Iter就相对比较难一点,我们需要获取容器的不可变引用。并迭代。如何指向链表的下一个节点,是一个问题。
Iter中定义一个curr: Option<T>
,指向当前的节点,每次调用next,就返回curr的值,然后更新curr。
还是可以使用match来匹配。
pub struct Iter <'a, T> {
curr: Option<&'a Node<T>>,
}
impl <'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
match self.curr {
None => None,
Some(node) => {
self.curr = node.next.as_deref();
Some(&node.data)
}
}
}
}
由于self中的curr为Option包裹的引用类型,所以match匹配出来的值也是一个&类型,不用再额外添加引用。、
Some的部分值得拿出来好好说说。
Some(node) => {
self.curr = node.next.as_deref();
Some(&node.data)
}
先搞清楚类型,curr: Option<Node<T>>
,node.next: Option<Box<Node<T>>>
。我们直接使用 self.curr = node.next
来赋值,类型不对。Some(&Node) <- Some(Box<Node<T>>)
,要是给Box解引用就好了。使用as_deref
方法来返回一个解引用(被Some包裹的)。正好合适。
然后返回node中的data即可,别忘了添加&。
IterMut
IterMut又设计到了可变性。编码要考虑的因素就更多了。
老样子,我们对Iter使用的方法,故技重施看看。
pub struct IterMut<'a, T> {
curr: Option<&'a mut Node<T>>
}
impl <'a, T> Iterator for IterMut<'a, T> {
type Item = &'a mut T;
fn next(&mut self) -> Option<Self::Item> {
match self.curr {
None => None,
Some(node) => {
self.curr = node.next.as_deref_mut();
Some(&mut node.data)
}
}
}
}
会得到这样的编译错误。
error[E0507]: cannot move out of `self.curr.0` which is behind a mutable reference
--> src\first.rs:88:15
|
88 | match self.curr {
| ^^^^^^^^^ help: consider borrowing here: `&self.curr`
89 | None => None,
90 | Some(node) => {
| ----
| |
| data moved here
| move occurs because `node` has type `&mut Node<T>`, which does not implement the `Copy` trait
编译器说我们移动了以已经绑定可变引用的变量。
奇怪,为什么Iter可以而IterMut不可以呢?原因是不能对&mut & T
进行copy,就是没有实现Copy trait
,那怎么办?。那就又回到了peek的情况——移动了一个已经被借用的变量。只不过这个变量是一个可变引用&mut
。
按照编译器的方法改。你大可试试,会有更多的错误。换一种方法吧。
还是take方法。
pub struct IterMut<'a, T> {
curr: Option<&'a mut Node<T>>
}
impl <'a, T> Iterator for IterMut<'a, T> {
type Item = &'a mut T;
fn next(&mut self) -> Option<Self::Item> {
match self.curr.take() {
None => None,
Some(node) => {
self.curr = node.next.as_deref_mut();
Some(&mut node.data)
}
}
}
}
iter into_iter iter_mut
LinkedList的这三个方法如下定义。
pub fn iter(&self) -> Iter<T> {
Iter {
curr: self.head.as_deref(),
}
}
pub fn iter_mut(&mut self) -> IterMut<T> {
IterMut {
curr: self.head.as_deref_mut()
}
}
pub fn into_iter(self) -> IntoIter<T> {
IntoIter {
list: self
}
}
测试
fn main() {
let mut ls = LinkedList::new();
ls.push_front(12);
ls.push_front(14);
ls.push_front(100);
ls.push_front(222);
ls.pop();
assert_eq!(ls.peek(), Some(&100));
assert_eq!(ls.peek_mut(), Some(&mut 100));
for val in ls.iter() {
println!("{}",val);
}
for val in ls.iter_mut() {
*val = 1;
println!("{}",val);
}
for val in ls.into_iter() {
println!("{}",val);
}
}
很好的工作了起来!
再来看看数据量大的时候,会不会栈溢出。
fn main() {
let mut ls = LinkedList::new();
let n: usize = 10000000;
for i in 0..n {
ls.push_front(i);
}
}
很好,栈没有溢出。
总结
如果谁犯下了大罪。我一定让他试试在不看资料的情况下手写一个Option Box的链表。
玩笑归玩笑,好好的看清楚上面的实现,还是能对所有权和借用和声明周期的理解更上一层楼的。
对于peek,peek_mut等函数,你也可以使用map来实现,但是使用map会获得所所有权,又需要额外的处理。本文保留了match方法。
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgkkgib
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13