检索对树值的可变引用

Question

披露：这是我的 Rust 编程的作业问题 class。我也很想 understand/learn 这个 material.

所以我有一个类似于下面的树（包含更改）：

struct Tree<V> {
  val: Option<V>,
  children: Vec<Tree<V>>
}

我的任务是从根开始搜索树并检索对 val 的可变引用。这是函数签名：

fn get_mut(&mut self, key: &str) -> Option<&mut V>

函数本身非常简单。我采用 self 参数并将其设置为 current_node 变量并进行搜索，直到找到正确的节点。我已经完成并测试了这部分（我可以看到它使用调试语句在树中搜索）。由于我通过了自己的可变版本，因此这是 current_node:

let mut current_node: &mut Tree<V> = self;

为了保留对 current_node 的可变引用，在搜索每个 tree/subtree 的子项时，我在 Vec 上使用 iter_mut():

for child in current_node.children.iter_mut() {
  ...
}

找到正确的节点后，我会从中提取值，然后 return:

let val_opt: Option<&mut V> = current_node.val.as_mut();
return match val_opt {
  Some(val) => {
    return Some(val)
  },
  None => None
}

但是，我在子循环中遇到错误：

cannot borrow `current_node.children` as mutable more than once at a time. mutable borrow starts here in previous iteration of loop.

let's call the lifetime of this reference `'1` (start of the function)

mutable borrow starts here in previous iteration of loop (child loop)

returning this value requires that `current_node.children` is borrowed for `'1` (on the line where I return Some(val) at the very end of the function)

我正在尝试了解为什么会发生这种情况以及如何克服它。从基本搜索来看，它似乎与生命周期有关，但我对如何补救它有些迷茫。此外，我无法更改 Tree<V> 结构或函数签名。

最少的实现：

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Tree<V> {
    val: Option<V>,
    children: Vec<(char, Tree<V>)>,
}

fn str_split_first(x: &str) -> Option<(char, &str)> {
    let mut chars = x.chars();
    let first = chars.next()?;
    Some((first, chars.as_str()))
}

impl<V> Tree<V> {
    pub fn get_mut(&mut self, key: &str) -> Option<&mut V> {
        let mut current_node: &mut Tree<V> = self;
        let mut key_index: usize = 0;

        loop {
            match str_split_first(&key[key_index..]) {
                Some((c, _)) => {
                    let mut found: bool = false;

                    'child_loop: for (character, child) in current_node.children.iter_mut() {
                        if c == *character {
                            current_node = child;
                            found = true;
                            break 'child_loop;
                        }
                    }

                    // If nothing was found, this key does not exist.
                    if found == false {
                        return None;
                    }

                    key_index += 1;
                }
                _ => break,
            }
        }

        let val_opt: Option<&mut V> = current_node.val.as_mut();
        return match val_opt {
            Some(val) => return Some(val),
            None => None,
        };
    }
}

Playground link

Answer 1

这里的问题是您在修改 current_node 的同时遍历它的子项。 Rust 编译器试图保护您免受迭代器失效，但在这种情况下这样做实际上是正确的，因为迭代在更改 current_node.

的值后立即停止

不幸的是，编译器还不够聪明，看不到它。一个简单的解决方法是在某个临时变量中存储一个新值并在循环外更新 current_node 。像这样：

let mut found = None;

for (character, child) in current_node.children.iter_mut() {
    if c == *character {
        found = Some(child);
        break;
    }
}

current_node = match found {
    Some(child) => child,
    None => return None,
};

Link to the playground

检索对树值的可变引用

Retrieve a mutable reference to a tree value

mutable

rust