在Rust中遍历HashSet的同时对其进行更新的最优实现方案是什么？

优化思路 #

你当前实现的主要冗余点在于重复的成员检查、多余的集合维护，完全可以通过精简逻辑降低开销：

1. HashSet插入时自带去重逻辑，不需要提前手动检查当前批次（原代码中的curr）是否存在对应元素
2. 可以利用迭代器简化嵌套循环逻辑，减少不必要的变量声明
3. 调整process的返回类型约束，支持直接返回迭代器，省掉中间集合的创建开销

优化后实现 #

use std::collections::HashSet;

fn extend_from_within<T, F, I>(original: &mut HashSet<T>, process: F) 
where 
    T: Eq + Hash,
    F: Fn(&T) -> I,
    I: IntoIterator<Item = T>
{
    // 首次处理原始集合已有元素，筛选出未存在的新元素作为首批待处理项
    let mut pending: HashSet<_> = original
        .iter()
        .flat_map(|x| process(x))
        .filter(|y| !original.contains(y))
        .collect();

    while !pending.is_empty() {
        let mut next_pending = HashSet::new();
        // 处理当前批次所有待处理元素，生成下一批新元素
        for item in &pending {
            next_pending.extend(process(item).filter(|y| !original.contains(y)));
        }
        // 合并当前批次元素到原始集合
        original.extend(pending);
        pending = next_pending;
    }
}

额外优化点 #

如果你的业务场景中，process返回的元素本身不会重复，可以把pending和next_pending的类型从HashSet换成Vec，省去哈希计算和哈希表维护的开销，性能会更好。调整后只需要修改两处类型声明即可：

// 把原来的HashSet声明换成Vec
let mut pending: Vec<_> = original
    .iter()
    .flat_map(|x| process(x))
    .filter(|y| !original.contains(y))
    .collect();

// 下一批待处理也换成Vec
let mut next_pending = Vec::new();

内容的提问来源于stack exchange，提问作者Lokapit