深度优先树搜索期间的多个可变借用

Question

如何重构这个进行深度优先搜索并返回匹配节点的父节点的函数？

\n\n

我知道这个问题的变体经常出现（例如，在 Rust 中使用递归函数生成树结构时，多个可变借用，Mut 借用未在预期的位置结束），但我仍然可以 \xe2\x80\x99t 弄清楚如何修改它以使其工作。我尝试过使用切片、std::mem::drop和添加生命周期参数的变体where \'a: \'b，但我仍然没有\xe2\x80\x99t 弄清楚编写它而不需要有条件地可变地借用一个分支中的变量，然后在另一个分支中使用该变量。

\n\n

#[derive(Clone, Debug)]\nstruct TreeNode {\n    id: i32,\n    children: Vec<TreeNode>,\n}\n\n// Returns a mutable reference to the parent of the node that matches the given id.\nfn find_parent_mut<\'a>(root: &\'a mut TreeNode, id: i32) -> Option<&\'a mut TreeNode> {\n    for child in root.children.iter_mut() {\n        if child.id == id {\n            return Some(root);\n        } else {\n            let descendent_result = find_parent_mut(child, id);\n            if descendent_result.is_some() {\n                return descendent_result;\n            }\n        }\n    }\n    None\n}\n\nfn main() {\n    let mut tree = TreeNode {\n        id: 1,\n        children: vec![TreeNode {\n                           id: 2,\n                           children: vec![TreeNode {\n                                              id: 3,\n                                              children: vec![],\n                                          }],\n                       }],\n    };\n    let a: Option<&mut TreeNode> = find_parent_mut(&mut tree, 3);\n    assert_eq!(a.unwrap().id, 2);\n}\n

\n\n

#[derive(Clone, Debug)]\nstruct TreeNode {\n    id: i32,\n    children: Vec<TreeNode>,\n}\n\n// Returns a mutable reference to the parent of the node that matches the given id.\nfn find_parent_mut<\'a>(root: &\'a mut TreeNode, id: i32) -> Option<&\'a mut TreeNode> {\n    for child in root.children.iter_mut() {\n        if child.id == id {\n            return Some(root);\n        } else {\n            let descendent_result = find_parent_mut(child, id);\n            if descendent_result.is_some() {\n                return descendent_result;\n            }\n        }\n    }\n    None\n}\n\nfn main() {\n    let mut tree = TreeNode {\n        id: 1,\n        children: vec![TreeNode {\n                           id: 2,\n                           children: vec![TreeNode {\n                                              id: 3,\n                                              children: vec![],\n                                          }],\n                       }],\n    };\n    let a: Option<&mut TreeNode> = find_parent_mut(&mut tree, 3);\n    assert_eq!(a.unwrap().id, 2);\n}\n

\n\n

这是 @huon\xe2\x80\x99s 建议和持续的编译器错误：

\n\n

fn find_parent_mut<\'a>(root: &\'a mut TreeNode, id: i32) -> Option<&\'a mut TreeNode> {\n    for child in root.children {\n        if child.id == id {\n            return Some(root);\n        }\n    }\n    for i in 0..root.children.len() {\n        let child: &\'a mut TreeNode = &mut root.children[i];\n        let descendent_result = find_parent_mut(child, id);\n        if descendent_result.is_some() {\n            return descendent_result;\n        }\n    }\n    None\n}\n

\n\n

error[E0499]: cannot borrow `*root` as mutable more than once at a time\n  --> src/main.rs:11:25\n   |\n9  |     for child in root.children.iter_mut() {\n   |                  ------------- first mutable borrow occurs here\n10 |         if child.id == id {\n11 |             return Some(root);\n   |                         ^^^^ second mutable borrow occurs here\n...\n20 | }\n   | - first borrow ends here\n

\n

Answer 1

我设法让它以这种方式工作：

fn find_parent_mut<'a>(root: &'a mut TreeNode, id: i32)
        -> Option<&'a mut TreeNode> {
    if root.children.iter().any(|child| {child.id == id}) {
        return Some(root); 
    }
    for child in &mut root.children {
        match find_parent_mut(child, id) {
            Some(result) => return Some(result),
            None => {}
        }
    }
    None
}

首先，在第二次尝试中，您编写了for child in root.children而不是for child in &mut root.children（注意缺少&mut），这导致 root.children 被循环消耗而不是仅仅迭代，因此出现错误cannot move out of borrowed content。

我还使用该函数以更迭代器丰富的方式折叠它any(..)。

对于第二个循环，我不太确定发生了什么，显然将引用绑定到变量使借用检查器感到困惑。我删除了所有临时变量，现在它可以编译了。