编写二叉搜索树时,参数类型“T”的寿命可能不够长
The parameter type `T` may not live long enough when writing a binary searching tree
我正在尝试用 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
我知道这可以通过使用 Box
es 而不是引用来解决,但我想像这样练习。
如错误消息所述,可以通过添加生命周期限制来修复该特定错误 T: 'a
。但是你会得到许多其他错误,因为你正在尝试做的事情是不合理的:你正在尝试存储对其他地方没有所有者的对象的引用。
当你在你的节点中存储 &mut BST::<'a, T>::new()
时,BST::<'a, T>::new()
returns 一个很快就会被销毁的临时值,所以你不能存储对它的引用和期待它继续存在。
您需要您的节点拥有其子节点,而不是引用。您可以通过将子类型更改为 left: Box<BST<T>>
并在创建新子节点时使用 Box::new
来实现。一旦你这样做,你就可以摆脱所有的 'a
并且不会得到与生命周期相关的错误。
另一个问题是您的 add
使用了 self
参数,因此调用者将无法再使用它。您应该改为使用 &mut self
以便它可以修改调用者拥有的树。
我正在尝试用 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
我知道这可以通过使用 Box
es 而不是引用来解决,但我想像这样练习。
如错误消息所述,可以通过添加生命周期限制来修复该特定错误 T: 'a
。但是你会得到许多其他错误,因为你正在尝试做的事情是不合理的:你正在尝试存储对其他地方没有所有者的对象的引用。
当你在你的节点中存储 &mut BST::<'a, T>::new()
时,BST::<'a, T>::new()
returns 一个很快就会被销毁的临时值,所以你不能存储对它的引用和期待它继续存在。
您需要您的节点拥有其子节点,而不是引用。您可以通过将子类型更改为 left: Box<BST<T>>
并在创建新子节点时使用 Box::new
来实现。一旦你这样做,你就可以摆脱所有的 'a
并且不会得到与生命周期相关的错误。
另一个问题是您的 add
使用了 self
参数,因此调用者将无法再使用它。您应该改为使用 &mut self
以便它可以修改调用者拥有的树。