Rust中迭代Vec<HashSet<usize>>的v[i-1]时如何更新v[i]？

给定v为Vec<HashSet<usize>>，能否在迭代v[i-1]的同时更新v[i]？

Rust的所有权规则通常会阻止这类同时持有同一容器中两个可变引用的操作，但v[i]和v[i-1]是完全独立的元素，内存上没有重叠，所以确实存在可行方案。允许使用unsafe代码，且假设v长度极大，必须保留Vec容器。

这类场景常见于动态规划，以下是一个极简示例（原代码存在不必要的clone()操作，目标是消除这些clone()）：

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(); // 这个clone用来复制前一个集合的内容
        let prev = v[i - 1].clone(); // 想要消除这个clone
        prev.iter().for_each(|e| {
            v[i].insert(*e + 1);
        })
    }
    println!("{:?}", v); // 输出：[{0}, {0, 1}, {0, 1, 2}, {0, 1, 2, 3}, ...]
}

解决方案 #

方法一：安全方案（推荐）—— 使用split_at_mut #

Rust的Vec::split_at_mut方法可以安全地将容器分割为两个不重叠的可变切片，这样就能同时获取v[i-1]的不可变引用和v[i]的可变引用，完全不需要clone前一个集合来迭代：

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分割为[0..i)和[i..n)两个不重叠的可变切片
        let (left, right) = v.split_at_mut(i);
        // left是[0..i)，left[i-1]对应v[i-1]
        let prev = &left[i-1];
        // right是[i..n)，right[0]对应v[i]
        let curr = &mut right[0];
        
        // 复制前一个集合的所有元素
        curr.extend(prev.iter().cloned());
        // 插入每个元素+1的值
        curr.extend(prev.iter().map(|&e| e + 1));
    }
    
    // 打印前5个元素验证结果
    println!("{:?}", &v[0..5]);
}

方法二：Unsafe方案（仅特殊场景使用） #

如果一定要用unsafe代码，可以通过裸指针获取两个独立元素的引用。由于明确知道i-1和i是不同索引，内存区域不重叠，这个操作是安全的：

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 {
        unsafe {
            // 获取v[i-1]的不可变指针和v[i]的可变指针
            let prev_ptr = v.get_unchecked(i-1) as *const HashSet<usize>;
            let curr_ptr = v.get_unchecked_mut(i) as *mut HashSet<usize>;
            
            // 解引用指针为引用
            let prev = &*prev_ptr;
            let curr = &mut *curr_ptr;
            
            curr.extend(prev.iter().cloned());
            curr.extend(prev.iter().map(|&e| e + 1));
        }
    }
    
    println!("{:?}", &v[0..5]);
}

说明 #

两种方案都消除了原代码中迭代前的clone()操作，同时保留原逻辑：先复制前一个集合的内容，再添加每个元素+1的值。安全方案利用Rust类型系统保证内存安全，是首选；unsafe方案需开发者自行确保索引不重叠，仅在特殊场景考虑使用。

内容的提问来源于stack exchange，提问作者ynn