在同一Vec中的另一个元素的字段上循环时,变换Vec元素的字段

Question

我正在Rust中编写一个Trie数据结构来实现Aho-Corasick算法.该TrieNode结构respresents一个节点,如下所示:

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);
    }
    ...
}