rust 给定'Vec< HashSet>',如何在迭代'v[i - 1]'时更新'v[i]`?[duplicate]

o75abkj4  于 2022-12-23  发布在  其他
关注(0)|答案(1)|浏览(167)
    • 此问题在此处已有答案**:

(9个答案)
15小时前关门了。
vVec<HashSet<usize>>
是否可以在迭代v[i - 1]时更新v[i]
通常,Rust的所有权规则不允许这样做,但我相信应该存在某种方式,因为v[i]v[i - 1]本质上是独立的。
unsafe是允许的,因为unsafe有时候允许我们绕过(某种意义上)所有权规则。(例如,交换HashMap的值通常是不可能的,但是使用unsafe使之成为可能。swapping two entries of a HashMap
请假设v.len()非常大,因为如果v.len()很小,您首先就可以放弃使用Vec容器。
下面是一个非常人工但最小的工作示例(Rust Playground)。这种类型的源代码在做dynamic programming时经常看到。

use std::collections::HashSet;

fn main() {
    let n = 100000;
    let mut v = vec![HashSet::new(); n];
    v[0].insert(0);
    for i in 1..n {
        v[i] = v[i - 1].clone(); //This `clone()` is necessarily.
        let prev = v[i - 1].clone(); //I want to eliminate this `clone()`.
        prev.iter().for_each(|e| {
            v[i].insert(*e + 1);
        })
    }
    println!("{:?}", v); //=> [{0}, {0, 1}, {0, 1, 2}, {0, 1, 2, 3}, ...]
}
bq3bfh9z

bq3bfh9z1#

当你用v[i]修改一个向量时,你使用的是IndexMut trait,它需要一个可变的借用到Self,也就是整个向量。因此,Rust永远不允许同时使用v[i]v[i-1],如果它们中至少有一个是可变的借用。
要解决这个问题,您必须再努力一点,让Rust知道v[i]v[i-1]没有别名(因为,最终,所有的借用检查都在LLVM中结束,LLVM能够判断是否有别名)。
"坏"消息是不依赖于unsafe是不可能做到的,好消息是其他人已经做了,并将其 Package 在一个安全的接口中,即split_at_mut,这将把一个向量分成两个子切片,这两个子切片保证是不相交的(这就是unsafe的作用)。
所以,举个例子,在你的情况下,你可以

use std::collections::HashSet;

fn main() {
    let n = 100000;
    let mut v = vec![HashSet::new(); n];
    v[0].insert(0);
    for i in 1..n {
        v[i] = v[i - 1].clone(); //This `clone()` is necessarily.
        let (left, right) = v.split_at_mut(i);
        left[i-1].iter().for_each(|e| {
            right[0].insert(*e + 1);
        })
    }
    println!("{:?}", v); //=> [{0}, {0, 1}, {0, 1, 2}, {0, 1, 2, 3}, ...]
}

参见the playground
此外,也许这只是因为您的示例被简化了,但是如果您只是立即修改它们,那么创建100000个HashMap实际上没有意义。

use std::collections::HashSet;

fn main() {
    let n = 100000;
    let mut v = Vec::with_capacity(n);
    v.insert(HashSet::from([0]));
    for i in 0..n-1 {
        let mut new_set = v[i].clone();
        for e in v[i].iter().copied() {
            new_set.insert(e+1);
        }
        v.push(new_set);
    }
    println!("{:?}", v);
}

参见the playground

相关问题