理解 Rust `Rc<RefCell<_>>`

Question

我正在尝试创建类型定义类似于

的树

#[derive(Debug, Clone)]
pub(crate) struct TreeBox<T> {
    root: Option<Box<NodeBox<T>>>,
}

#[derive(Debug, Clone)]
struct NodeBox<T> {
    value: T,
    left: Option<Box<NodeBox<T>>>,
    right: Option<Box<NodeBox<T>>>,
}

有插入功能

impl<T: Ord> TreeBox<T> {
    fn new() -> Self {
        Self { root: None }
    }

    pub fn insert(&mut self, value: T) -> bool {
        let mut node = &mut self.root;

        while let Option::Some(current_node) = node {
            match current_node.value.cmp(&value) {
                Ordering::Less => node = &mut current_node.right,
                Ordering::Equal => return false,
                Ordering::Greater => node = &mut current_node.left,
            }
        }

        *node = Option::Some(Box::new(NodeBox {
            value,
            left: Option::None,
            right: Option::None,
        }));

        return true;
    }
}

这非常有效，我对实施非常满意。但是我想将每个节点的引用存储到它的父节点。经过一些研究，我发现这个 article 描述了使用 RefCell 和 Weak 结构的实现。

有了这些知识，我的计划是更新上面的示例。我的想法是，我可以将 Box<...> 替换为 Rc<RefCell<..>>。我的想法是这些类型非常相似，因为它们都存储对某些数据结构的引用，唯一的区别是可以有多个 Rc<RefCell<..>> 指向该数据结构。我将实施更改为

#[derive(Debug, Clone)]
pub(crate) struct Tree<T> {
    root: Option<Rc<RefCell<Node<T>>>>,
}

#[derive(Debug, Clone)]
struct Node<T> {
    value: T,
    left: Option<Rc<RefCell<Node<T>>>>,
    right: Option<Rc<RefCell<Node<T>>>>,
}

impl<T: Ord> Tree<T> {
    fn new() -> Self {
        Self { root: None }
    }

    pub fn insert(&mut self, value: T) -> bool {
        let mut node = &mut self.root;

        while let Option::Some(current_node) = node {
            let cmp = current_node.borrow().value.cmp(&value);
            match cmp {
                Ordering::Less => node = &mut current_node.borrow_mut().right,
                Ordering::Equal => return false,
                Ordering::Greater => node = &mut current_node.borrow_mut().left,
            };
        }

        *node = Option::Some(Rc::new(RefCell::new(Node {
            value,
            left: Option::None,
            right: Option::None,
        })));

        return true;
    }
}

然而，这个更新的例子没有运行，说

error[E0716]: temporary value dropped while borrowed
  --> src/lib.rs:28:47
   |
28 |                 Ordering::Less => node = &mut current_node.borrow_mut().right,
   |                                               ^^^^^^^^^^^^^^^^^^^^^^^^^     -
   |                                               |                             |
   |                                               |                             temporary value is freed at the end of this statement
   |                                               |                             ... and the borrow might be used here, when that temporary is dropped and runs the destructor for type `RefMut<'_, Node<T>>`
   |                                               creates a temporary which is freed while still in use
   |                                               a temporary with access to the borrow is created here ...
   |
   = note: consider using a `let` binding to create a longer lived value

我的例子是不是错了，或者我对生锈还有什么不太了解的地方Rc<RefCell<_>>？

A link 到操场上面的例子：https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=9929b2118e2430f03035da4c65a4cf2f

Answer 1

所以，你有一些问题。第一个是您试图引用一个 Option，它包含一个生命周期很短的值，因为它与 RefCell 上的 borrow() 相关联。（你也在尝试 borrow_mut 而 borrow 就位，这会引起恐慌。）幸运的是， Rc 使得获取对 [=16= 的引用的所有权变得便宜且容易]（这就是重点），所以这个问题可以通过存储 Option 而不是 &Option 并自由克隆所包含的 Rc 来解决。我们使用 Option::as_ref 将 &Option<Rc<_>> 转换为 Option<&Rc<_>>，然后通过在其上映射 Rc::clone 将其转换为 Option<Rc<_>>。

pub fn insert(&mut self, value: T) -> bool {
    let mut node = self.root.as_ref().map(Rc::clone);

    while let Some(current_node) = node {
        let current_node = current_node.borrow();
        let cmp = current_node.value.cmp(&value);
        let new_node = match cmp {
            Ordering::Less => &current_node.left,
            Ordering::Equal => return false,
            Ordering::Greater => &current_node.right,
        };
        node = new_node.as_ref().map(Rc::clone);
    }

    let node = &mut node;
    *node = Some(Rc::new(RefCell::new(Node {
        value,
        left: None,
        right: None,
    })));

    true
}

理解 Rust `Rc<RefCell<_>>`

Understanding Rust `Rc<RefCell<_>>`

tree

rust

refcell