编写二进制搜索树时，参数类型"T"的寿命可能不够长 [英] The parameter type `T` may not live long enough when writing a binary searching tree

问题描述

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

I'm trying to write a binary searching tree in Rust, but I don't understand what is going on:

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() {
}

当我尝试对此进行编译时，出现以下错误:

When I try to compile this, I get the following errors:

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> }
  |                         ^^^^^^^^^^^^^^^^^^^^^^^^

好吧，经过大量研究并完成了编译器建议的工作后，我想到了以下代码:

Well, after doing lots of research and doing the things that the compiler suggests I came up with this code:

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() {
}

但是我仍然会收到错误:

But I still get errors:

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而不是引用来解决此问题，但我想像这样进行练习.

I know this can be fixed by using Boxes instead of references, but I want to make it like this for exercise.

推荐答案

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

As the error message says, that specific error can be fixed by adding a lifetime bound T: 'a. But then you'll get many other errors, because what you are trying to do is unsound: You are trying to store references to objects which don't have an owner elsewhere.

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

When you do something like storing &mut BST::<'a, T>::new() in your node, BST::<'a, T>::new() returns a temporary value which will soon be destroyed, so you can't store a reference to it and expect it to live on.

您需要节点来拥有其子代，而不是引用.您可以通过将子类型更改为left: Box<BST<T>>并在创建新的子节点时使用Box::new来实现.完成此操作后，您就可以摆脱所有地方的所有'a，并且不会遇到与生命周期相关的错误.

Instead of references, you need your node to own its children. You can do this by changing the child type to left: Box<BST<T>> and using Box::new when you create a new child node. Once you do this, you can get rid of all the 'a everywhere and won't get the lifetime-related errors.

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

Another issue is that your add consumes the self parameter so it won't be able to be used anymore by the caller. You should make it take &mut self instead so that it can modify the tree owned by the caller.

这篇关于编写二进制搜索树时，参数类型"T"的寿命可能不够长的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！