Как я пересекаю два HashSets при перемещении общих значений в новый набор?

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

Детская площадка

Answer 2

В качестве альтернативы, если вы можете стать владельцем самих наборов и не заботиться о сохранении непересекающихся значений в других наборах, вы можете сделать следующее:

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()
}

Это займет элементыв a, которые содержатся в b и собирает их в новый HashSet

Answer 3

Другое решение, похожее на E_net4, но это не включает слив и последующее повторное заполнение первого набора. ИМХО, его немного легче читать.

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

После написания я понял, что это можно сделать еще проще:

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