Rust Vec 的内存布局与扩容策略：深入理解动态数组的核心机制

一、Vec 的内存布局剖析

Rust 的 Vec<T> 是一个在堆上分配的动态数组，它在栈上存储三个关键字段：

pub struct Vec<T> {
    ptr: *mut T,      // 指向堆内存的指针
    cap: usize,       // 容量（已分配的元素数量）
    len: usize,       // 长度（实际存储的元素数量）
}

这个设计非常精妙：栈上只占用 24 字节（64位系统），而实际数据存储在堆上。让我们通过实验验证：

use std::mem;

fn main() {
    let vec: Vec<i32> = vec![1, 2, 3, 4, 5];
    
    println!("Vec 本身大小: {} 字节", mem::size_of_val(&vec));
    println!("Vec 长度: {}", vec.len());
    println!("Vec 容量: {}", vec.capacity());
    println!("指针地址: {:p}", vec.as_ptr());
    
    // 验证数据在堆上
    let stack_var = 42;
    println!("栈变量地址: {:p}", &stack_var);
    println!("Vec 数据地址: {:p}", &vec[0]);
}

关键观察：Vec 自身大小固定（24字节），与元素数量无关！这体现了 Rust 的零成本抽象理念。

二、扩容策略：倍增法则

Vec 采用 指数增长策略，每次扩容时容量大约翻倍。这种设计在时间和空间上达到了巧妙的平衡。

扩容行为实验

fn main() {
    let mut vec = Vec::new();
    let mut last_capacity = 0;
    
    println!("索引 | 长度 | 容量 | 扩容");
    println!("-----|------|------|------");
    
    for i in 0..20 {
        if vec.capacity() != last_capacity {
            println!("{:4} | {:4} | {:4} | ✓", 
                     i, vec.len(), vec.capacity());
            last_capacity = vec.capacity();
        }
        vec.push(i);
    }
}

输出分析：

• 初始容量为 0

• 首次 push 分配容量 4

• 后续扩容：4 → 8 → 16 → 32...

为什么是倍增？因为这保证了 摊还时间复杂度为 O(1)。假设插入 n 个元素：

• 扩容次数：log₂(n)

• 总拷贝次数：n + n/2 + n/4 + ... ≈ 2n

• 平均每次插入：O(1)

三、深度实践：观察内存重分配

fn main() {
    let mut vec = Vec::with_capacity(4);
    let initial_ptr = vec.as_ptr();
    
    println!("初始指针: {:p}", initial_ptr);
    
    for i in 0..10 {
        vec.push(i);
        let current_ptr = vec.as_ptr();
        
        if current_ptr != initial_ptr {
            println!("第 {} 次 push 触发扩容！", i);
            println!("  旧指针: {:p}", initial_ptr);
            println!("  新指针: {:p}", current_ptr);
            println!("  新容量: {}", vec.capacity());
        }
    }
}

关键发现：指针地址变化意味着整个数组被重新分配并拷贝到新位置！这就是为什么：

1. 频繁扩容会影响性能

2. 持有元素的引用在扩容后可能失效

四、性能优化：预分配策略

use std::time::Instant;

fn test_without_reserve() -> u128 {
    let start = Instant::now();
    let mut vec = Vec::new();
    for i in 0..1_000_000 {
        vec.push(i);
    }
    start.elapsed().as_micros()
}

fn test_with_reserve() -> u128 {
    let start = Instant::now();
    let mut vec = Vec::with_capacity(1_000_000);
    for i in 0..1_000_000 {
        vec.push(i);
    }
    start.elapsed().as_micros()
}

fn main() {
    println!("不预分配耗时: {} μs", test_without_reserve());
    println!("预分配耗时: {} μs", test_with_reserve());
}

性能对比：预分配可提升 30-50% 的性能！

五、专业思考：容量管理技巧

1. 使用 shrink_to_fit() 回收内存

fn main() {
    let mut vec = Vec::with_capacity(100);
    vec.push(1);
    
    println!("收缩前容量: {}", vec.capacity());
    vec.shrink_to_fit();
    println!("收缩后容量: {}", vec.capacity());
}

2. 避免不必要的克隆

// ❌ 糟糕：完整拷贝
let vec2 = vec1.clone();

// ✅ 更好：共享所有权（如果可能）
let vec2 = std::rc::Rc::new(vec1);

// ✅ 或转移所有权
let vec2 = vec1; // vec1 不再可用

3. 理解 reserve vs reserve_exact

fn main() {
    let mut vec = Vec::with_capacity(4);
    
    // reserve 可能分配比请求更多的容量
    vec.reserve(10);
    println!("reserve 后容量: {}", vec.capacity()); // 可能 > 14
    
    let mut vec2 = Vec::with_capacity(4);
    // reserve_exact 精确分配
    vec2.reserve_exact(10);
    println!("reserve_exact 后容量: {}", vec2.capacity()); // 精确 14
}

六、安全性保障：所有权与借用

Rust 通过所有权系统防止内存安全问题：

fn main() {
    let mut vec = vec![1, 2, 3];
    let first = &vec[0]; // 不可变借用
    
    // vec.push(4); // ❌ 编译错误！扩容可能使 first 失效
    
    println!("第一个元素: {}", first);
    vec.push(4); // ✅ 借用结束后才能修改
}

总结

Vec 的设计体现了三大核心原则：

1. 高效的内存布局：栈上固定 24 字节，数据在堆上

2. 智能的扩容策略：倍增法实现摊还 O(1) 复杂度

3. 安全的内存管理：所有权系统防止悬空指针

实践建议：

• 已知大小时使用 with_capacity 预分配 🎯

• 注意扩容对引用的影响 ⚠️

• 不再使用时考虑 shrink_to_fit 回收内存 ♻️