📑 目录

• 前言：为什么要读源码？
• 第一章：Vec 的底层结构
• 第二章：内存分配策略
• 第三章：扩容机制
• 第四章：元素操作
• 第五章：性能优化技巧
• 总结

---

前言：为什么要读源码？💡

Vec<T> 是 Rust 最常用的集合类型，但你真的理解它吗？

let mut v = Vec::new();
v.push(1);  // 发生了什么？
v.push(2);  // 内存如何扩容？

通过阅读源码，你将理解：

• ✅ 内存如何分配和释放
• ✅ 扩容策略的设计思想
• ✅ 为什么 Vec 这么快
• ✅ 如何写出高性能代码

---

第一章：Vec 的底层结构 🏗️

1.1 核心数据结构

// 简化版源码
pub struct Vec<T> {
    buf: RawVec<T>,   // 底层缓冲区
    len: usize,       // 当前元素数量
}

struct RawVec<T> {
    ptr: Unique<T>,   // 指向堆内存的指针
    cap: usize,       // 容量（可容纳元素数）
}

关键字段：

• ptr：指向堆上分配的内存
• cap：当前分配的容量
• len：实际存储的元素数量

1.2 内存布局

栈上：
┌─────────────────┐
│ Vec<T>          │
│ ├─ ptr: 0x1000 │ ──┐
│ ├─ cap: 4       │   │
│ └─ len: 2       │   │
└─────────────────┘   │
                       │
堆上：                 │
┌──────────────────────┼──┐
│ 0x1000: [1, 2, ?, ?] │  │
└──────────────────────┘  │
  │     │    └─ 未初始化  │
  │     └─ 已使用 (len=2) │
  └─ 容量 (cap=4) ────────┘

---

第二章：内存分配策略 💾

2.1 创建空 Vec

// Vec::new() 源码
pub const fn new() -> Vec<T> {
    Vec {
        buf: RawVec::new(),
        len: 0,
    }
}

// RawVec::new()
impl<T> RawVec<T> {
    pub const fn new() -> Self {
        RawVec {
            ptr: Unique::dangling(),  // 悬垂指针，不分配内存！
            cap: 0,
        }
    }
}

关键点：Vec::new() 不分配内存，零成本！

2.2 首次分配

// push() 第一次调用
pub fn push(&mut self, value: T) {
    if self.len == self.cap {
        self.buf.reserve_for_push(self.len);  // 扩容
    }
    unsafe {
        let end = self.as_mut_ptr().add(self.len);
        ptr::write(end, value);
        self.len += 1;
    }
}

// 首次扩容
fn reserve_for_push(&mut self, used_capacity: usize) {
    self.grow_amortized(used_capacity, 1);
}

fn grow_amortized(&mut self, used_cap: usize, needed: usize) {
    let new_cap = used_cap
        .checked_add(needed)
        .and_then(|required_cap| {
            // 策略1：至少分配 4 个元素
            required_cap.checked_next_power_of_two()
        })
        .unwrap_or_else(|| capacity_overflow());
    
    self.grow_exact(new_cap);
}

分配策略：

• 初始容量：max(4, next_power_of_two(需要的容量))
• 例如：需要 1 个 → 分配 4 个

---

第三章：扩容机制 📈

3.1 扩容触发时机

// push() 检查
if self.len == self.cap {
    // 容量已满，需要扩容
    self.reserve(1);
}

3.2 扩容倍数

fn grow_amortized(&mut self, len: usize, additional: usize) {
    let required_cap = len.checked_add(additional).unwrap();
    let cap = self.cap;
    
    if required_cap > cap {
        // 策略：2 倍扩容
        let new_cap = cmp::max(cap * 2, required_cap);
        self.grow_exact(new_cap);
    }
}

扩容过程：

初始：cap=0, len=0
push(1): 扩容到 cap=4
  [1, _, _, _]

push(2,3,4,5): cap=4 已满，扩容到 cap=8
  [1, 2, 3, 4, 5, _, _, _]

push(6,7,8,9): cap=8 已满，扩容到 cap=16
  [1,2,3,4,5,6,7,8,9,_,_,_,_,_,_,_]

3.3 内存重分配

fn grow_exact(&mut self, new_cap: usize) {
    let elem_size = mem::size_of::<T>();
    let old_layout = Layout::array::<T>(self.cap).unwrap();
    let new_layout = Layout::array::<T>(new_cap).unwrap();
    
    unsafe {
        let new_ptr = if self.cap == 0 {
            // 首次分配
            alloc::alloc(new_layout)
        } else {
            // 重新分配（会复制旧数据）
            alloc::realloc(
                self.ptr.as_ptr() as *mut u8,
                old_layout,
                new_layout.size(),
            )
        };
        
        self.ptr = Unique::new_unchecked(new_ptr as *mut T);
        self.cap = new_cap;
    }
}

realloc 的优化：

• 可能原地扩展（如果后续内存空闲）
• 否则分配新内存并复制

---

第四章：元素操作 🛠️

4.1 push() 详解

pub fn push(&mut self, value: T) {
    // 1. 检查容量
    if self.len == self.cap {
        self.reserve(1);
    }
    
    // 2. 写入元素
    unsafe {
        let end = self.as_mut_ptr().add(self.len);
        ptr::write(end, value);  // 移动语义，不调用析构
    }
    
    // 3. 更新长度
    self.len += 1;
}

4.2 pop() 详解

pub fn pop(&mut self) -> Option<T> {
    if self.len == 0 {
        None
    } else {
        unsafe {
            self.len -= 1;
            let ptr = self.as_mut_ptr().add(self.len);
            Some(ptr::read(ptr))  // 读取并转移所有权
        }
    }
}

关键：ptr::read() 不调用析构函数，转移所有权。

4.3 insert() 详解

pub fn insert(&mut self, index: usize, element: T) {
    assert!(index <= self.len);
    
    if self.len == self.cap {
        self.reserve(1);
    }
    
    unsafe {
        let p = self.as_mut_ptr().add(index);
        // 移动后续元素
        ptr::copy(p, p.add(1), self.len - index);
        // 写入新元素
        ptr::write(p, element);
        self.len += 1;
    }
}

过程：

插入前：[1, 2, 4, 5]
insert(2, 3):
  1. 移动 [4,5] → [_, 4, 5]
  2. 写入 3
结果：[1, 2, 3, 4, 5]

4.4 remove() 详解

pub fn remove(&mut self, index: usize) -> T {
    assert!(index < self.len);
    
    unsafe {
        let p = self.as_mut_ptr().add(index);
        let result = ptr::read(p);  // 读取要删除的元素
        
        // 移动后续元素
        ptr::copy(p.add(1), p, self.len - index - 1);
        
        self.len -= 1;
        result
    }
}

---

第五章：性能优化技巧 ⚡

5.1 预分配容量

// ❌ 慢：多次扩容
let mut v = Vec::new();
for i in 0..1000 {
    v.push(i);  // 可能扩容 8-10 次
}

// ✅ 快：一次分配
let mut v = Vec::with_capacity(1000);
for i in 0..1000 {
    v.push(i);  // 零扩容
}

5.2 批量操作

// ❌ 慢：逐个 push
for item in items {
    v.push(item);
}

// ✅ 快：extend
v.extend(items);  // 批量分配和复制

5.3 避免不必要的 clone

// ❌ 慢：克隆整个 Vec
fn process(v: Vec<i32>) {
    // ...
}
let v = vec![1, 2, 3];
process(v.clone());  // 复制所有元素

// ✅ 快：借用
fn process(v: &[i32]) {
    // ...
}
process(&v);  // 零拷贝

5.4 shrink_to_fit

let mut v = Vec::with_capacity(1000);
v.push(1);
v.push(2);
// 现在 len=2, cap=1000，浪费内存

v.shrink_to_fit();  // 释放多余内存
// 现在 len=2, cap=2

---

总结与最佳实践 🎯

核心设计思想

设计	目的
2倍扩容	摊销 O(1) 时间复杂度
初始容量4	平衡小对象开销
延迟分配	Vec::new() 零成本
realloc	可能原地扩展，减少拷贝

时间复杂度

操作	复杂度	说明
push()	O(1)*	摊销常数
pop()	O(1)	常数时间
insert()	O(n)	需要移动元素
remove()	O(n)	需要移动元素
get()	O(1)	直接索引

性能建议

✅ DO：

• ✅ 已知大小时用 with_capacity()
• ✅ 使用 extend() 批量添加
• ✅ 优先借用而非克隆
• ✅ 用 swap_remove() 替代 remove()（不关心顺序时）

❌ DON’T：

• ❌ 频繁 insert(0, x)（每次 O(n)）
• ❌ 不预分配容量
• ❌ 过早优化（先正确，再优化）

手写简化版 Vec

use std::alloc::{alloc, dealloc, Layout};
use std::ptr;

struct MyVec<T> {
    ptr: *mut T,
    cap: usize,
    len: usize,
}

impl<T> MyVec<T> {
    fn new() -> Self {
        MyVec { ptr: ptr::null_mut(), cap: 0, len: 0 }
    }
    
    fn push(&mut self, value: T) {
        if self.len == self.cap {
            self.grow();
        }
        unsafe {
            ptr::write(self.ptr.add(self.len), value);
        }
        self.len += 1;
    }
    
    fn grow(&mut self) {
        let new_cap = if self.cap == 0 { 4 } else { self.cap * 2 };
        let new_layout = Layout::array::<T>(new_cap).unwrap();
        
        let new_ptr = unsafe {
            if self.cap == 0 {
                alloc(new_layout) as *mut T
            } else {
                let old_layout = Layout::array::<T>(self.cap).unwrap();
                let new_ptr = alloc(new_layout) as *mut T;
                ptr::copy_nonoverlapping(self.ptr, new_ptr, self.len);
                dealloc(self.ptr as *mut u8, old_layout);
                new_ptr
            }
        };
        
        self.ptr = new_ptr;
        self.cap = new_cap;
    }
}

---

最后的话 💝

通过阅读 Vec 源码，我们学到了：

• ✅ 内存管理的精妙设计
• ✅ 性能优化的思考方式
• ✅ 安全与性能的平衡

记住：好的数据结构设计是性能的基础！🚀

---