在编写二叉搜索树时，参数类型"T"的生存时间可能不够长

Question

我正在尝试在 Rust 中编写一个二叉搜索树，但我不明白发生了什么：

enum BST<'a, T: Ord> {
Leaf,
BinTree { value: T, left: &'a mut BST<'a, T>, right: &'a mut BST<'a, T> }
}
impl<'a, T: Ord> BST<'a, T> {
fn new() -> BST<'a, T> {
BST::Leaf
}
fn add(self, val: T) {
match self {
BST::Leaf => self = BST::BinTree {
value: val,
left: &mut BST::<'a, T>::new(),
right: &mut BST::<'a, T>::new()
},
BST::BinTree{value: v, left: l, right: r} => if val < v {
l.add(val);
} else {
r.add(val);
}
}
}
}
fn main() {
}

当我尝试编译它时，我收到以下错误：

error[E0309]: the parameter type `T` may not live long enough
--> heap.rs:3:25
|
3 |     BinTree { value: T, left: &'a mut BST<'a, T>, right: &'a mut BST<'a, T> }
|                         ^^^^^^^^^^^^^^^^^^^^^^^^
|
= help: consider adding an explicit lifetime bound `T: 'a`...
note: ...so that the reference type `&'a mut BST<'a, T>` does not outlive the data it points at
--> heap.rs:3:25
|
3 |     BinTree { value: T, left: &'a mut BST<'a, T>, right: &'a mut BST<'a, T> }
|                         ^^^^^^^^^^^^^^^^^^^^^^^^

好吧，在做了大量的研究并做了编译器建议的事情之后，我想出了这段代码：

enum BST<'a, T: Ord + 'a> {
Leaf,
BinTree { 
value: T,
left: &'a mut BST<'a, T>,
right: &'a mut BST<'a, T>
}
}
impl<'a, T: Ord + 'a > BST<'a, T> {
fn new() -> BST<'a, T> {
BST::Leaf
}
fn add(&mut self, val: T) {
match *self {
BST::Leaf => *self = BST::BinTree {
value: val,
left: &mut BST::<'a, T>::new() as &'a mut BST<'a, T>,
right: &mut BST::<'a, T>::new() as &'a mut BST<'a, T>
},
BST::BinTree{value: ref v, left: ref mut l, right: ref mut r} => if val < *v {
l.add(val);
} else {
r.add(val);
}
}
}
}
fn main() {
}

但我仍然收到错误：

error: borrowed value does not live long enough
--> heap.rs:19:16
|
19 |                left: &mut BST::<'a, T>::new() as &'a mut BST<'a, T>,
|                           ^^^^^^^^^^^^^^^^^^^ does not live long enough
20 |                right: &mut BST::<'a, T>::new() as &'a mut BST<'a, T>
21 |            },
|            - temporary value only lives until here
|
note: borrowed value must be valid for the lifetime 'a as defined on the body at 15:27...
--> heap.rs:15:28
|
15 |    fn add(&mut self, val: T) {
|  ____________________________^
16 | |      match *self {
17 | |          BST::Leaf => *self = BST::BinTree {
18 | |              value: val,
...  |
27 | |      }
28 | |  }
| |__^
error: borrowed value does not live long enough
--> heap.rs:20:17
|
20 |                right: &mut BST::<'a, T>::new() as &'a mut BST<'a, T>
|                            ^^^^^^^^^^^^^^^^^^^ does not live long enough
21 |            },
|            - temporary value only lives until here
|
note: borrowed value must be valid for the lifetime 'a as defined on the body at 15:27...
--> heap.rs:15:28
|
15 |    fn add(&mut self, val: T) {
|  ____________________________^
16 | |      match *self {
17 | |          BST::Leaf => *self = BST::BinTree {
18 | |              value: val,
...  |
27 | |      }
28 | |  }
| |__^
error: aborting due to 2 previous errors

我知道这可以通过使用Boxes 而不是引用来解决，但我想让它像这样进行练习。

Answer 1

正如错误消息所说，可以通过添加生命周期绑定T: 'a来修复该特定错误。但是，您会收到许多其他错误，因为您尝试执行的操作是不合理的：您正在尝试存储对在其他地方没有所有者的对象的引用。

当您执行诸如在节点中存储&mut BST::<'a, T>::new()之类的操作时，BST::<'a, T>::new()返回一个临时值，该值将很快被销毁，因此您无法存储对它的引用并期望它继续存在。

您需要节点拥有其子节点，而不是引用。为此，可以将子类型更改为left: Box<BST<T>>，并在创建新的子节点时使用Box::new。完成此操作后，您可以摆脱所有'a无处不在，并且不会获得与生命周期相关的错误。

另一个问题是您的add使用self参数，因此调用方将无法再使用它。您应该改为采用&mut self，以便它可以修改调用方拥有的树。