Trie 插入"borrowed value does not live long enough"错误

Question

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

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

a Node包含一个边的向量：

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的寿命不够长。

我很确定我写的东西远非惯用生锈。最初，当我在Edge中包括对Node的引用时，我没有添加寿命参数，并提示这样做，然后我必须到处添加它。但是看起来很奇怪。我想知道正确的方法是什么？

也许我真正使用的是Edge中的其他包装器类型抽象，以参考堆分配的Node，例如。Box？我将仔细阅读有关此主题的部分。

Answer 1

此数据结构无法按设计工作。红旗是以下句子：

我认为返回值应该是对Node的引用：如果字符已经在一个边缘中，则直接返回现有的Node；如果没有，我们返回新创建的Node。

代码未返回新创建的节点，它试图将A 参考返回到新创建的节点。仅当对象存储在将其超过参考的地方时，返回对象的引用才安全。否则，引用最终将指向对象用于驻留的堆栈上的位置，从而导致使用时崩溃。像这样的错误是C和C 的经常出现的崩溃来源，正是Rust借用检查器旨在预防的错误。

Rust在功能和数据上使用寿命参数跟踪参考寿命。为了证明参考不会超过对象，Rust禁止参考的寿命超出对象的寿命。由于新节点在功能末尾删除，并且从函数返回引用，因此对象的寿命太短，并且代码正确拒绝为无效。

有几个可能的修复：

• 直接将Node存储在Edge中。显示了这是编译的。

• 将&Node更改为Rc<Node>。这允许单个节点的共享所有权以多个边缘和自动DealLocation。

在这两种情况下，明确的终身管理将不再是必要的，所有权将"仅仅工作"。如果您知道C 11，则Rc<>大致相当于std::shared_ptr。