rust - 在遍历同一 Vec 中另一个元素的字段时改变 Vec 元素的字段

Question

我正在用 Rust 编写一个 Trie 数据结构来实现 Aho-Corasick 算法。 TrieNode 结构表示一个节点，如下所示:

use std::collections::{HashMap, HashSet, VecDeque};

struct TrieNode {
    next_ids: HashMap<char, usize>,
    kw_indices: HashSet<usize>,
    fail_id: Option<usize>,
}

我使用与分代竞技场相同的策略来实现 trie，其中所有节点都存储在一个 Vec 中，并使用它们的索引相互引用。在创建所有节点后构建自动机时，我试图在不使用 clone() 方法的情况下运行以下代码:

fn build_ac_automaton(nodes: &mut Vec<TrieNode>) {
    let mut q = VecDeque::new();
    for &i in nodes[0].next_ids.values() {
        q.push_back(i);
        nodes[i].fail_id = Some(0);
    }
    // ...
}

但是借阅检查员对此不是很高兴:

error[E0502]: cannot borrow `*nodes` as mutable because it is also borrowed as immutable
   |
   |             for &i in nodes[0].next_ids.values() {
   |                       -----                    - immutable borrow ends here
   |                       |
   |                       immutable borrow occurs here
   |                 q.push_back(i);
   |                 nodes[i].fail_id = Some(0);
   |                 ^^^^^ mutable borrow occurs here

在不使用代价高昂的 clone() 方法的情况下，还有什么方法(如果有的话)实现上述目标？

Answer 1

分割切片:

fn build_ac_automaton(nodes: &mut Vec<TrieNode>) {
    let mut q = VecDeque::new();
    let (first, rest) = nodes.split_first_mut();
    for &i in first.next_ids.values() {
        q.push_back(i);
        if i == 0 {
            first.fail_id = Some(0);
        } else {
            rest[i-1].fail_id = Some(0);
        }
    }
    ...
}

然而，仅克隆 next_ids 可能成本更低:

fn build_ac_automaton(nodes: &mut Vec<TrieNode>) {
    let mut q = VecDeque::new();
    let ids: Vec<_> = nodes[0].next_ids.values().cloned().collect();
    for &i in ids {
        q.push_back(i);
        nodes[i].fail_id = Some(0);
    }
    ...
}