Trie：一次不能多次借用 _ 可变的

Question

我想为 Trie 实现一些基本方法。

use std::collections::HashMap;

#[derive(Debug)]
struct TrieNode {
    chs: HashMap<char, TrieNode>,
    value: Option<i32>,
}

#[derive(Debug)]
struct Trie {
    root: TrieNode,
}

impl Trie {
    fn new() -> Trie {
        Trie {
            root: TrieNode {
                chs: HashMap::new(),
                value: None,
            },
        }
    }

    fn add_string(&mut self, string: String, value: i32) {
        let mut current_node = &mut self.root;
        for c in string.chars() {
            current_node = current_node.chs.entry(c).or_insert(TrieNode {
                chs: HashMap::new(),
                value: None,
            });
        }
        current_node.value = Some(value);
    }

    fn delete(&mut self, key: &String) -> Option<i32> {
        if key.is_empty() {
            // if key is empty, no need to delete
            return None;
        }
        let mut current_node = &mut self.root;
        for (ind, ch) in key.chars().enumerate() {
            match current_node.chs.get_mut(&ch) {
                Some(node) => {
                    if ind < key.len() - 1 {
                        current_node = node;
                    }
                }
                None => return None,
            }
        }
        // here current_node is actually the previous node of the deleted node
        let temp = current_node.chs.remove(&key.chars().last().unwrap());
        match temp {
            Some(node) => node.value,
            None => None,
        }
    }
}

方法delete是删除一个键（从一个Trie）和returns那个键对应的值。但是，我收到以下错误。

error[E0499]: cannot borrow `current_node.chs` as mutable more than once at a time
   --> src/main.rs:118:19
    |
118 |             match current_node.chs.get_mut(&ch) {
    |                   ^^^^^^^^^^^^^^^^ mutable borrow starts here in previous iteration of loop

Answer 1

正如错误消息所解释的那样，您不能一次多次借用可变值 (current_node.chs)。

一个解决方案是为 TrieNode 导出 Clone 特征。 Clone 是显式复制对象能力的一个共同特征：

#[derive(Debug, Clone)]
struct TrieNode {
    chs: HashMap<char, TrieNode>,
    value: Option<i32>,
}

现在您可以克隆它，而不是借用 self.root：

fn delete(&mut self, key: &String) -> Option<i32> {
  if key.is_empty() { 
    return None
  }
  // clone `self.root`
  let mut current_node = self.root.clone();
  for (ind, ch) in key.chars().enumerate() {
  match current_node.chs.get_mut(&ch) {
    Some(node) => {
      if ind < key.len() - 1 {
      // clone `node`
        current_node = node.clone();
      }
    // ...

如果性能是一个问题，那么克隆可能不是最好的主意。但是，它仍然是一个选项，可能适合也可能不适合您的用例。

Answer 2

我不太确定借用检查器在哪里被绊倒了，但你可以通过提升 if 检查来修复它：

    let mut current_node = &mut self.root;
    for (ind, ch) in key.chars().enumerate() {
        if ind < key.len() - 1 {
            match current_node.chs.get_mut(&ch) {
                Some(node) => {
                    current_node = node;
                }
                None => return None,
            }
        }
    }

它甚至会跳过检查叶节点是否存在，但是您的 remove( 匹配已经涵盖了这种情况。

此外，您的 ind < key.len() - 1 检查假设最后一个字符是 ascii。对于您的用例来说可能是正确的，但如果不是，您可以使用迭代直到倒数第二个字符。

Trie：一次不能多次借用 _ 可变的

Trie: cannot borrow `_` as mutable more than once at a time

trie

rust

data-structures