面试题：Rust向量动态扩展的基本原理及实现

Question

请阐述Rust向量（Vec）动态扩展背后的基本原理。并编写一段Rust代码，展示如何通过添加元素使Vec动态扩展，同时说明在扩展过程中内存是如何管理的。

Answer 1

Rust向量（Vec）动态扩展背后的基本原理

1. 内存分配策略：
   • Vec在底层使用连续的内存块来存储元素。当创建一个空的Vec时，它通常会分配一个初始容量（可能是0）。随着元素的添加，当当前容量不足以容纳新元素时，Vec会重新分配内存。
   • 重新分配内存时，Vec会申请一块更大的内存块，通常是当前容量的两倍（不同的Rust版本和平台可能略有差异）。然后将原来的数据从旧的内存块复制到新的内存块，并释放旧的内存块。
2. 指针和长度：
   • Vec内部通过三个部分来管理内存：一个指向存储元素的内存块的指针，当前Vec中元素的数量（长度），以及当前分配的内存块能容纳的最大元素数量（容量）。

代码展示如何通过添加元素使Vec动态扩展

fn main() {
    let mut vec: Vec<i32> = Vec::new();
    // 初始容量通常为0
    println!("初始容量: {}", vec.capacity());

    for i in 0..10 {
        vec.push(i);
        if vec.len() == vec.capacity() {
            println!("在添加元素 {} 后，容量扩展到: {}", i, vec.capacity());
        }
    }
    println!("最终长度: {}", vec.len());
    println!("最终容量: {}", vec.capacity());
}

扩展过程中内存管理说明

1. 初始状态：当使用Vec::new()创建一个空的Vec时，它有一个指向空内存块的指针，长度为0，容量通常也为0（有些实现可能有一个小的初始容量）。
2. 第一次添加元素：当调用push方法添加第一个元素时，Vec发现当前容量为0，不足以容纳新元素，于是会分配一个合适大小的内存块（通常能容纳至少一个元素）。此时容量变为1（或其他初始值），长度变为1。
3. 后续添加元素：随着不断调用push方法添加元素，当长度达到当前容量时，Vec会重新分配内存。例如，假设当前容量为4，长度也为4，当添加第5个元素时，Vec会分配一个新的内存块，容量变为8（通常是当前容量的两倍），然后将原来4个元素从旧内存块复制到新内存块，释放旧内存块，最后将新元素添加到新内存块，此时长度变为5，容量变为8。