如何创建内存连续的嵌套Vec？

先看你提供的代码和输出：

let v = vec![vec![1,2,3], vec![4,5,6]];

println!("{:p}", &v[0][0]);
println!("{:p}", &v[0][1]);
println!("{:p}", &v[0][2]);
println!("{:p}", &v[1][0]);
println!("{:p}", &v[1][1]);
println!("{:p}", &v[1][2]);

输出：

0x7f6bbc000d20
0x7f6bbc000d24
0x7f6bbc000d28
0x7f6bbc000d40
0x7f6bbc000d44
0x7f6bbc000d48

问题原因 #

Rust中的Vec<T>由指针、长度、容量三个字段构成，每个子Vec都会独立在堆上分配内存块。嵌套Vec本质是多个独立堆分配的集合，因此子Vec的内存块之间必然存在间隙，无法做到连续。

解决方案：单一底层Vec存储+索引划分 #

要实现内存连续的嵌套结构，核心是把所有子数组的元素放在同一个堆内存块中，再用索引记录每个子数组的范围。

基础实现（手动管理） #

直接用两个Vec：一个存储所有元素，另一个记录每个子数组的起始索引：

fn main() {
    // 存储所有元素的底层连续数组
    let mut data = Vec::new();
    // 记录每个子数组的起始位置
    let mut starts = Vec::new();

    // 添加第一个子数组
    starts.push(data.len());
    data.extend_from_slice(&[1, 2, 3]);
    // 添加第二个子数组
    starts.push(data.len());
    data.extend_from_slice(&[4, 5, 6]);

    // 访问第一个子数组
    let first_sub = &data[starts[0]..starts[1]];
    println!("{:p}", &first_sub[0]);
    println!("{:p}", &first_sub[1]);
    println!("{:p}", &first_sub[2]);

    // 访问第二个子数组
    let second_sub = &data[starts[1]..];
    println!("{:p}", &second_sub[0]); // 地址紧接第一个子数组的最后一个元素
    println!("{:p}", &second_sub[1]);
    println!("{:p}", &second_sub[2]);
}

运行后子数组的元素地址会完全连续，因为所有元素都在同一个data的堆内存里。

封装成结构体（模拟嵌套Vec的使用体验） #

如果需要更接近嵌套Vec的调用方式，可以封装自定义结构体并实现Index trait：

use std::ops::{Index, Range};

struct ContiguousNestedVec<T> {
    data: Vec<T>,
    ranges: Vec<Range<usize>>,
}

impl<T> ContiguousNestedVec<T> {
    fn new() -> Self {
        Self {
            data: Vec::new(),
            ranges: Vec::new(),
        }
    }

    // 添加子数组
    fn push_sub(&mut self, sub: impl IntoIterator<Item = T>) {
        let start = self.data.len();
        self.data.extend(sub);
        let end = self.data.len();
        self.ranges.push(start..end);
    }
}

// 实现索引访问，支持v[0]获取第一个子数组
impl<T> Index<usize> for ContiguousNestedVec<T> {
    type Output = [T];

    fn index(&self, index: usize) -> &Self::Output {
        &self.data[self.ranges[index].clone()]
    }
}

fn main() {
    let mut v = ContiguousNestedVec::new();
    v.push_sub(vec![1, 2, 3]);
    v.push_sub(vec![4, 5, 6]);

    println!("{:p}", &v[0][0]);
    println!("{:p}", &v[0][1]);
    println!("{:p}", &v[0][2]);
    println!("{:p}", &v[1][0]);
    println!("{:p}", &v[1][1]);
    println!("{:p}", &v[1][2]);
}

优缺点说明 #

• 优点：内存完全连续，缓存命中率更高，适合频繁遍历、对性能敏感的场景；
• 缺点：无法单独扩容某个子数组（修改子数组长度需要调整整个底层数组），而原生嵌套Vec可以独立操作每个子数组的内存。

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