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)).

1

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

1

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

3

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.