我创建了一个树，其类型定义类似于：
#[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结构体实现的章节。
有了这些知识，我的计划是更新上面的例子。我的想法是，我可以用Rc<RefCell<..>>替换Box<...>。我的想法是，这些类型非常相似，因为它们都存储了对某个数据结构的引用，唯一的区别是，可以有多个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<_>>还有什么不太理解的地方？
2条答案
按热度按时间68bkxrlz1#
所以，你有一些问题，主要的一个问题是，你试图引用一个
Option，这个Option包含一个值，这个值的生存期很短，因为它绑定到RefCell上的borrow()。（您还尝试在borrow就位时执行borrow_mut，这会引起混乱。）谢天谢地，Rc使获取对Rc的引用的所有权变得便宜且容易（这就是全部要点），所以这个问题可以通过存储Option而不是&Option来解决，我们使用Option::as_ref将&Option<Rc<_>>转换为Option<&Rc<_>>，然后通过将Rc::cloneMap到Option<&Rc<_>>上将其转换为Option<Rc<_>>。vcirk6k62#
虽然原始答案是正确的，但是示例中的代码不起作用，因为它忘记添加根节点。
有两种方法可以解决这个问题：
递归解：