rust - 如何在 Option 中访问 T 而不会导致移动？

Question

我正在研究二叉搜索树实现中的插入函数。这是我的代码:

pub struct Node {
    data: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>
}

fn insert_at_root(mut root_node: Node, new_node: Node) -> Node { //not reference because root_node will be mutated
    if root_node.data > new_node.data { // value less than root
        if let Some(left) = root_node.left {
            insert_node(*left, new_node); // *left is a way to downcast box, i.e. *left = T from Box<T>
        }
        else {
            root_node.set_left(Some(Box::new(new_node)));
        }
    }
    else if root_node.data < new_node.data {
        if let Some(right) = root_node.right {
            insert_node(*right, new_node);
        }
        else {
            root_node.set_right(Some(Box::new(new_node)));
        }
    }
    root_node
}

fn insert_node(mut exist_node: Node, new_node: Node) -> () {
    if exist_node.data > new_node.data {
        if let Some(left) = exist_node.left {
            insert_node(*left, new_node);
        }
        else {
            exist_node.set_left(Some(Box::new(new_node)));
        }
    }
    else if exist_node.data < new_node.data {
        if let Some(right) = exist_node.right {
            insert_node(*right, new_node);
        }
        else {
            exist_node.set_right(Some(Box::new(new_node)));
        }
    }
}

我有两个插入函数，因此当我调用 insert_at_node 时，我可以将变量与根节点一起保存。

我目前的问题是行 if let Some(left) = root_node.left { (和行 if let Some(right) = root_node.right { )在 insert_at_root显然会导致移动的功能。结果无法返回 root_node在 insert_at_node 结尾:

error[E0382]: use of moved value: `root_node`
  --> src/lib.rs:34:5
   |
19 |         if let Some(left) = root_node.left {
   |                     ---- value moved here
...
34 |     root_node
   |     ^^^^^^^^^ value used here after partial move
   |
   = note: move occurs because value has type `std::boxed::Box<Node>`, which does not implement the `Copy` trait

error: aborting due to previous error

这些行的目的是检查 left (或 right )子节点不是 None , 基本上 root_node.left != None .
有什么方法可以在不引起移动的情况下实现这一目标？也许有 !=或 ==符号。

Answer 1

你的问题不在于你测试是否left/right是 Some或 None .顺便说一句，可以通过测试来完成 .is_some()和 .is_none() .

您遇到的问题是您绑定(bind)了变量 left到Node那是在Option .这样您就可以移动 Option 内容的所有权。到left多变的。

通常，如果您不想移动所有权，则必须使用引用。当变量在 Option 中时并且您需要查看它作为引用，您必须将它的类型从 Option<T> 转换至Option<&T> .当您查看选项时，它只是一个引用，因此不会移动所有权。
Option 上有两个功能可用进行此转换:.as_ref()转换为不可变引用，.as_mut()转换为可变引用。因为要修改left的内容你需要一个可变引用，所以 .as_mut()如你所愿。

通过使用 .as_mut() left你得到的是一个引用而不是变量本身，所以没有所有权被转移。

您遇到的下一个问题是您无法将引用传递给 insert_node。因为这个函数的类型签名需要获取变量而不是引用。那样的话，它需要你在这个辅助函数中传递所有权，所以它也不起作用。所以我们转换insert_node的签名采取&mut Box<Node>而不是 Node .因此，我们再次仅获取引用而不是所有权。

pub fn insert_at_root(mut root_node: Node, new_node: Node) -> Node {
    //not reference because root_node will be mutated
    if root_node.data > new_node.data {
        // value less than root
        if let Some(left) = root_node.left.as_mut() {
            insert_node(&mut *left, new_node);
        } else {
            root_node.set_left(Some(Box::new(new_node)));
        }
    } else if root_node.data < new_node.data {
        if let Some(right) = root_node.right.as_mut() {
            insert_node(&mut *right, new_node);
        } else {
            root_node.set_right(Some(Box::new(new_node)));
        }
    }
    root_node
}

pub fn insert_node(exist_node: &mut Box<Node>, new_node: Node) -> () {
    if exist_node.data > new_node.data {
        if let Some(left) = exist_node.left.as_mut() {
            insert_node(&mut *left, new_node);
        } else {
            exist_node.set_left(Some(Box::new(new_node)));
        }
    } else if exist_node.data < new_node.data {
        if let Some(right) = exist_node.right.as_mut() {
            insert_node(&mut *right, new_node);
        } else {
            exist_node.set_right(Some(Box::new(new_node)));
        }
    }
}