让我们在Rust中使用RefCell结构实现一个简单的Tree数据结构。特别是,我们将编写traverse()方法来收集树中包含的所有项。
代码如下:
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
pub struct TreeNode {
pub val: i32,
pub left: Option<Rc<RefCell<TreeNode>>>,
pub right: Option<Rc<RefCell<TreeNode>>>,
}
pub fn traverse(root: &Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
let mut result = Vec::new();
let mut queue = VecDeque::new();
queue.push_back(root.as_ref());
while let Some(opt) = queue.pop_front() {
if let Some(node) = opt {
let borrowed = node.borrow();
result.push(borrowed.val);
queue.push_back(borrowed.left.as_ref());
queue.push_back(borrowed.right.as_ref());
}
}
result
}
下面是编译器的报错:
error[E0597]: `borrowed` does not live long enough
--> src/lib.rs:19:29
|
17 | let borrowed = node.borrow();
| -------- binding `borrowed` declared here
18 | result.push(borrowed.val);
19 | queue.push_back(borrowed.left.as_ref());
| ^^^^^^^^ borrowed value does not live long enough
20 | queue.push_back(borrowed.right.as_ref());
21 | }
| -
| |
| `borrowed` dropped here while still borrowed
| borrow might be used here, when `borrowed` is dropped and runs the destructor for type `Ref<'_, TreeNode>`
为了理解错误消息,记录一下与编译器错误相关的变量类型:
queue: VecDeque<Option<&Rc<RefCell<TreeNode>>>>
opt: Option<&Rc<RefCell<TreeNode>>>
node: &Rc<RefCell<TreeNode>>
borrowed: Ref<TreeNode>
了解了这些类型之后,让我们来检查一下错误消息。编译器抱怨借用的变量生命周期不够长,在第21行被drop了。根源在于node,注意,node变量的类型是&Rc<RefCell<TreeNode>>,这是Rc<…>的借用。这种类型没有多大意义- Rc<…>是一个引用计数智能指针,其目的是允许多个指针/引用其内容。换句话说,我们通常希望Rc::clone()它而不是创建它的引用,因为它本身已经是引用了。这意味着我们实际上希望node变量的类型是Rc<RefCell<TreeNode>>。
好,那我们怎么修改代码呢?查看我们的类型,我们观察到&Rc<…>类型源自队列变量,当前类型为VecDeque<Option<&Rc<RefCell<TreeNode>>>>。我们需要修复它的类型为VecDeque<Option<Rc<RefCell<TreeNode>>>>在Rc前面去掉&引用。要做到这一点,当我们将Option<&Rc<…>>压入队列时,可以调用map()函数并调用Rc::clone()转换为另一个指针实例。
pub fn traverse(root: &Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
let mut result = Vec::new();
let mut queue = VecDeque::new();
// queue.push_back(root.as_ref());
queue.push_back(root.as_ref().map(|rc| Rc::clone(rc)));
while let Some(opt) = queue.pop_front() {
if let Some(node) = opt {
let borrowed = node.borrow();
result.push(borrowed.val);
// 堆代码 duidaima.com
// queue.push_back(borrowed.left.as_ref());
// queue.push_back(borrowed.right.as_ref());
queue.push_back(borrowed.left.as_ref().map(|rc| Rc::clone(rc)));
queue.push_back(borrowed.right.as_ref().map(|rc| Rc::clone(rc)));
}
}
result
}
注意,为了克隆Rc,必须使用Rc::clone(Rc)而不是Rc .clone()来调用它。修复后,以下是变量的新类型:
queue: VecDeque<Option<Rc<RefCell<TreeNode>>>>
opt: Option<Rc<RefCell<TreeNode>>>
node: Rc<RefCell<TreeNode>>
borrowed: Ref<TreeNode>
编译器不再报错!虽然我们修复了编译器错误,但这个修复似乎使我们的代码变得有点冗长。有更简单的方法吗?本质上,我们要做的是取&Option<T>并返回Option<T>,其中包含的值是克隆的,在我们的例子中T = Rc<…>。Option实现了Clone特性,因此提供了Clone()方法,因此,一个更简单的解决方案如下:
pub fn traverse(root: &Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
let mut result = Vec::new();
let mut queue = VecDeque::new();
// queue.push_back(root.as_ref());
// queue.push_back(root.as_ref().map(|rc| Rc::clone(rc)));
queue.push_back(root.clone());
while let Some(opt) = queue.pop_front() {
if let Some(node) = opt {
let borrowed = node.borrow();
result.push(borrowed.val);
// queue.push_back(borrowed.left.as_ref());
// queue.push_back(borrowed.right.as_ref());
// queue.push_back(borrowed.left.as_ref().map(|rc| Rc::clone(rc)));
// queue.push_back(borrowed.right.as_ref().map(|rc| Rc::clone(rc)));
queue.push_back(borrowed.left.clone());
queue.push_back(borrowed.right.clone());
}
}
result
}