rust - "borrowed value does not live long enough"trie插入错误

Question

我有一个简单的 trie 实现，其中 Edge 包含一个字符和对另一个 Node 的引用:

struct Edge<'a> {
    ch: char,
    to: &'a Node<'a>,
}

一个节点包含一个边向量:

pub struct Node<'a> {
    edges: Vec<Edge<'a>>,
}

我正在尝试实现将字符插入/获取节点的方法。我认为返回值应该是一个Node的引用:如果字符已经在其中一条边上，那么我们直接返回已有的Node；如果不是，我们返回新创建的 Node。这就是我遇到麻烦的地方:

impl<'a> Node<'a> {
    fn get_or_create(&mut self, ch: char) -> &Node<'a> {
        match self.edges.binary_search_by(|e| e.ch.cmp(&ch)) {
            Ok(idx) => {
                return &self.edges.get(idx).unwrap().to;
            }
            Err(idx) => {
                let to = &Node { edges: Vec::new() };
                let e = Edge { ch: ch, to: to };
                self.edges.insert(idx, e);
                return to;
            }
        }
    }
}

据说 to 的生命周期不够长。

我很确定我写的远非惯用的 Rust。最初当我在 Edge 中包含对 Node 的引用时，我没有添加 lifetime 参数，系统提示我这样做，然后我不得不在所有地方添加它。然而，它看起来很奇怪。我想知道这样做的正确方法是什么？

也许我真正应该使用的是 Edge 中的一些其他包装器类型抽象来引用堆分配的 Node，例如框？我将仔细阅读 The Rust Programming Language 中有关此主题的部分。

Answer 1

此数据结构无法按设计工作。红旗是下面这句话:

I think the return value should be a reference to a Node: if the character is already in one of the edges, then we directly return the existing Node; if not, we return the newly created Node.

代码不返回新创建的节点，它试图返回一个引用 给新创建的节点。返回对象的引用只有在对象存储在比引用更有效的地方时才是安全的。否则，引用最终会指向对象曾经驻留的堆栈位置，从而导致使用时崩溃。像这样的错误是 C 和 C++ 中常见的崩溃根源，而 Rust 的借用检查器正是为了防止这种错误而设计的。

Rust 使用函数和数据的生命周期参数来跟踪引用生命周期。为了证明引用不会比对象长寿，Rust 禁止引用的生命周期超过对象的生命周期。由于新节点在函数末尾被删除并且引用从函数返回，对象的生命周期太短，代码被正确拒绝为无效。

有几种可能的修复方法:

• 存储Node直接在里面Edge .这是 shown to compile .

• 更改 &Node至 Rc<Node> .这允许多个边缘共享单个节点的所有权，并自动解除分配。

在这两种情况下，不再需要明确的生命周期管理，所有权将“正常工作”。如果你了解 C++11，一个 Rc<>大致相当于 std::shared_ptr .