将借入值添加到基于RefCell构建的二叉树时，借用值的存留时间不够长 [英] Borrowed value does not live long enough when adding to a binary tree built on RefCell

问题描述

我尝试在二叉树中实现add操作：

use std::cell::RefCell;
use std::cmp::PartialOrd;

type Link<T> = RefCell<Option<Box<Node<T>>>>;

struct Node<T> {
    key: T,
    left: Link<T>,
    right: Link<T>,
}

struct Tree<T> {
    root: Link<T>,
}

impl<T> Node<T> {
    fn new(val: T) -> Self {
        Node {
            key: val,
            left: RefCell::new(None),
            right: RefCell::new(None),
        }
    }
}

impl<T: PartialOrd> Tree<T> {
    fn new() -> Self {
        Tree {
            root: RefCell::new(None),
        }
    }

    fn add(&self, val: T) {
        let mut next = self.root.borrow();
        let node = Box::new(Node::new(val));
        match next.as_ref() {
            None => {
                self.root.replace(Some(node));
                ()
            }
            Some(root_ref) => {
                let mut prev = root_ref;
                let mut cur: Option<&Box<Node<T>>> = Some(root_ref);
                while let Some(node_ref) = cur {
                    prev = node_ref;
                    if node.key < node_ref.key {
                        next = node_ref.left.borrow();
                    } else {
                        next = node_ref.right.borrow();
                    }
                    cur = next.as_ref();
                }
                if node.key < prev.key {
                    prev.left.replace(Some(node));
                } else {
                    prev.right.replace(Some(node));
                }
            }
        }
    }
}

fn main() {}

我不明白为什么next变量的生命期不够长：

error[E0597]: `next` does not live long enough
  --> src/main.rs:36:15
   |
36 |         match next.as_ref() {
   |               ^^^^ borrowed value does not live long enough
...
60 |     }
   |     - `next` dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created

error[E0597]: `next` does not live long enough
  --> src/main.rs:51:27
   |
51 |                     cur = next.as_ref();
   |                           ^^^^ borrowed value does not live long enough
...
60 |     }
   |     - `next` dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created

next存在于add函数的整个作用域中，在next删除之前，包含对它的引用的其他变量已被删除。

编译器说"values in a scope are dropped in the opposite order they are created"，这表明还有另一种方法来声明变量并解决这个问题，但我不知道怎么做。

推荐答案

我看到的问题是，为了更新树的叶节点，您必须持有对每个中间步骤的引用，而不仅仅是它的父步骤，因为在更新值时，到根节点的所有链接都必须保持活动状态。而铁锈的寿命根本不能做到这一点。

也就是说，Rust不能在循环中做到这一点，但它可以在递归函数中做到这一点，而树最好用递归函数来实现。

自然，您的递归结构是Node，而不是Tree，但这样的结构可以工作(有许多方法可以使借入工作)：

impl<T: PartialOrd> Node<T> {
    fn add(&self, val: T) {
        let mut branch = if val < self.key {
            self.left.borrow_mut()
        } else {
            self.right.borrow_mut()
        };
        if let Some(next) = &*branch {
            next.add(val);
            return;
        }
        //Separated from the if let so that branch is not borrowed.
        *branch = Some(Box::new(Node::new(val)));
    }
}

然后，在impl Tree中，只需将工作转发到此工作。

如果像其他人指出的那样，去掉TreevsNode和RefCell...

，代码可能会简化一点

这篇关于将借入值添加到基于RefCell构建的二叉树时，借用值的存留时间不够长的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！