parsing - 如何在 Rust 中迭代 HashSet 并同时更新它？

Question

在大多数语言中，迭代容器并同时对其进行变异是一种明显的反模式。在 Rust 中，借用检查器使之变得不可能。

但有些情况下是需要这样做的。一个例子是 Earley 的解析算法。我是 Rust 新手，我不知道在扩展 HashSet (或实际上任何容器)时有什么好的方法可以对其进行迭代。我想出了以下内容(从 Earley 用例中概括):

use std::collections::HashSet;

fn extend_from_within<T, F>(original: &mut HashSet<T>, process: F) 
    where T: std::cmp::Eq,
          T: std::hash::Hash,
          F: Fn(&T) -> Set<T>
{
    let mut curr : HashSet<T> = HashSet::new(); // Items currently being processed
    let mut next : HashSet<T> = HashSet::new(); // New items

    // go over the original set once
    let hack : &HashSet<T> = original; // &mut HashSet is not an iterator
    for x in hack {
        for y in process(x) {
            if !original.contains(&y) {
                curr.insert(y);
            }
        }
    }

    // Process and extend until no new items emerge
    while !curr.is_empty() {
        for x in &curr {
            for y in process(x) {
                // make sure that no item is processed twice
                // the check on original is redundant, but might save space
                if !curr.contains(&y) && !original.contains(&y) {
                    next.insert(y);
                }
            }
        }

        original.extend(curr.drain());
        std::mem::swap(&mut curr, &mut next);
    }
}

如您所见，任何对 process 的调用都可以产生多个项目。它们都被添加到集合中，并且也都必须被处理，但前提是它们还没有被看到。这已经足够好了。但是保留最多 4 组，对每个项目进行 3 次成员资格检查(其中一项在原始数组上检查两次)对于这个问题来说似乎很荒谬。有更好的办法吗？

Answer 1

I'm not aware of a known good way to iterate over a HashSet (or in fact any Container) while extending it

我认为在迭代 HashMaps 时主要有三种处理修改的模式/HashSets :

• 将修改收集到 Vec 中并在迭代后应用它们
• drain荷兰国际集团HashSet和collect进入新的阶段
• retain ，但这仅适用于删除

但无论如何，你的情况很特殊，你想让你的集合充满 process ，对吗？

Is there a better way?

在这种情况下，我可能会选择

let mut todo = original.iter().map(Clone::clone).collect::<VecDeque<T>>();
while let Some(x) = todo.pop_front() {
    for x in process(&x) {
        if original.insert(x.clone()) {
            todo.push_back(x);
        }
    }
}

• VecDeque可能没有必要(正常的 Vec 就可以)，除非您对处理元素的顺序有一些要求。缓存方面，a Vec可能会更好。
• 可以避免 clone而是保留 Set process(x) 的结果在todo 。不知道什么Set和T是，我不能说哪个更好。如果process的结果通常是空的，这也允许在将空的插入 todo 之前过滤掉它们。 .
• [编辑:]另一种变体可能是

  let mut todo = original
      .iter()
      .flat_map(&process)
      .filter(|x| !original.contains(x))
      .collect::<VecDeque<T>>();
  todo.iter().for_each(|x| {
      original.insert(x.clone());
  });
  // while let …
  

  这可能会分配较少的资源，但会导致更多的 HashMap 访问/缓存未命中。找出哪种变体更有效确实需要基准测试。