首页 文章

“借来的 Value 不够长”，插入错误

提问于
浏览 次
2

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

struct Edge<'a> {
    ch: char,
    to: &'a Node<'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 的寿命不够长 .

我很确定我所写的内容远非惯用的Rust . 最初，当我在 Edge 中包含对 Node 的引用时，我没有添加生命周期参数，并且被提示这样做，然后我不得不在任何地方添加它 . 然而，它看起来很奇怪 . 我想知道这样做的正确方法是什么？

也许我真正应该使用的是 Edge 中的一些其他包装类型抽象来引用堆分配的 Node ，例如 Box ？我将仔细阅读Rust编程语言中关于该主题的部分 .

rust lifetime borrow-checker

1 回答

  • 2

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

    我认为返回值应该是对节点的引用：如果字符已经在其中一个边缘，那么我们直接返回现有节点;如果没有，我们返回新创建的节点 .

    代码不返回新创建的节点，它尝试返回对新创建的节点的引用 . 返回对对象的引用只有在对象存储在比引用更长的位置时才是安全的 . 否则，引用最终将指向堆栈中用于驻留的位置，从而导致使用时发生崩溃 . 像这样的错误经常是C和C崩溃的根源，而且正是Rust的借用检查器旨在防止的那种错误 .

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

    有几种可能的修复方法：

    • 将 Node 直接存储在 Edge 内 . 这是shown to compile .

    • 将 &Node 更改为 Rc<Node> . 这允许多个边缘共享单个节点的所有权，并自动释放 .

    在这两种情况下，将不再需要显式生命周期管理，并且所有权将为"just work" . 如果你知道C 11， Rc<> 大致相当于 std::shared_ptr .

    回复于

相关问题