rust - 无法从匹配臂返回对成员的可变引用

Question

作为 rust 借用和生命周期的练习，我想实现一个简单的二叉树。但是，我被困在了一些事情上。考虑一下:

struct Node {
    key: i32,
    value: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

struct BinaryTree {
     root: Option<Box<Node>>,
}

impl BinaryTree {

    fn find_mut(&mut self, key: i32) -> &mut Option<Box<Node>> {
        let mut node = &mut self.root;
        loop {
            match node {
                Some(box_node) if box_node.key != key => {
                    node = if box_node.key < key {
                        &mut box_node.right
                    } else {
                        &mut box_node.left
                    }
                },
                other => return other
            }
        }
    }
}

以上无法编译:

error[E0505]: cannot move out of `node` because it is borrowed
  --> src/main.rs:40:17
   |
29 |     fn find_mut(&mut self, key: i32) -> &mut Option<Box<Node>> {
   |                 - let's call the lifetime of this reference `'1`
...
33 |                 Some(box_node) if box_node.key != key => {
   |                      -------- borrow of `node.0` occurs here
...
40 |                 other => return other
   |                 ^^^^^           ----- returning this value requires that `node.0` is borrowed for `'1`
   |                 |
   |                 move out of `node` occurs here

我尝试显式设置 self 的生命周期和输出。我还尝试扩展 Some(_) None 的 ARM 和火柴而不是 other也是。
(编辑 2): find_mut 的目的是向应该创建新节点的对象(以防找不到键)或现有节点所在的对象返回一个引用。
更详细的编译错误的原因是什么？我该怎么去修复它？我正在尝试做的甚至是一个好的做法，(编辑 1)，即返回 ref 到 Optional 的修改应该在哪里(假设这不是公共(public)方法)？

Answer 1

Rust 编译器出现错误的原因是因为 Some(expr)模式匹配整个表达式以其拥有的形式，即 expr被移动。
通常，这很容易通过匹配表达式作为借用 Some(ref expr) 来解决。 , 或可变借用 Some(ref mut expr) ，但这里不是这样。
如果您查看标准库，您会经常看到 as_mut()/as_ref() , 当值可能不存在时，总是返回 Option<&mut T>而不是 &mut Option<T> .那是因为你真的想访问这个值，而不是数据结构的任何内部结构，它的结构类似于 Option<Box<None>>是。
在那之后，我想出了这个:

struct Node {
    key: i32,
    value: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

struct BinaryTree {
     root: Option<Box<Node>>,
}

impl BinaryTree {
    fn find_mut(&mut self, key: i32) -> Option<&mut Node> {
        // &mut Option<Box<Node>> -> Option<&mut Box<Node>> -> Option<&mut Node>
        let mut node = self.root.as_mut().map(|boxed| boxed.as_mut());
        loop {
            match node {
                Some(box_node) if box_node.key != key => {
                    node = if box_node.key < key {
                        box_node.right.as_mut().map(|boxed| boxed.as_mut())
                    } else {
                        box_node.left.as_mut().map(|boxed| boxed.as_mut())
                    }
                },
                other => return other
            }
        }
    }
}

可能有更好的方法来写这个，但我现在不知道。
请注意，这解决了所有权问题，因为现在 &mut Node是移到这里的内容，同时使 API 变得更好。
至于其是否良好的做法，鉴于其双重含义，是与否。
它可以帮助您学习如何处理借款；另一方面，我们已经有了 Vec::binary_search , 和 BTreeMap / BTreeSet ，并且很可能在 crates.io 上除了最极端的情况外，还有其他实现应该涵盖所有情况，并且自己制作搜索树没有什么意义。