rust - 修改 HashMap 对象中的特定值，以防以后可以移动其对象的所有权

Question

我正在实现深度优先搜索。

它的数据结构是用HashMap实现的，如“当前节点”->“下一个节点”。

为了避免循环图中的循环，我的程序在标记时尝试从 HashMap 的值(Vec of next depth Vertices)中删除一个节点。

当通过 get_mut 操作 HashMap 对象的值时，我注意到它的整个 HashMap 对象的所有权以后不能移动。

#[derive(Debug, PartialEq, Eq, Hash, Copy, Clone)]
pub enum Vertex<A> {
    Start,
    Goal,
    Vertex(A),
}

pub fn search(
    curr: &Vertex<i32>,
    mut acc: Vec<Vertex<i32>>,
    mut field: HashMap<Vertex<i32>, Vec<Vertex<i32>>>,
    goal: &Vertex<i32>,
) -> Vec<Vertex<i32>> {
    match field.get_mut(&curr) {
        // when reached goal
        _ if *curr == *goal => {
            acc.push(*curr);
            acc
        }

        // when vertices found
        Some(ns) => {
            if let Some(next) = ns.pop() {
                // go to next depth
                acc.push(*curr);
                // trying to move "field"'s ownership to next recursive call here but it fails because "field.get_mut(&curr)" is done at match expression
                search(&next, acc, field, goal)
            } else if let Some(prev) = acc.pop() {
                // backtrack
                search(&prev, acc, field, goal) // ditto
            } else {
                // no answer
                vec![]
            }
        }

        // when next is not registered
        None => vec![],
    }
}

如评论中所写，递归调用中存在非法移动。

因此我在编译时收到以下消息。

18 |     let result: Vec<Vertex<i32>> = match field.get_mut(&curr) {  
   |                                          ----- borrow of `field` occurs here  
...  
29 |                 _search(&next, acc, field, goal) // to be fixed  
   |                                     ^^^^^ move out of `field` occurs here  

error[E0505]: cannot move out of `field` because it is borrowed  
  --> src/algorithm/search/graph/depth_first.rs:31:37  
   |  
18 |     let result: Vec<Vertex<i32>> = match field.get_mut(&curr) {  
   |                                          ----- borrow of `field` occurs here  
...  
31 |                 _search(&prev, acc, field, goal) // to be fixed  
   |                                     ^^^^^ move out of `field` occurs here  

您能否提出解决此问题或重新设计整个代码的好方法？

Answer 1

您的代码编译为稳定的 Rust 2018(或带有 #![feature(nll​​)] 的 nightly Rust 2015)。

要使其在稳定的 Rust 2015 上运行，您可以将递归调用移到借用 field 的范围之外。一种方法如下:

pub fn _search(
    curr: &Vertex<i32>,
    mut acc: Vec<Vertex<i32>>,
    mut field: HashMap<Vertex<i32>, Vec<Vertex<i32>>>,
    goal: &Vertex<i32>,
) -> Vec<Vertex<i32>> {
    let v = match field.get_mut(&curr) {
        // when reached goal
        _ if *curr == *goal => {
            acc.push(*curr);
            return acc;
        }

        // when vertices found
        Some(ns) => {
            if let Some(next) = ns.pop() {
                // go to next depth
                acc.push(*curr);
                next
            } else if let Some(prev) = acc.pop() {
                // backtrack
                prev // ditto
            } else {
                // no answer
                return vec![];
            }
        }

        // when next is not registered
        None => return vec![],
    };
    _search(&v, acc, field, goal)
}