盒子与树——Rust 中的智能指针
最近，我尝试在 Rust 中实现一个二叉树数据结构。每棵二叉树都有一个根值、一个左子树和一个右子树。我从下面这个 Python 实现开始，它相当直观。
class Tree:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right这样我们就可以声明出一个漂亮的树对象：
t = Tree(15,
Tree(12,
None,
Tree(13)),
Tree(22,
Tree(18),
Tree(100)))结果还可以很漂亮地可视化出来。
（是的，这是我自己画的。）
把这段代码移植到 Rust，结果却有点……棘手。我的第一次尝试看起来相当无害。
struct Tree {
root: i64,
left: Tree,
right: Tree,
}这基本上是 Python 定义的一对一翻译——但 rustc 说不行。
error[E0072]: recursive type `Tree` has infinite size
--> src/main.rs:1:1
|
1 | struct Tree {
| ^^^^^^^^^^^ recursive type has infinite size
|
= help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `Tree` representable我之前接触的都是 Python、PHP 或 Ruby 这类内存管理语言，因此对此感到困惑。不过，这个问题其实很容易理解。计算机的内存容量是有限的。编译器的工作之一，就是弄清楚要为每个项目分配多少内存。
在这个例子中，它会推断出如下结果：
一棵树是一个包含一个 i64 和两棵树的结构体。这两棵树又分别是一个包含一个 i64 和两棵树的结构体。每一棵……
你明白我的意思了。
Tree { i64, Tree, Tree }
Tree { i64, Tree { ... }, Tree { ... } }
// The next expansion won't fit on the page anymore由于我们不知道一棵树会有多少棵子树，因此无法预先确定需要分配多少内存。只有在运行时才能知道！
Rust 告诉我们该如何修复：插入一个 indirection(间接层)，例如 Box、Rc 或 &。这些都是 Rust 中不同的“指针类型”。它们都指向内存中的某个位置。因此，我们不必知道整个树结构的总大小，只需要知道树所在内存中的位置。但这已经足以定义树结构了。这些指针类型让我们能够安全地做到这一点，而无需手动进行内存管理。它们各自提供不同的保证，你应该选择最符合自己需求的那一种。
&在 Rust 的术语中称为borrow(借用)。三者中它最为常见。它是对内存中某个位置的引用，但并不拥有它所指向的数据。因此，借用的生命周期取决于其所有者。所以这里还需要添加生命周期参数，这会让它用起来有些繁琐。struct Tree<'a> { root: i64, left: &'a Tree<'a>, right: &'a Tree<'a>, }Box是一种没有运行时开销的smart pointer(智能指针)。它拥有自己所指向的数据，并将数据存储在堆上。之所以称它为智能指针，是因为当它离开作用域时，会先丢弃它所指向的数据，然后再丢弃自身。无需手动进行内存管理，这一点很棒。✨struct Tree { root: i64, left: Box<Tree>, right: Box<Tree>, }Rc是另一种智能指针，它是“reference-counting(引用计数)”的缩写。它会在内部跟踪指向该数据结构的引用数量。一旦引用数量降为零，它就会自行清理。如果你需要让同一线程中的多个所有者共享同一份数据，就应该选择Rc。对于多线程场景，还有Arc（原子引用计数）。struct Tree { root: i64, left: Rc<Tree>, right: Rc<Tree>, }
把树装进盒子
这三个选项都完全有效。应该选择哪一个，取决于你的使用场景。一个经验法则是保持简单。就我而言，我选择使用 Box，因为我不需要任何特殊保证。
让子树变为可选
我遇到的下一个问题是，无法实例化树结构。左、右子树的类型都是 Box<Tree>，但在某些时候我需要一个空子树。
在 Python 示例中，我使用 None 表示数据结构的末端。借助 Rust 的 Option 类型，我们也可以做到这一点：
struct Tree {
root: i64,
left: Option<Box<Tree>>,
right: Option<Box<Tree>>,
}完成这些之后，我们就可以创建第一棵树了：
Tree {
root: 15,
left: Some(Box::new(Tree {
root: 12,
left: None,
right: Some(Box::new(Tree {
root: 13,
left: None,
right: None,
})),
})),
right: Some(Box::new(Tree {
root: 22,
left: Some(Box::new(Tree {
root: 18,
left: None,
right: None,
})),
right: Some(Box::new(Tree {
root: 100,
left: None,
right: None,
})),
})),
};从不同角度来看，你可能会说这要么很冗长，要么很明确。与 Python 版本相比，按我的口味，它看起来有点过于杂乱了。
能不能做得更好？Chris McDonald（克里斯·麦克唐纳）帮我想出了下面这种表示方式：
Tree::new(15)
.left(
Tree::new(12)
.right(Tree::new(13))
)
.right(
Tree::new(22)
.left(Tree::new(18))
.right(Tree::new(100))
);在我看来，这样看起来舒服多了。
下面是让这种写法成为可能的完整树实现：
#[derive(Default)]
struct Tree {
root: i64,
left: Option<Box<Tree>>,
right: Option<Box<Tree>>,
}
impl Tree {
fn new(root: i64) -> Tree {
Tree {
root: root,
..Default::default()
}
}
fn left(mut self, leaf: Tree) -> Self {
self.left = Some(Box::new(leaf));
self
}
fn right(mut self, leaf: Tree) -> Self {
self.right = Some(Box::new(leaf));
self
}
}更新：Danny Grein（丹尼·格林）在 Twitter 上提到，只要实现 From<i64> for Tree，我们就可以支持下面这种语法：
root(15)
.left(
root(12)
.right(13)
)
.right(
root(22)
.left(18)
.right(100)
);为什么在 Python 中直接就能运行？
现在你可能会想，为什么我们的树实现在 Python 中能够如此顺利地工作。原因在于，Python 会在运行时为树对象动态分配内存。此外，它还会把所有内容封装在 PyObject 中，这在某种程度上类似于上面的 Rc——一种引用计数的智能指针。
Rust 在这里更加明确。它让我们能够更灵活地表达自己的需求，但我们也需要了解所有可能的替代方案，才能善加利用。我的建议是：如果一个简单的借用就能满足需求，那就不要使用智能指针。
不过，如果生命周期造成了阻碍，或者你需要线程安全之类的额外保证，那么智能指针会是工具箱中的绝佳补充。Rust documentation（《Rust 文档》）是了解智能指针的一个很好的起点。另外，如果你的树需要在运行时可变，也可以阅读“Idiomatic tree and graph-like structures in Rust”（《Rust 中惯用的树与类图结构》），其中介绍了一些巧妙使用分配器的方法。