循环链表定义

Question

我正在尝试在 Rust 中创建一个循环链表定义，并提出了以下实现：

pub struct ListNode {
    pub val: i32,
    pub next: Option<Rc<RefCell<ListNode>>>,
}

impl ListNode {
    pub fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }

    pub fn for_each<F>(&self, f: F) -> ()
    where
        F: Fn(i32),
    {
        f(self.val);
        while let Some(next) = &self.next {
            f(next.borrow_mut().val);
        }
    }
}

问题是运行以下代码时出现紧急错误：

already borrowed: BorrowMutError

fn main() {
    let lst = Rc::new(RefCell::new(ListNode::new(10)));
    let mut ref_mt = lst.borrow_mut();
    ref_mt.next = Some(lst.clone());
    lst.clone().borrow_mut().for_each(|val| println!("{}", val))
}

有没有办法修复代码，使其与

RefCell

一起工作，或者

RefCell

本质上不适合这种情况？

Answer 1

在（安全）Rust 程序中，数据最多可以有一个可变引用，该引用由“所有权规则”控制并由“借用检查器”强制执行。用 Rc 包装类型不会改变 here 所讨论的情况，这也是使用

RefCell

的原因。它使用“内部可变性”来允许表面上看起来像多个可变引用。然而，正如here所讨论的，相同的规则适用，它们只是“动态”检查（即在运行时，而不是在编译时）。这就是你在这里遇到的问题。曾经有一个时间点违反了“别名 XOR 可变性”规则。让我们看看哪里出了问题。 首先，当尝试调用 ref_mt（可变借用 2）时，

for_each

仍在范围内（可变借用 1）。让我们通过显式删除

ref_mt

来解决这个问题。

let mut ref_mt = lst.borrow_mut();
ref_mt.next = Some(lst.clone());
drop(ref_mt);
lst.clone().borrow_mut().for_each(|val| println!("{}", val))

进行此更改后，至少会打印一次“10”。接下来，在尝试迭代时该节点仍保持借用状态，迭代本身将尝试借用同一节点。让我们通过避免不必要的借用来解决这个问题。

lst.clone().borrow().for_each(|val| println!("{}", val))

接下来，我们在无限迭代中遇到同样的问题。让我们以同样的方式解决这个问题。

f(next.borrow().val);

最后，循环开始工作，只要您允许，程序就会继续循环打印“10”。

修改后的代码完整版：

use std::{cell::RefCell, rc::Rc};

pub struct ListNode {
    pub val: i32,
    pub next: Option<Rc<RefCell<ListNode>>>,
}

impl ListNode {
    pub fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }

    pub fn for_each<F>(&self, f: F) -> ()
    where
        F: Fn(i32),
    {
        f(self.val);
        while let Some(next) = &self.next {
            f(next.borrow().val);
        }
    }
}

fn main() {
    let lst = Rc::new(RefCell::new(ListNode::new(10)));
    let mut ref_mt = lst.borrow_mut();
    ref_mt.next = Some(lst.clone());
    drop(ref_mt);
    lst.clone().borrow().for_each(|val| println!("{}", val))
}