20.1 内存申请

首先，我们知道 Vec 是一个动态数组，它会根据情况动态扩展当前的空间大小。 在 Rust 以及 C++ 这样的语言中，动态数组这样的类型是由库来实现的，而不是像某些带 GC 的语言一样由运行时环境内置提供。 这是因为 Rust 和 C++ 一样，都具备对内存的直接控制力，其中一个表现就是，可以手动调用内存分配器，自己管理内存分配和释放的策略。

动态数组类型的基本思想是：它不像内置数组一样直接把数据保存到栈上，而是在堆上开辟一块空间来保存数据，在向 Vec 中插入数据的时候，如果当前已分配的空间不够用了，它会重新分配更大的内存空间，把原有的数据复制过去，然后继续执行插入操作。

在目前版本的标准库中，Vec 类型的源码存在于alloc/vec/mod.rs文件中。 它的定义很简单：

pub struct Vec<T, #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global> {
    buf: RawVec<T>,
    len: usize,
}

它只有两个成员：一个是RawVec<T>类型，管理内存空间的分配和释放；另外一个是usize类型，记录当前包含的元素个数。 Vec 的 new 和 capacity 方法都很简单：

pub fn new() -> Vec<T> {
    Vec {
        buf: RawVec::new(),
        len: 0,
    }
}
pub fn with_capacity(capacity: usize) -> Vec<T> {
    Vec {
        buf: RawVec::with_capacity(capacity),
        len: 0,
    }
}

我们继续深入查看 RawVec 这个类型的 new 和 capacity 方法是如何实现的。 它的源码在alloc/raw_vec.rs文件中：

#[allow(missing_debug_implementations)]
pub(crate) struct RawVec<T, A: Allocator = Global> {
    ptr: Unique<T>,
    cap: usize,
    alloc: A,
}

...

impl<T> RawVec<T, Global> {
    pub const fn new() -> Self {
        Self::new_in(Global)
    }

    pub fn with_capacity(capacity: usize) -> Self {
        Self::with_capacity_in(capacity, Global)
    }
}

从这里可以看到，RawVec的泛型参数比Vec多了一个，这个泛型参数代表的是内存分配器 allocator。 这个设计的目的是让 Rust 的标准容器能像 C++ 中的一样，可以由用户自行指定内存分配器。 这个功能目前还处于设计过程中，因此只有 RawVec 中有这个功能，而 Vec 还没有，以后 Vec 同样也会有这样一个泛型参数的。 这个泛型参数有一个默认值，叫作 Global，是标准库给我们提供的默认内存分配器。一般来说，内存分配器都是0大小的类型，它没有任何成员，不保存任何状态信息。 比如 Global 这个类型的定义：

#[unstable(feature = "allocator_api", issue = "32838")]
#[derive(Copy, Clone, Default, Debug)]
#[cfg(not(test))]
pub struct Global;

继续分析RawVec的new方法。它调用了它自己的new_in方法，并将 allocator 作为参数传递进去。 因为 Global 类型没有成员，所以它可以直接用它的名字当作一个对象实例来使用。 这个new_in方法是这样实现的：

/// Like `new`, but parameterized over the choice of allocator for
/// the returned `RawVec`.
pub const fn new_in(alloc: A) -> Self {
    // `cap: 0` means "unallocated". zero-sized types are ignored.
    Self { ptr: Unique::dangling(), cap: 0, alloc }
}

对于成员ptr以及成员alloc，都是简单的默认构造。 只有成员cap的大小是0，那么显然 Vec 即便不申请任何内存，也可以存下任意多的 T 类型成员。 因为不管你往 Vec 中插入多少数据，总大小依然是0。所以这里的处理逻辑就是，当size_of::<T>()==0的时候，cap的取值是usize::MAX。 这里的!0的写法，实际上是对0按位取反。

再回看 RawVec 的with_capacity方法。它调用了它自己的allocate_in方法。

这个方法的实现如下所示：

fn allocate_in(cap: usize, zeroed: bool, mut a: A) -> Self {
    unsafe {
        let elem_size = mem::size_of::<T>();

        let alloc_size = cap.checked_mul(elem_size).expect("capacity overflow");
        alloc_guard(alloc_size);

        // handles ZSTs and `cap = 0` alike
        let ptr = if alloc_size == 0 {
            mem::align_of::<T>() as *mut u8
        } else {
            let align = mem::align_of::<T>();
            let result = if zeroed {
                a.alloc_zeroed(Layout::from_size_align(alloc_size, align).unwrap())
            } else {
                a.alloc(Layout::from_size_align(alloc_size, align).unwrap())
            };
            match result {
                Ok(ptr) => ptr,
                Err(err) => a.oom(err),
            }
        };

        RawVec {
            ptr: Unique::new_unchecked(ptr as *mut _),
            cap,
            a,
        }
    }
}

#[cfg(not(no_global_oom_handling))]
fn allocate_in(capacity: usize, init: AllocInit, alloc: A) -> Self {
    // Don't allocate here because `Drop` will not deallocate when `capacity` is 0.
    if T::IS_ZST || capacity == 0 {
        Self::new_in(alloc)
    } else {
        // We avoid `unwrap_or_else` here because it bloats the amount of
        // LLVM IR generated.
        let layout = match Layout::array::<T>(capacity) {
            Ok(layout) => layout,
            Err(_) => capacity_overflow(),
        };
        match alloc_guard(layout.size()) {
            Ok(_) => {}
            Err(_) => capacity_overflow(),
        }
        let result = match init {
            AllocInit::Uninitialized => alloc.allocate(layout),
            AllocInit::Zeroed => alloc.allocate_zeroed(layout),
        };
        let ptr = match result {
            Ok(ptr) => ptr,
            Err(_) => handle_alloc_error(layout),
        };

        // Allocators currently return a `NonNull<[u8]>` whose length
        // matches the size requested. If that ever changes, the capacity
        // here should change to `ptr.len() / mem::size_of::<T>()`.
        Self {
            ptr: unsafe { Unique::new_unchecked(ptr.cast().as_ptr()) },
            cap: capacity,
            alloc,
        }
    }
}

首先计算需要分配的内存大小。它使用了checked_mul处理溢出问题。然后考虑0大小的问题。 此时无须调用内存分配器的方法，而是直接返回一个数值很小的指针（一般情况下这个值就是 1）。 为了有利于编译器后端优化，这个指针保证了与 T 类型字节对齐。此时不是直接用数值 0，主要是为了和“空指针”做区分。 因为 RawVec 已经假定了它的成员 ptr 永远不会是空指针，所以它用了 Unique 类型。 这种设计可以让Option<Vec<T>>拥有和Vec<T>相同的大小，而无须浪费空间。

最后我们再来分析一下 RawVec 里面的ptr成员。它是Unique<T>这个类型。

这个类型的定义如下：

pub struct Unique<T: ?Sized> {
    pointer: NonZero<*const T>,
    _marker: PhantomData<T>,
}

这个类型是在裸指针基础上做了一点封装。

• 它通过PhantomData<T>方式，向编译器表达了“它是 T 类型对象的拥有者”这样一个概念。 PhantomData这个类型是一个 0 大小的、被编译器特殊对待的类型，它有一个 attribute 做修饰#[lang="phantom_data"]，凡是被#[lang=…]修饰的东西，都是被编译器特殊处理的，跟普通用户自己定义的不一样。

• 因为从逻辑上说这个指针不应该为空，因此它使用 NonZero 做了一个包装。NonZero 这个类型也是一个特殊类型，它也有一个 attribute 是#[lang="non_zero"]。 在编译器内部，会认为这个类型的取值永远不可能为 0。 这样在某些情况下，编译器可以根据这个信息优化存储空间。比如Option<Box<T>>占据的空间大小跟Box<T>就一模一样，无须额外空间，这里的关键就是Box<T>内部也使用了 NonZero 这个类型。

• Unique<T>还实现了 Send 和 Sync 这两个 trait。 unsafe impl<T：Send+？Sized> Send for Unique<T>{} unsafe impl<T：Sync+？Sized> Sync for Unique<T>{}

标准库中很多底层的数据结构都需要基于裸指针，使用 unsafe 代码才能实现。 而很多数据结构都需要表达一种“对成员拥有所有权”这样一个概念，因此它们有一些共同的代码可以复用。 这就是为什么 RawVec 是基于 Unique 类型而不是直接基于裸指针来实现的原因。 因为抽象出的这样一个 Unique 类型，不止在实现动态数组的时候有用，还可以在实现Box<T>HashMap<K，V>等类型的时候有用。

与之对应的，标准库中还有一个叫作Shared<T>的类型。它也是在裸指针基础上做了一点封装。 它跟Unique<T>之间的主要区别在于，Shared<T>适合用于表达那种“共享所有权的引用”的情况。 比如Rc<T> Arc<T> LinkedList<T>等类型，都是基于Shared<T>实现的。