4

我正在尝试编写一个函数，该函数在给定树结构的情况下返回该树的副本，但在特定索引处更改了节点。这是我到目前为止所拥有的：

#[derive(Clone)]
pub enum Node {
    Value(u32),
    Branch(u32, Box<Node>, Box<Node>),
}

fn main() {
    let root = Node::Branch(1, Box::new(Node::Value(2)), Box::new(Node::Value(3)));
    zero_node(&root, 2);
}

pub fn zero_node (tree: &Node, node_index: u8) -> Node {

    let mut new_tree = tree.clone();

    fn zero_rec (node : &mut Node, node_count : u8, node_index : u8) -> u8 {
        if (node_index == node_count) {
            match node {
                &mut Node::Value(_) => { *node = Node::Value(0); },
                &mut Node::Branch(_, ref mut left, ref mut right) => { *node = Node::Branch(0, *left, *right);  }
            }
            node_count
        } else {
            match node {
                &mut Node::Value(val) => {1},
                &mut Node::Branch(_, ref mut left, ref mut right) => {
                    let count_left = zero_rec(&**left, node_count + 1, node_index);
                    let count_right = zero_rec(&**right, node_count + 1 + count_left, node_index);
                    count_left + count_right + 1
                }
            }
        }
    }

    zero_rec(&new_tree, 0, node_index);

    new_tree

}

http://is.gd/YdIm0g

我似乎无法摆脱错误，例如：“不能将不可变的借用内容作为可变借用”和“无法移出借用的内容”。

我可以在原始树的基础上从头开始创建新树，并在此过程中更改一个节点。但我想了解如何用借用检查器赢得这场战斗。

4

1 回答 1

10

此代码编译：

#[derive(Clone)]
pub enum Node {
    Value(u32),
    Branch(u32, Box<Node>, Box<Node>),
}

fn main() {
    let root = Node::Branch(1, Box::new(Node::Value(2)), Box::new(Node::Value(3)));
    zero_node(&root, 2);
}

pub fn zero_node (tree: &Node, node_index: u8) -> Node {

    let mut new_tree = tree.clone();

    fn zero_rec (node : &mut Node, node_count : u8, node_index : u8) -> u8 {
        if node_index == node_count {
            match node {
                &mut Node::Value(ref mut val) => { *val = 0; },
                &mut Node::Branch(ref mut val, _, _) => { *val = 0; }
            }
            node_count
        } else {
            match node {
                &mut Node::Value(_) => {1},
                &mut Node::Branch(_, ref mut left, ref mut right) => {
                    let count_left = zero_rec(&mut **left, node_count + 1, node_index);
                    let count_right = zero_rec(&mut **right, node_count + 1 + count_left, node_index);
                    count_left + count_right + 1
                }
            }
        }
    }

    zero_rec(&mut new_tree, 0, node_index);

    new_tree

}

我所做的更改是：

  • &new_tree→&mut new_tree和&**left→&mut **left等：创建&mut T引用的方式是使用&mut操作符（即mut是必要的）。cannot borrow immutable borrowed content as mutable这通过传递可变引用而不是不可变引用来修复错误
  • 更改node_index == node_count分支以直接改变值，而不是尝试就地覆盖。cannot move out of borrowed content这通过根本不做任何动作来修复错误。

实际上可以通过仔细使用std::mem::replace, 来实现覆盖，以将新值（例如Value(0)，因为创建起来很便宜）交换到leftandright引用。这些replace函数返回之前存在的值，即里面的东西left以及right创建新分支所需的值。对相关分支的这种更改match看起来有点像：

&mut Node::Branch(_, ref mut left, ref mut right) => { 
    let l = mem::replace(left, Box::new(Node::Value(0)));
    let r = mem::replace(right, Box::new(Node::Value(0)));
    *node = Node::Branch(0, l , r); 
}

（已添加use std::mem;到文件顶部。）

但是它遇到了一个新错误：

<anon>:25:9: 25:39 error: cannot assign to `*node` because it is borrowed
<anon>:25                   *node = Node::Branch(0, l , r); 
                            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
<anon>:22:26: 22:38 note: borrow of `*node` occurs here
<anon>:22               &mut Node::Branch(_, ref mut left, ref mut right) => { 
                                             ^~~~~~~~~~~~

left和right值是深入 的旧内容的指针，node因此，就编译器所知（目前），覆盖node将使那些指针无效，这将导致任何进一步使用它们的代码被破坏（当然，我们可以看到两者都没有更多地使用，但编译器还没有关注这样的事情）。幸运的是，有一个简单的解决方法：match双臂都设置node为新值，因此我们可以使用match来计算新值，然后node在计算后设置为它：

*node = match node {
    &mut Node::Value(_) => Node::Value(0),
    &mut Node::Branch(_, ref mut left, ref mut right) => { 
        let l = mem::replace(left, Box::new(Node::Value(0)));
        let r = mem::replace(right, Box::new(Node::Value(0)));
        Node::Branch(0, l , r)
    }
};

（注意，操作顺序有点奇怪，和let new_val = match node { ... }; *node = new_val;.）

但是，这比我上面写的要贵，因为它必须为 new 分配 2 个新框Branch，而就地修改的框不必这样做。

一个稍微“更好”的版本可能是（内联评论）：

#[derive(Clone, Show)]
pub enum Node {
    Value(u32),
    Branch(u32, Box<Node>, Box<Node>),
}

fn main() {
    let root = Node::Branch(1, Box::new(Node::Value(2)), Box::new(Node::Value(3)));
    let root = zero_node(root, 2);

    println!("{:?}", root);
}

// Taking `tree` by value (i.e. not by reference, &) possibly saves on
// `clone`s: the user of `zero_node can transfer ownership (with no
// deep cloning) if they no longer need their tree.
//
// Alternatively, it is more flexible for the caller if it takes 
// `&mut Node` and returns () as it avoids them having to be careful 
// to avoid moving out of borrowed data.
pub fn zero_node (mut tree: Node, node_index: u8) -> Node {

    fn zero_rec (node : &mut Node, node_count : u8, node_index : u8) -> u8 {
        if node_index == node_count {
            // dereferencing once avoids having to repeat &mut a lot
            match *node {
                // it is legal to match on multiple patterns, if they bind the same
                // names with the same types
                Node::Value(ref mut val) | 
                    Node::Branch(ref mut val, _, _) => { *val = 0; },
            }
            node_count
        } else {
            match *node {
                Node::Value(_) => 1,
                Node::Branch(_, ref mut left, ref mut right) => {
                    let count_left = zero_rec(&mut **left, node_count + 1, node_index);
                    let count_right = zero_rec(&mut **right, node_count + 1 + count_left, node_index);
                    count_left + count_right + 1
                }
            }
        }
    }

    zero_rec(&mut tree, 0, node_index);

    tree

}
于 2015-01-18T10:55:26.290 回答