如何处理将基于Box的树结构改为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;
    }
}

这个实现十分完美，我对此非常满意。但是我想要每个节点都能存储一个指向其父节点的引用。经过一些研究，我发现Rust Book中的一节描述了使用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

这两个例子都可以在playground找到。

我的示例是错误的，还是我对于Rc<RefCell<_>>仍有些不太理解？

- cl_um

Answer 1

所以，您有一些问题。主要问题是您正在尝试获取对包含值的Option的引用，其生命周期很短，因为它与RefCell上的borrow()相关联。（您还尝试在存在borrow的情况下borrow_mut，这将导致恐慌。）幸运的是，Rc使得获取对Rc的引用变得简单和便宜（这就是整个目的），因此可以通过存储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
}

- BallpointBen

---

如果代码实际上并没有起作用，那么这怎么能成为被接受的答案呢？ - Danilo Souza Morães

map(clone) -> cloned(). - Chayim Friedman

@DaniloSouzaMorães 这种情况时有发生。请点个踩然后继续前进。 - Chayim Friedman

Answer 2

虽然原始答案是正确的，但示例中的代码不起作用，因为它忘记添加根节点。

以下是解决此问题的两个替代方案：

    pub fn insert(&mut self, value: T) -> bool {
        //if no root, just create one
        let mut node = if let Some(root) = &self.root {
            Rc::clone(root)
        } else {
            self.root = Some(Rc::new(RefCell::new(Node {
                value,
                left: None,
                right: None,
            })));
            return true;
        };

        loop {
            let current_node = Rc::clone(&node);
            let mut current_node = RefCell::borrow_mut(&current_node);
            let cmp = current_node.value.cmp(&value);
            let next_node = match cmp {
                Ordering::Less => &mut current_node.left,
                Ordering::Equal => return false,
                Ordering::Greater => &mut current_node.right,
            };
            if let Some(next_node) = next_node {
                node = Rc::clone(next_node);
            } else {
                *next_node = Some(Rc::new(RefCell::new(Node {
                    value,
                    left: None,
                    right: None,
                })));

                println!("node: {:?}", node);
                return true;
            }
        }
    }

递归解决方案：

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

    pub fn insert(&mut self, value: T) -> bool {
        //if no root, just create one
        if let Some(root) = &self.root {
            let mut root = RefCell::borrow_mut(&root);
            root.insert(value)
        } else {
            self.root = Some(Rc::new(RefCell::new(Node {
                value,
                left: None,
                right: None,
            })));
            true
        }
    }
}

impl<T: Ord + fmt::Debug> Node<T> {
    fn insert(&mut self, value: T) -> bool {
        let node = match self.value.cmp(&value) {
            Ordering::Less => &mut self.left,
            Ordering::Equal => return false,
            Ordering::Greater => &mut self.right,
        };
        //if the node is empty, add to it, otherwise check deeper
        if let Some(node) = node {
            let mut node = RefCell::borrow_mut(node);
            node.insert(value)
        } else {
            *node = Some(Rc::new(RefCell::new(Node {
                value,
                left: None,
                right: None,
            })));
            println!("node: {:?}", node);
            true
        }
    }
}

- Rubens Brandão