Rust 源码分析之 Vec
原文地址¶
动态数组几乎是每门编程语言都具备的一种容器，Rust 中的动态数组就是 std::vec::Vec<T> 类型。一种堆分配的连续增长的数组类型，它具有 O(1) 的索引复杂度，以及在尾端 O(1) 的插入和删除复杂度。
我们都知道，对于动态数组，若构造的时候没有指定容量的话，肯定是会有一个初始容量的，这个容量不应该太大也不应该太小，否则就可能造成空间浪费或者频繁分配内存；以及在容量用完或将要用完的时候，再往里面插入数据的时候是需要扩容的，那应该扩容多大呢？以及扩容前的数据是怎么处理的呢？这些问题我们都可以通过分析源码的方式得到答案，所谓源码面前，了无秘密。
Vec\<T> 基础速览¶
先看下我们平常是怎么使用 Vec 的，最常见的方式如下：
fn main() {
let mut arr = Vec::new();
arr.push(1);
arr.push(2);
arr.push(3);
assert_eq!(arr[0], 1);
println!("The vector: {:?}",arr);
}
另外就是若你提前知道动态数组的大小，我们还可以使用 Vec::with_capicity() 的方式预分配好对应的内存，如下：
fn main() {
let mut arr = Vec::with_capacity(3);
arr.push(1);
arr.push(2);
arr.push(3);
assert!(arr.capacity() == 3);
println!("The vector: {:?}",arr);
}
当然，若我们还能提前知道动态数组的内容，那还可以直接使用 vec! 宏的方式来进行初始化创建，如下：
fn main() {
let arr = vec![1,2,3];
assert_eq!(arr.capacity(), 3);
println!("The vector: {:?}",arr);
}
不仅如此，我们同样还可以使用 vec! 宏来快速的对一个动态数组中每个元素都进行给定值的初始化设置，这可能比先分配内存然后再用循环进行初始化设置要高效的多，如下对一个长度为 5 的动态数组全部初始化为 0：
对于上面的代码，虽然我们还可以使用 resize() 方法实现，但可能其效率是要比 vec! 宏的方式慢很多。
另外 Vec 可以是可变的，而切片一定是不可变的，要获得 Vec 的切片只需要使用 & 运算即可，得益于它们可变性的不同，对于那种只需要提供读访问的函数参数，推荐都是以切片作为参数。
fn print_slice(slice: &[i32]) {
for val in slice {
print!("{} ", val)
}
}
fn main() {
let mut arr = vec![1,2,3,4,5,6];
print_slice( &mut arr ); // 这里即使误写成 &mut arr, 也不用当心值会被修改
}
上面的例子中，以切片作为参数还有一个好处就是，如果我们的数据不是 Vec 类型，而是数组类型，print_slice 也可以正常工作。这对于 String 和 &str 类型来说也是同样的道理，如果可以的话我们尽量传递字符串切片。
还有一个就是，你可能没有在 Rust 标准库中找到栈这个容器，那是因为栈结构的实现其实是和 Vec<T> 高度重合的，并且 Vec<T> 本身提供了 push() 和 pop() 在尾端进行插入和删除动作。
fn main() {
let mut arr = Vec::with_capacity(3);
arr.push(1);
arr.push(2);
arr.push(3);
while let Some(value) = arr.pop() {
print!("{} ", value);
}
}
// 依次打印出 3 2 1
另外我们可以从 Vec 的文档之中了解到 Vec 的方法非常之多，它也实现了很多 trait，vec.rs 源文件也有三千多行，因此这里我们不打算介绍全部的方法，这样的话，就实在太多了，文章也就没有重点了。所以为了不迷失方向，为了突出我们重点，这篇文章的目的就是主要分析一下 Vec 的构造，扩容机制，插入数据，获取数据以及清空数据等几个比较重要的部分。
Vec\<T> 结构定义¶
首先我们来看一下 Vec<T> 的结构体定义：
这个结构体简直非常简单，就两个字段，一个是 buf 字段用于管理在堆上分配的一块连续内存；一个 len 字段用来表示当前 Vec 的长度。然后它就没了，如此平平无奇。正因为它定义的如此简单，所以我们可以猜到和内存相关的很多事情背后其实都是 RawVec<T> 在管理。因此对 RawVec<T> 还不太了解的同学推荐看 Rust 源码分析之 RawVec 这篇文章。
有了前面对 RawVec<T> 的了解，我们就可以先来看看它的构造函数都有做了些什么吧：
pub const 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 是使用 RawVec::new() 函数构造的一个 RawVec 实例，所以在这里 buf 实际上并没有分配任何的内存，也就是说你使用 Vec::new() 函数构造 Vec 变量的时候并不会有任何内存分配动作发生，直到你往里面插入数据后才会开始分配内存。
而 RawVec::with_capacity(cap) 函数则会分配指定的 cap 大小的内存块，此时它的长度还是 0，容器的容量和容器的长度是两个不同的概念，一个指的是分配的内存块的数量，一个指的是使用的内存块数量，见下图：
还有一个问题就是通过 RawVec::with_capacity(cap) 的方式分配的内存块是没有初始化的，所以理论上通过 Vec::with_capacity(cap) 的方式构造一个 Vec 之后，它指向的内存块中可能还保存有上一个用户的痕迹，其实 RawVec 本身是提供了一个 RawVec::``with_capacity_zeroed(cap) 构造函数可以保证分配的内存会做零初始化，但是 Vec 并没有把这个构造函数向上提供出来。
和 RawVec 的构造对应，Vec 也还有一种构造方式是从已有的内存中开始构造，但是这种方式是不安全的，传入的内存地址，容量，长度等都需要开发者自己保证，一般不推荐使用这种方式进行构建。
#[stable(feature = "rust1", since = "1.0.0")]
pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Vec<T> {
unsafe { Vec { buf: RawVec::from_raw_parts(ptr, capacity), len: length } }
}
Vec\<T> 的插入操作¶
构造完 Vec<T> 之后里面是没有数据的，所以构造完成之后我们就需要往里面添加数据了，Vec<T> 提供了好几种添加数据的方法，比如 push(), insert(), append() 等，下面我们就一一来分析下它们的异同之处。
在尾端插入数据：push 操作¶
首先就是通读一边 push() 的源码并根据理解进行注释：
pub fn push(&mut self, value: T) {
// 若当前长度已经等于当前容量了，也就是没有更多空间可以容纳新 push 的 value 了，
// 这时我们就需要先调用 reserve 函数对容量进行扩容
if self.len == self.buf.capacity() {
// reserve(1) 表示至少要新增1个单位内存块以容纳新 push 的 value
self.reserve(1);
}
unsafe {
// 获取当前内存块首地址并往后偏移到已有数据的下一个地址
let end = self.as_mut_ptr().add( self.len );
// 在指针指向的地址上写入 value 数据
ptr::write(end, value);
// 当前容器长度 + 1
self.len += 1;
}
}
对上面代码进行注释后看起来整个逻辑还是比较简单的：
- 首先判断是否还有剩余空间，若没有则进行扩容操作
- 然后获取首地址并偏移到需要插入值的地址上
- 往指定地址中写入新 push 的值
- 当前长度加 1
后面第二，三，四步都是通过裸指针的方式进行的，没什么不清楚的地方。就是对第一步的扩容部分还是有疑问的，因为注释说的是至少新增一个，那到底是多少个呢？继续分析它的内部实现，我们可以发现它最终调用的是 Raw::grow_amortized() 函数，而该函数我们在之前的 RawVec 源码分析的文章中已经介绍过了，这里不再赘述，只说一下结论：
Vec::reserve 扩容策略***：***首先按原本容量的两倍进行扩容，若原本容量的两倍不能满足要求，则按请求新增的容量大小进行扩容，也就是以请求的为准，并且保证每次扩容的字节不少于 8 字节。
在任意位置插入数据：insert 操作¶
照例是看一边 insert 源码并贴上注释：
pub fn insert(&mut self, index: usize, element: T) {
// 首先就是定义了一个内部函数，并加上了 cold, inline(never) 属性
#[cold] // 表示该函数不太可能会被执行，因此用不同的方式优化和调用
#[inline(never)] // 要求编译器永远不要执行内联展开
fn assert_failed(index: usize, len: usize) -> ! {
panic!("insertion index (is {}) should be <= len (is {})", index, len);
}
// 检查当前插入的位置是否超过当前容器的长度，若超过，则直接 painic 退出
// 注意：这里是插入位置和长度做检查，而不是和容量做检查，所以即使你插入位置
// 没有超过容器容量但超过其长度了也还是会报错并退出
let len = self.len();
if index > len {
assert_failed(index, len);
}
// 这里和 push 操作一样，用于检查是否需要做扩容操作，具体的扩容策略前面也介绍过了。
if len == self.buf.capacity() {
self.reserve(1);
}
unsafe {
{
// 通过裸指针的方式偏移到需要插入的位置
let p = self.as_mut_ptr().add( index );
// 通过裸指针的方式把当前插入位置及其之后的值全部往后挪一个位置
// 这样当前插入位置就空出来了
ptr::copy(p, p.offset(1), len - index);
// 在当前空出的位置上写入要插入的值
ptr::write(p, element);
}
// 当前长度加 1
self.set_len(len + 1);
}
}
分析代码之后整体还是比较简单，相比 push 操作就多了一个插入位置的检查以及挪动 Vec 中元素的操作而已，毕竟 push 只是在尾端插入，而 insert 是在中间插入。
上面图中 ptr::copy 部分只是做一个说明，ptr::copy 内部实现不一定要有 tmp 内存块，也有可能为了性能，ptr::copy 是从重合内存块的尾端到首端反向进行拷贝，这样就不需要中间的临时内存块了。
其实对于上面的代码还有一个疑问，就是为什么 panic 要专门写在一个内部的 assert_failed() 函数中而不是直接调用呢？这不仅让 painic 的行数不准确了，还看不到这样写的好处，有知道的小伙伴还麻烦告知一下。
在尾端插入另一个Vec：append 操作¶
如下是 append 的原码：
pub fn append(&mut self, other: &mut Self) {
unsafe {
self.append_elements(other.as_slice() as _);
// 可以看到，append 操作会影响到被 append 的 vec 本身。
other.set_len(0);
}
}
unsafe fn append_elements(&mut self, other: *const [T]) {
// 获的需要 append 的内存块的长度，并尝试扩容
let count = unsafe { (*other).len() };
// 如果 len + count < cap，实际上就不会有扩容动作
self.reserve(count);
let len = self.len();
unsafe {
// 把从 other 内存首地址开始的连续 count 个内存块全部依次拷贝到当前容器的尾端
ptr::copy_nonoverlapping(other as *const T, self.as_mut_ptr().add(len), count)
};
// 当前长度值加上 count
self.len += count;
}
这个插入操作可能需要注意的就是使用它之后，被 append 的 Vec 的长度就会被置为 0，也就是说里面的元素虽然还在，但已经不可用了，只能当作是一个未初始化的新的 Vec 变量去使用了。
另外一个值得说明的地方就是 ptr::copy_nonoverlapping 这个函数了，它其实和 ptr::copy 的作用是类似的，但是前者用于没有重合的 buff 间的拷贝，后者用于有重合的 buff 间的拷贝。
http://152.69.196.199/usr/uploads/2021/05/3366020655.png)
除了上面三个外，其实 Vec 还提供了 extend(), extend_from_slice() 等几个用于插入的函数，这里也不再详细赘述， 下面我就接着分析 Vec 提供了哪些获取数据的方法。
从 Vec\<T> 获取数据¶
一味的往 Vec 中添加数据而不使用，这样的程序就是没有意义的，所以我们还需要了解一下 Vec 中都有哪些获取数据的方式，以及它们的内部实现。
获取尾端数据：pop 操作¶
pub fn pop(&mut self) -> Option<T> {
if self.len == 0 {
None
} else {
unsafe {
self.len -= 1;
Some(ptr::read(self.as_ptr().add(self.len())))
}
}
}
可以看到，从 Vec 中获取数据要比往里面添加数据简单的多，首先判断当前长度是否为 0，是的话，就直接返回 None 表示当前没有任何数据；否则的话，就将当前长度减 1 之后定位到容器的尾端，并读取其中的值然后返回即可，之所以先减 1，是因为我们的索引是从 0 开始的。
获取任意位置的数据：[], get, get_unchecked 操作¶
可以看到，前面的 pop() 调用之后，最后一个元素会被丢掉，并且它也只能得到最后一个位置的元素，这有时可能并不是我们想要的，所以 Vec 还有其他方法访问容器中的数据，比如像数组那样使用中括号索引 []， get()， get_mut()， get_unchecked()，以及 get_unchecked_mut() 等方式访问任意位置的值。 实际上这些方法其实是数组类型提供的，但因为 Vec 实现了 Deref trait 可以在需要的时候转换成数组，所以 Vec 也可以直接使用数组的这些方式进行取值操作。
impl<T> ops::Deref for Vec<T> {
type Target = [T];
fn deref(&self) -> &[T] { // Vec<T> 会解引用成 &[T] 类型
unsafe { slice::from_raw_parts(self.as_ptr(), self.len) }
}
}
就上面这几行代码，Vec<T> 就拥有了数组切片 &[T] 的所有功能。并且得益于 Rust 的自动解引用功能，你使用的时候根本感受不到这其实是数组而非 Vec 的方法。
Vec\<T> 的清空操作¶
最后我们再来看看 Vec 中清除数据的相关方法，从这些方法的实现中，我们可以知道 Vec 是否会释放它已分配的内存以及对应的数据等信息。
截断 Vec\<T> 中数据：truncate 操作¶
vec::truncate(len) 方法的作用就是在第 len 个元素的位置进行截断，并保留前 len 个元素，清除剩下的所有元素，它的原码如下：
有了前面 truncate 操作，那清除所有元素其实就是在 0 的位置进行截断而已，事实也确实是这样，下面就是 clear 操作的实现。
清除指定位置的元素：remove 操作¶
前面 truncate 操作相当于把 Vec 一分为二，然后把后半区间整个丢掉，但有时我们只是想丢弃某个位置的某一个值而已，这就是 remove 操作的作用了。