Rust难点笔记 2. 链表

yyi
yyi
2024-02-24 / 0 评论 / 50 阅读 / 正在检测是否收录...

为一个基础数据结构开一个新篇?链表这么有牌面么?

今天在Leetcode随机到了跳表,于是我准备学习下Rust链表先。

乍一看链表应该不难啊,值得放进难点?

看一下course.rs:

image-20240224120148694

人家开了一整章,好吧,我们知道Rust不允许悬垂指针,那我们的链表可咋整,且听我慢慢来学

1 实现链表

从简单的定义开始

pub enum List {
    Empty,
    Elem(i32, List),
}

当尝试build这个的时候,会出现

image-20240224122425791

当前这个类型并不是定长的,Rust编译器认为栈上类型必须有固定长度,因此,我们按照提示,把List通过Box封装到堆上,栈上只留下一个定长的指针。

更改为box封装后,我们的链表过编了,但是这还有点问题,一点都不优雅

[] = Stack
() = Heap

[Elem A, ptr] -> (Elem B, ptr) -> (Empty, *junk*)

链表头并不是一个指针,而是一个栈上元素,而后面的尾节点却在堆上,而我们期望的(显然,你应该已经了解C的链表了)

[head] -> (val A, ptr) -> (val B, null)

是这样的链表

这是有意义的,前者在分割、合并链表的时候,都会有Copy到栈上、Copy到堆里的操作,但是后者只需要动动指针,也和我们最初的期望保持一致。

由此,我们的定义改版为如下:

struct Node {
    elem: i32,
    next: List,
}

pub enum List {
    Empty,
    More(Box<Node>),
}

在叙述中,这种enum会遵循Rust的编译器优化,More中包含了一个非0指针,而Empty是无数据的(More、Empty都是自定义的,叫啥都行),在这种情况下不会产生enum_tag的开销,即Rust不需要记住具体是哪种tag,非0就是More,为0就是Empty

image-20240224124141126

还有一点小问题,封装的可见性。材料里报的是error,我本地报的warning,但是不管哪种,我们都希望尽可能符合最小暴露原则,所以定义改为如下:

pub struct List {
    head: Link,
}

enum Link {
    Empty,
    More(Box<Node>),
}

struct Node {
    elem: i32,
    next: Link,
}

接下来,我们为这个链表加上操作

impl List {
    pub fn new() -> Self {
        List { head: Link::Empty }
    }
    pub fn push(&mut self, elem: i32) { 
        // 在链表头插入数据
    }
}

push会改变链表,所以需要一个可变借用,我们新建一个Node,然后把她的next指向旧head,把head指向他

    pub fn push(&mut self, elem: i32) {
        let new_node = Box::new(Node {
            elem: elem,
            next: self.head,
        });

        self.head = Link::More(new_node);
    }

看起来很美好,但是估计没有这么简单

image-20240224124719067

Link没有实现Copy,我们也不能简单粗暴的实现一个Clone,如果直接赋值,会导致Link的所有权被移走,head悬垂了

我们用一个不太优雅的小trick:mem::replace,在从head中偷出值的同时塞回去一个新值

变成这样:

pub fn push(&mut self, elem: i32) {
    let new_node = Box::new(Node {
        elem: elem,
        next: std::mem::replace(&mut self.head, Link::Empty),
    });

    self.head = Link::More(new_node);
}

好吧,看着奇奇怪怪,在逻辑中引入了一些不逻辑的东西,但是我们没有什么办法了

接着实现Pop,在弹出的同时返回一个Option

pub fn pop(&mut self) -> Option<i32> {
    match &self.head {
        Link::Empty => {
            None;
        }
        Link::More(node) => {
            self.head = node.next;
            Some(node.elem)
        }
    }
}

不需要编译,都能猜到肯定 self.head = node.next;有点问题,这里又产生move了

我本来想说,那就不给大家演示了,结果一编译发现还有个问题

image-20240224125412468

两个愿望,一次满足:

pub fn pop(&mut self) -> Option<i32> {
    match std::mem::replace(&mut self.head, Link::Empty) {
        Link::Empty => None,
        Link::More(node) => {
            self.head = node.next;
            Some(node.elem)
        }
    }
}

把head变成empty,同时换到node里,但是和push一样使用了一点trick

链表的释放

rust为绝大多数类型实现了drop,并且如果结构的每个字段都有drop,也会自动为结构实现drop

但是材料给了一种问题情况:

#[test]
fn long_list() {
    let mut list = List::new();
    for i in 0..100000 {
        list.push(i);
    }
    drop(list);
}

虽然这看上去是一个尾递归(递归发生在尾部,应当复用栈帧),但是在rust实现里并非如此

impl Drop for List {
    fn drop(&mut self) {
        // NOTE: 在 Rust 代码中,我们不能显式的调用 `drop` 方法,只能调用 std::mem::drop 函数
        // 这里只是在模拟编译器!
        self.head.drop(); // 尾递归 - good!
    }
}

impl Drop for Link {
    fn drop(&mut self) {
        match *self {
            Link::Empty => {} // Done!
            Link::More(ref mut boxed_node) => {
                boxed_node.drop(); // 尾递归 - good!
            }
        }
    }
}

impl Drop for Box<Node> {
    fn drop(&mut self) {
        self.ptr.drop(); // 糟糕,这里不是尾递归!
        deallocate(self.ptr); // 不是尾递归的原因是在 `drop` 后,还有额外的操作
    }
}

impl Drop for Node {
    fn drop(&mut self) {
        self.next.drop();
    }
}

对于Box\<Node>来说,编译器的行为并不是尾递归,会爆栈

材料给出一种方法

impl Drop for List {
    fn drop(&mut self) {
        let mut cur_link = mem::replace(&mut self.head, Link::Empty);
        while let Link::More(mut boxed_node) = cur_link {
            cur_link = mem::replace(&mut boxed_node.next, Link::Empty);
        }
    }
}

手动的换出每个节点,然后在while结束的时候就drop了


优化类型定义和代码复杂度

刚刚的代码中,除了replace很怪,还有一大坨的类型声明也很怪,毕竟我们C的链表声明一个结构体就够了

有一个很显然的优化是enum Link和Option十分的类似

pub struct List {
    head: Link,
}
type Link = Option<Box<Node>>;
struct Node {
    elem: i32,
    next: Link,
}

Option提供了一个take函数,让我们不需要那个冗长的replace

pub fn push(&mut self, elem: i32) {
        let new_node = Box::new(Node {
            elem: elem,
            next: self.head.take(),
        });

        self.head = Some(new_node);
    }

Option让我们的match可以变为map

pub fn pop(&mut self) -> Option<i32> {
    self.head.take().map(|node| {
        self.head = node.next;
        node.elem
    })
}

加入泛型

我们会在签名处加入 <T\>,这样这个链表即时就支持泛型了

pub struct List<T> {
    head: Link<T>,
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None }
    }

    pub fn push(&mut self, elem: T) {
        let new_node = Box::new(Node {
            elem: elem,
            next: self.head.take(),
        });

        self.head = Some(new_node);
    }

    pub fn pop(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next;
            node.elem
        })
    }
}

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut cur_link = self.head.take();
        while let Some(mut boxed_node) = cur_link {
            cur_link = boxed_node.next.take();
        }
    }
}
0

评论 (0)

取消