Rust中删除单链表中的节点（两种实现

Question

我有两个删除功能的实现。 方法 1 不起作用，因为编译器说

curr

是借用的。

while let Some(boxed_node) = curr

和

match curr

有什么区别？

方法1

    fn delete_method_1(&mut self, val : i32) {
        let mut curr = &mut self.head;

        while let Some(boxed_node) = curr {
            if boxed_node.val == val {
                *curr = boxed_node.next.take(); // it does not work
            } else {
                curr = &mut boxed_node.next
            }
        }
    }

方法1的错误信息

while let Some(boxed_node) = curr {
   |                        ---------- `*curr` is borrowed here
26 |             if boxed_node.val == val {
27 |                 *curr = boxed_node.next.take(); // it does not work
   |                 ^^^^^
   |                 |
   |                 `*curr` is assigned to here but it was already borrowed
   |                 borrow later used here

方法2

  fn delete_method_2(&mut self, val : i32) {
        let mut curr = &mut self.head;
        loop {
            match curr {
                None => return,
                Some(boxed_node) if boxed_node.val == val => {
                    *curr = boxed_node.next.take();
                },
                Some(boxed_node) => {
                    curr = &mut boxed_node.next;
                }
            }
        }
    }

我预计方法1有效。

Answer 1

这实际上并不是

while let

和

match

之间的区别。如果您将第二个方法编写得与第一个方法完全相同，它将如下所示：

fn delete_method_2(&mut self, val: i32) {
    let mut curr = &mut self.head;

    loop {
        match curr {
            None => return,
            Some(boxed_node) => {
                if boxed_node.val == val {
                    *curr = boxed_node.next.take();
                } else {
                    curr = &mut boxed_node.next;
                }
            }
        }
    }
}

你会得到完全相同的错误。

实际发生的事情有点微妙。首先，比赛人体工程学会自动为您取消引用比赛监督员。实际发生了什么 是这样的：

fn delete_method_2(&mut self, val: i32) {
    let mut curr = &mut self.head;

    loop {
        //    v Rust inserts this dereference...
        match *curr {
            None => return,
            //   vvvvvvv and this borrow automatically
            Some(ref mut boxed_node) => {
                if boxed_node.val == val {
                    *curr = boxed_node.next.take();
                } else {
                    curr = &mut boxed_node.next;
                }

            }
        }
    }
}

while let

版本看起来几乎一样。这里的问题是，

curr = &mut boxed_node.next

行强制在

boxed_node

的生命周期内借用

curr

。使用虚假的生命周期注释：

fn delete_method_2(&mut self, val: i32) {
    let mut curr = &'curr mut self.head;

    loop {
        match *curr {
            None => return,
            Some(ref 'curr mut boxed_node) => {
                if boxed_node.val == val {
                    *curr = boxed_node.next.take();
                } else {
                    //            we force the compiler to match this lifetime
                    //      vvvvv exactly
                    curr = &'curr mut boxed_node.next;
                }

            }
        }
    }
}

因此，因为

boxed_node

必须借用给

'curr

，所以我们不允许在同一范围内分配给

*curr

。借用检查器（还）无法确定两个分支需要借用

boxed_node

以获得不同的生命周期。

但是，当您将案例分成两个不同的匹配臂时，编译器可以计算出在每种情况下借用

boxed_node

的适当生命周期：

fn delete_method_2(&mut self, val: i32) {
    let mut curr = &'curr mut self.head;

    loop {
        match *curr {
            None => return,
            Some(ref '_ mut boxed_node) if boxed_node.val == val => {
                *curr = boxed_node.next.take();
            }
            Some(ref 'curr mut boxed_node) => {
                curr = &'curr mut boxed_node.next;
            }
        }
    }
}

在第一种情况下，编译器只需要在

boxed_node

调用期间借用

take

，之后

curr

不再被视为借用，我们可以重新分配它。

在第二种情况下，编译器可以在

boxed_node

生命周期内借用

'curr

。

该解释中可能存在无数技术错误，但从大局来看，我认为这就是正在发生的事情。