與 Rust 編譯器的鬥爭 - 3
讓我們在 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>，這是 Rc<…> 的借用。這種類型沒有多大意義 - Rc<…> 是一個引用計數智能指針，其目的是允許多個指針 / 引用其內容。換句話說，我們通常希望 Rc::clone() 它而不是創建它的引用，因爲它本身已經是引用了。這意味着我們實際上希望 node 變量的類型是 Rc<RefCell>。
好，那我們怎麼修改代碼呢？查看我們的類型，我們觀察到 & Rc<…> 類型源自隊列變量，當前類型爲 VecDeque<Option<&Rc<RefCell>>>。我們需要修復它的類型爲 VecDeque<Option<Rc<RefCell>>> 在 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);
// 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 並返回 Option，其中包含的值是克隆的，在我們的例子中 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
}本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/qBHMfMaMkXyTxb-R6hJsDg