rust 如何在将公共值移动到一个新集合的同时对两个HashSet求交集？

vybvopom 于 2022-12-04 发布在其他

关注(0)|答案(4)|浏览(151)

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））的最小值。

rust

来源：https://stackoverflow.com/questions/55975234/how-do-i-intersect-two-hashsets-while-moving-values-in-common-into-a-new-set

4条答案

按热度按时间

u5rb5r591#

编译器的别名规则要求你来回移动值。值可以从一个集合中被清空，尽管是无条件的。但是，如果我们跟踪哪些值应该被移动，哪些应该留在一个新的集合中，我们可以把某些值发送回去。然后，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]);

Playground

赞(0）回复(0）举报 2022-12-04

n8ghc7c12#

另一个解决方案，similar to E_net4's，但这一个不涉及排放，然后重新填充第一集。IMHO它也稍微容易阅读。

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

赞(0）回复(0）举报 2022-12-04

kdfy810k3#

或者，如果您可以取得集合本身的所有权，并且不在乎保留其他集合中的非相交值，则可以执行以下操作：

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中

赞(0）回复(0）举报 2022-12-04

cld4siwp4#

您也可以使用比特AND运算子：