Rust难点笔记 2. 链表

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

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

乍一看链表应该不难啊，值得放进难点？

看一下course.rs:

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

1 实现链表

从简单的定义开始

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

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

当前这个类型并不是定长的，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

还有一点小问题，封装的可见性。材料里报的是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);
    }

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

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了

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

两个愿望，一次满足：

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();
        }
    }
}