我有一个集合向量,我想删除作为向量中其他集合子集的所有集合。示例:
a = {0, 3, 5}
b = {0, 5}
c = {0, 2, 3}
在这种情况下,我想删除 b
,因为它是 a
的子集。我可以使用“愚蠢的”n² 算法。
遗憾的是,让它与借用检查器一起工作非常棘手。我想到的最好的是 ( Playground ):
let mut v: Vec<HashSet<u8>> = vec![];
let mut to_delete = Vec::new();
for (i, set_a) in v.iter().enumerate().rev() {
for set_b in &v[..i] {
if set_a.is_subset(&set_b) {
to_delete.push(i);
break;
}
}
}
for i in to_delete {
v.swap_remove(i);
}
(注意:上面的代码不正确!查看评论了解更多详情)
我看到了一些缺点:
- 我需要一个带有额外分配的额外向量
- 也许有比经常调用
swap_remove
更有效的方法 - 如果我需要保留顺序,我不能使用
swap_remove
,但必须使用速度较慢的remove
有没有更好的方法来做到这一点?我不仅要问我的用例,还要问标题中描述的一般情况。
最佳答案
这是一个不进行额外分配并保留顺序的解决方案:
fn product_retain<T, F>(v: &mut Vec<T>, mut pred: F)
where F: FnMut(&T, &T) -> bool
{
let mut j = 0;
for i in 0..v.len() {
// invariants:
// items v[0..j] will be kept
// items v[j..i] will be removed
if (0..j).chain(i + 1..v.len()).all(|a| pred(&v[i], &v[a])) {
v.swap(i, j);
j += 1;
}
}
v.truncate(j);
}
fn main() {
// test with a simpler example
// unique elements
let mut v = vec![1, 2, 3];
product_retain(&mut v, |a, b| a != b);
assert_eq!(vec![1, 2, 3], v);
let mut v = vec![1, 3, 2, 4, 5, 1, 2, 4];
product_retain(&mut v, |a, b| a != b);
assert_eq!(vec![3, 5, 1, 2, 4], v);
}
这是一种分区算法。第一个分区中的元素将被保留,第二个分区中的元素将被删除。
关于rust - 根据同一 Vec 的其他元素删除 Vec 元素的最佳方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37906012/