我创建了一个树,其类型定义类似于:
#[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
and Weak
结构。
有了这些知识,我的计划是更新上面的示例。我的想法是我可以替代Box<...>
with 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<_>>
?