title: Is there a zero-copy way to find the intersection of an arbitrary number of sets?
body: <p>Here is a simple example demonstrating what I'm trying to do:</p>
  <pre><code>use std::collections::HashSet;
  
  fn main() {
      let mut sets: Vec&lt;HashSet&lt;char&gt;&gt; = 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(&amp;sets[1]);
      println!(&quot;Intersection of 0 and 1: {:?}&quot;, 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!(&quot;Intersection of all: {:?}&quot;, intersection);
  }
  </code></pre>
  <p>This solution uses fold to &quot;accumulate&quot; the intersection, using the first element as the initial value.</p>
  <p><code>Intersection</code>s are lazy iterators which iterate through references to the involved sets. Since the accumulator has to have the same type as the first element, we have to clone each set's elements. We can't make a set of owned data from references without cloning. I think I understand this.</p>
  <p>For example, this doesn't work:</p>
  <pre><code>let mut iter = sets.iter();
  let mut base = iter.next().unwrap();
  let intersection = iter.fold(base, |acc, set| acc.intersection(set).collect());
  println!(&quot;Intersection of all: {:?}&quot;, intersection);
  </code></pre>
  <hr />
  <pre><code>error[E0277]: a value of type `&amp;HashSet&lt;char&gt;` cannot be built from an iterator over elements of type `&amp;char`
    --&gt; src/main.rs:41:73
     |
  41 |     let intersection = iter.fold(base, |acc, set| acc.intersection(set).collect());
     |                                                                         ^^^^^^^ value of type `&amp;HashSet&lt;char&gt;` cannot be built from `std::iter::Iterator&lt;Item=&amp;char&gt;`
     |
     = help: the trait `FromIterator&lt;&amp;char&gt;` is not implemented for `&amp;HashSet&lt;char&gt;`
  </code></pre>
  <p>Even understanding this, I still don't want to clone the data. In theory it shouldn't be necessary, I have the data in the original vector, I should be able to work with references. That would speed up my algorithm a lot. This is a purely academic pursuit, so I am interested in getting it to be as fast as possible.</p>
  <p>To do this, I would need to accumulate in a <code>HashSet&lt;&amp;char&gt;</code>s, but I can't do that because I can't intersect a <code>HashSet&lt;&amp;char&gt;</code> with a <code>HashSet&lt;char&gt;</code> in the closure. So it seems like I'm stuck. Is there any way to do this?</p>
  <p>Alternatively, I could make a set of references for each set in the vector, but that doesn't really seem much better. Would it even work? I might run into the same problem but with double references instead.</p>
  <p>Finally, I don't actually need to retain the original data, so I'd be okay moving the elements into the accumulator set. I can't figure out how to make this happen, since I have to go through <code>intersection</code> which gives me references.</p>
  <p>Are any of the above proposals possible? Is there some other zero copy solution that I'm not seeing?</p>