与Rust编译器的斗争- 2

让我们想象一下用Rust编写一个简单的链表。具体来说，让我们实现push_front()方法，它在链表的头部插入一个元素。

代码如下：

struct Node<T> {
    val: T,
    next: Option<Box<Node<T>>>,
}

struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
}

impl<T> LinkedList<T> {
    fn push_front(&mut self, val: T) {
        self.head = Some(Box::new(Node{val, next: self.head}))
    }
}

我们用给定的值创建一个新节点，用当前head值赋值给它的next字段，然后设置self.head为新节点的head。很漂亮，除了Rust编译器会抱怨：

error[E0507]: cannot move out of `self.head` which is behind a mutable reference
  --> <source>:12:51
   |
12 |         self.head = Some(Box::new(Node{val, next: self.head}))
   |                                                   ^^^^^^^^^ move occurs because `self.head` has type `Option<Box<Node<T>>>`, which does not implement the `Copy` trait

error: aborting due to previous error

For more information about this error, try `rustc --explain E0507`.
Compiler returned: 1

你也可以在编译器资源管理器中自己尝试一下。让我们深入了解一下编译器为什么会报错，根本原因有两个方面：

1，在可变引用&mut self之后，我们不能移动self.head值，就像编译器说的那样。这是因为如果我们移动self.head给其他变量，那么self.head进行drop之后就成为无效的，这样self也变成无效的了

2，Rust编译器还没有那么聪明。在代码中我们移动self.head到新的node中，然后我们立即给self.head赋一个新的有效值“self.head = Some(Box::new(Node{…}))”，不幸的是，编译器不能分析那么远。它只能分析一步，self.head被移出，这是不允许的。

解决的办法是确保self.head总是有效的。也就是说，如果我们要移走它的值，那么我们需要同时为它提供一个新值——不是字面上的，而是逻辑上的。这是通过std::mem:: replace()或std::mem::swap()函数完成的。在本例中，我们需要使用std::mem::replace()。

pub fn replace<T>(dest: &mut T, src: T) -> T

所以，我们的解决方案如下：

impl<T> LinkedList<T> {
    fn push_front(&mut self, val: T) {
        // self.head = Some(Box::new(Node{val, next: self.head}));
        let head = std::mem::replace(&mut self.head, None);
        self.head = Some(Box::new(Node{val, next: head}))
    }
}

我们替换self.head为一个虚拟值，本例为None，并将其先前的值保存在一个局部变量head中。然后我们创建一个指向head的新节点，并设置self.head指向新节点。这是一个通用的解决方案，同时也有一个特定的Option类型的方法：Option::take()也是按上面的方式这样做的。因为我们的head变量是Option<…>类型，所以我们也可以像下面这样简化代码：

impl<T> LinkedList<T> {
    fn push_front(&mut self, val: T) {
        // self.head = Some(Box::new(Node{val, next: self.head}));
        self.head = Some(Box::new(Node{val, next: self.head.take()}));
    }
}

现在留一个作业，尝试实现pop_front()方法，它应该具有如下所示的签名。

fn pop_front(&mut self) -> Option<T>

• 如果头节点为空，则返回None
• 否则更新head以指向第二个节点并返回第一个值