0

我需要在树中找到具有最大值的节点，假设子节点的值总是大于拥有节点的值，然后修改它：

#[derive(Debug)]
struct Node {
    val: usize,
    nodes: Vec<Node>,
}

fn find_max(node: &mut Node, val: usize) -> Option<&mut Node> {
    if node.val < val {
        return None;
    }
    let mut max_val = node.val;
    let mut max: Option<&mut Node> = Some(node);
    for n in &mut node.nodes {
        if let Some(m) = find_max(n, max_val) {
            max_val = m.val;
            max = Some(m);
        }
    }
    max
}

fn main() {
    let mut root = Node {
        val: 1,
        nodes: vec![
            Node {
                val: 2,
                nodes: vec![],
            },
            Node {
                val: 3,
                nodes: vec![
                    Node {
                        val: 4,
                        nodes: vec![],
                    },
                ],
            },
        ],
    };
    println!("{:?}", find_max(&mut root, 0));
}

借用检查器返回此错误：

error[E0499]: cannot borrow `node.nodes` as mutable more than once at a time
  --> src/main.rs:13:19
   |
12 |     let mut max: Option<&mut Node> = Some(node);
   |                                           ---- first mutable borrow occurs here
13 |     for n in &mut node.nodes {
   |                   ^^^^^^^^^^ second mutable borrow occurs here
...
20 | }
   | - first borrow ends here

如果我从 中删除mut，find_max它可以工作，但我不知道如何从find_max.

重要的是它find_max本身不会修改任何东西。它只是搜索合适的节点。

4

3 回答 3

4

不需要使用unsafe：

fn find_max(node: &mut Node, val: usize) -> Option<&mut Node> {
    if node.val < val {
        return None;
    }

    if node.nodes.is_empty() {
        return Some(node);
    }

    let mut max_val = node.val;
    let mut max = None;
    for n in &mut node.nodes {
        if let Some(m) = find_max(n, max_val) {
            max_val = m.val;
            max = Some(m);
        }
    }
    max
}
于 2017-10-24T13:25:42.587 回答
0

这似乎unsafe是合理的罕见情况之一。

在这种情况下，通常的方法是用不可变引用替换可变引用并使用内部可变性。但在这种情况下，我们需要borrow() RefCell递归地 s 并以某种方式使它们即使在函数返回后仍保持活动状态。

考虑到问题不是由操作的固有不安全性引起的，而是由 Rust 借用检查器的限制引起的，使用unsafe. 请记住，虽然我有理由确定以下代码是安全的，但最好等待评论或其他解决方案。

fn find_max(node: &mut Node, val: usize) -> Option<&mut Node> {
    if node.val < val {
        return None;
    }
    let mut max = None;
    let mut max_val = node.val;
    // keep reference around as a pointer
    let node_ptr = node as *mut Node;
    // `{ node }` moves the reference instead of reborrowing it
    // so we can recreate it later with no risk of undefined behavior
    for n in &mut { node }.nodes {
        if let Some(m) = find_max(n, max_val) {
            max_val = m.val;
            max = Some(m);
        }
    }
    max.or_else(
        // the closure is executed only when `max == None`
        // and `node` was moved out earlier in `{node}`
        // therefore there's no active mutable references reachable thru recreated reference
        // function signature ensures that lifetime of the returned reference is ok
        // thus we can safely recreate the same mutable reference we received in `node`
        || unsafe { node_ptr.as_mut() }
    )
}
于 2017-10-24T11:49:53.203 回答
-2

U 可以使用 * 而不是 &mut 来取消引用。但 [Node]在编译时没有已知的常量大小

于 2017-10-24T09:36:51.300 回答