如何在将共同值移动到新集合中的同时将两个 HashSet 相交？

Question

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`

我不再需要不相交的值。如何偷/移动从集数据a和b成c无需复制或克隆？理想情况下，这将具有理论上最佳的时间复杂度：O(min(a, b))。

Answer 1

编译器强加的别名规则要求您来回移动值。值可以从集合中排出，尽管是无条件的。但是，如果我们跟踪哪些值应该被移动，哪些应该保留在新的集合中，我们可以将某些值发回。之后，retain允许我们从第二组中删除公共值。

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
}

使用：

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]);

操场