如何在将共同的值移动到新集合中时交叉两个哈希集?

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中窃取/移动数据并bc？理想情况下，这将具有理论上最佳的时间复杂度：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

另一种解决方案，类似于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
}

游乐场链接

写完这篇文章后，我意识到它可以变得更简单：

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
}

游乐场链接

Answer 3

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

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 中包含的元素，并将它们收集到一个新的 HashSet 中

Answer 4

您也可以使用按位和运算符：

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