How do I intersect two HashSets while moving values in common into a new set?

use std::collections::HashSet;
let mut a: HashSet<T> = HashSet::new();
let mut b: HashSet<T> = HashSet::new();
let mut c: HashSet<T> = a.intersection(&b).collect();
// Error: a collection of type `std::collections::HashSet<T>` cannot be built from an iterator over elements of type `&T`

I no longer need the non-intersecting values. How do I steal/move the data from the sets a and b into c without copying or cloning? Ideally, this would have the theoretically optimal time-complexity: O(min(a, b)).

4 Answers

The aliasing rules imposed by the compiler requires you to move the values back and forth. Values can be drained out of a set, although unconditionally. However, we can send certain values back if we keep track of which should be moved and which should stay in a new set. Afterwards, retain allows us to remove the common values from the second set.

use std::collections::HashSet;
use std::hash::Hash;
/// Extracts the common values in `a` and `b` into a new set.
fn inplace_intersection<T>(a: &mut HashSet<T>, b: &mut HashSet<T>) -> HashSet<T>
where T: Hash, T: Eq,
{ let x: HashSet<(T, bool)> = a .drain() .map(|v| { let intersects = b.contains(&v); (v, intersects) }) .collect(); let mut c = HashSet::new(); for (v, is_inter) in x { if is_inter { c.insert(v); } else { a.insert(v); } } b.retain(|v| !c.contains(&v)); c
}

Using:

use itertools::Itertools; // for .sorted()
let mut a: HashSet<_> = [1, 2, 3].iter().cloned().collect();
let mut b: HashSet<_> = [4, 2, 3].iter().cloned().collect();
let c = inplace_intersection(&mut a, &mut b);
let a: Vec<_> = a.into_iter().sorted().collect();
let b: Vec<_> = b.into_iter().sorted().collect();
let c: Vec<_> = c.into_iter().sorted().collect();
assert_eq!(&a, &[1]);
assert_eq!(&b, &[4]);
assert_eq!(&c, &[2, 3]);

Playground

Another solution, similar to E_net4's, but this one does not involve draining and then repopulating the first set. IMHO it is slightly easier to read as well.

fn inplace_intersection<T>(a: &mut HashSet<T>, b: &mut HashSet<T>) -> HashSet<T>
where T: Hash, T: Eq,
{ let mut c = HashSet::new(); for v in a.iter() { if let Some(found) = b.take(v) { c.insert(found); } } a.retain(|v| !c.contains(&v)); c
}

Playground Link

After writing this I realized it could be made even simpler:

fn inplace_intersection<T>(a: &mut HashSet<T>, b: &mut HashSet<T>) -> HashSet<T>
where T: Hash, T: Eq,
{ let c: HashSet<T> = a.iter().filter_map(|v| b.take(v)).collect(); a.retain(|v| !c.contains(&v)); c
}

Playground Link

Alternatively, if you can take ownership over the sets themselves and don't care about retaining the non-intersecting values in the other sets, you can do the following:

use std::hash::Hash;
use std::collections::HashSet;
fn intersection<T: Eq + Hash>(a: HashSet<T>, b: &HashSet<T>) -> HashSet<T> { a.into_iter().filter(|e| b.contains(e)).collect()
}

This takes the elements in a which are contained in b and collects them into a new HashSet

You can use the bitwise and operator as well:

let mut c: HashSet<T> = &a & &b