通过查找自身的键替换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