rust - 有没有零拷贝的方法来找到任意数量的集合的交集？

Question

这是一个简单的示例，演示了我正在尝试做的事情:

use std::collections::HashSet;

fn main() {
    let mut sets: Vec<HashSet<char>> = vec![];

    let mut set = HashSet::new();
    set.insert('a');
    set.insert('b');
    set.insert('c');
    set.insert('d');
    sets.push(set);

    let mut set = HashSet::new();
    set.insert('a');
    set.insert('b');
    set.insert('d');
    set.insert('e');
    sets.push(set);

    let mut set = HashSet::new();
    set.insert('a');
    set.insert('b');
    set.insert('f');
    set.insert('g');
    sets.push(set);

    // Simple intersection of two sets
    let simple_intersection = sets[0].intersection(&sets[1]);
    println!("Intersection of 0 and 1: {:?}", simple_intersection);

    let mut iter = sets.iter();
    let base = iter.next().unwrap().clone();
    let intersection = iter.fold(base, |acc, set| acc.intersection(set).map(|x| x.clone()).collect());
    println!("Intersection of all: {:?}", intersection);
}

此解决方案使用 fold 来“累积”交集，使用第一个元素作为初始值。Intersection s 是惰性迭代器，它通过对相关集合的引用进行迭代。由于累加器必须与第一个元素具有相同的类型，我们必须克隆每个集合的元素。我们不能在没有克隆的情况下从引用中创建一组拥有的数据。我想我明白这一点。
例如，这不起作用:

let mut iter = sets.iter();
let mut base = iter.next().unwrap();
let intersection = iter.fold(base, |acc, set| acc.intersection(set).collect());
println!("Intersection of all: {:?}", intersection);

error[E0277]: a value of type `&HashSet<char>` cannot be built from an iterator over elements of type `&char`
  --> src/main.rs:41:73
   |
41 |     let intersection = iter.fold(base, |acc, set| acc.intersection(set).collect());
   |                                                                         ^^^^^^^ value of type `&HashSet<char>` cannot be built from `std::iter::Iterator<Item=&char>`
   |
   = help: the trait `FromIterator<&char>` is not implemented for `&HashSet<char>`

即使理解了这一点，我仍然不想克隆数据。理论上应该没有必要，我有原始向量中的数据，我应该能够使用引用。这将大大加快我的算法。这是一个纯粹的学术追求，所以我有兴趣让它尽可能快。
为此，我需要积累 HashSet<&char> s，但我不能这样做，因为我不能与 HashSet<&char> 相交与 HashSet<char>在关闭。所以看起来我被卡住了。有没有办法做到这一点？
或者，我可以为向量中的每个集合创建一组引用，但这似乎并没有好多少。它甚至会起作用吗？我可能会遇到同样的问题，但改为使用双重引用。
最后，我实际上不需要保留原始数据，所以我可以将元素移动到累加器集中。我不知道如何实现这一点，因为我必须通过 intersection这给了我引用。
以上建议是否可行？还有其他一些我没有看到的零拷贝解决方案吗？

Answer 1

Finally, I don't actually need to retain the original data.

这真的很容易。
首先，可选择按大小对集合进行排序。然后:

let (intersection, others) = sets.split_at_mut(1);
let intersection = &mut intersection[0];
for other in others {
    intersection.retain(|e| other.contains(e));
}