通过查找 self 中的键替换 HashSet 值

Question

我有一个 map: HashSet<String, String> 并且想有条件地改变每个值。

我想在我正在改变的 HashSet 中查找新值。

如何才能避免借用检查器的问题？

fn main() {
    let mut map = std::collections::HashMap::new();
    map.insert("alien".to_string(), "".to_string());
    map.insert("covid".to_string(), "virus".to_string());
    map.insert("mammal".to_string(), "animal".to_string());
    map.insert("cat".to_string(), "mammal".to_string());
    map.insert("lion".to_string(), "cat".to_string());

    println!("{:#?}", map);

    // Replace values by lookup in self
    loop {
        let mut done = true;
        for (key, val) in map {
            if let Some(new) = map.get(val) {
                if let Some(old) = map.insert(key.clone(), new.clone()) {
                    if &old != new {
                        done = false;
                    }
                }
            }
        }
        if done {
            break;
        }
    }

    let mut result = std::collections::HashMap::new();
    result.insert("alien".to_string(), "".to_string());
    result.insert("covid".to_string(), "virus".to_string());
    result.insert("mammal".to_string(), "animal".to_string());
    result.insert("cat".to_string(), "animal".to_string());
    result.insert("lion".to_string(), "animal".to_string());

    println!("{:#?}", result);

    assert_eq!(map, result);
}

Playground

Answer 1

在花了很长时间之后，这是我根据@Stargateur 的建议得出的。

我使用第二个 HashMap 来存储您要查找的内容 - 由您的 map 定义的树（或更具体地说是森林）中每个节点的根。为了防止完全遍历这些树，我检查是否已经找到父树的根。如果是这样，则无需寻找 root，只需使用它即可。否则，我会遍历树，直到找到一个根或已经在 reducedMap 中找到一个根，并且在我遍历时存储我访问过的节点 - 我们将找到的根也将是它们的根。

找到根后，我将这个根分配给所有访问过的节点。

我们完成了将 reducedMap（引用映射）转换为结果映射，为此我们克隆了字符串

    // map of shortcuts to root, just references, no string copying
    let mut reducedMap = std::collections::HashMap::<&std::string::String, &std::string::String>::new();

    for (key, mut val) in map.iter() {
        let mut intermediateKeys = vec![]; // all intermediate keys as we go to root
        loop { 
            intermediateKeys.push(key); // remember the intermediate key to update it's shortcut too
            if let Some(shortcut) = reducedMap.get(val) { 
                val = shortcut; // if we know the shortcut, take it and leave 
                break;
            } 
            if let Some(parent) = map.get(val) {
                val = parent; // while not root, go deeper
            } else {
                break; // reached the root
            }
        }
        // insert or update shortcuts for all intermediate keys (root is in `val`)
        intermediateKeys.drain(..) // take items and clear the vector
            .for_each(|k| *reducedMap.entry(k).or_insert(val) = val);
    }

    map = reducedMap.iter()
        .map(|(k, v)| (k.to_string(), v.to_string()))
        .collect();  // move result back, now actually cloning strings

Playground

通过查找 self 中的键替换 HashSet 值

Replace HashSet value by looking up key in self

hashset

rust