​ 众所周知，std::vec::Vec是Rust中最常用的一种变长数组实现。由于实现了诸多特性，并且可以被方便地解构成Slice，在生产环境中被广泛应用。

​ 和Rust所保证的一致，在常规情况下使用Vec的实现，是不会（或者说极少会）导致内存泄露等问题的。但同时，Vec本身的实现也提供了一些非安全（unsafe）的方法，在此假设读者或多或少已经接触过这些非安全方法，在此基础上对Vec进行介绍。

来自Vec的基本法

​ 很多使用者倾向于把Vec当成黑箱，或者仅仅了解其内存的分配机制，实际上，能够在不了解这些的情况下安全地使用Vec正是达到了其设计目的。但当对Vec的非安全方法有需求时，明白其内部实现就至关重要。实际上，Rust在官方文档中对其实现做了一系列的保证（Guarantees），以防止开发者在非安全情况下使用Vec时踩雷。

Vec的结构

​ Rust对向量结构体的成员结构做了保证——在任意情况下，Vec均由一个三元组(Triplet)组成。这个三元组分别包含了向量的长度(length)——指示目前向量内的有效元素数，容量(capacity)——指示向量目前已分配的总空间，与指向数据的指针(pointer)。并且有以下两点：

  • 指针(pointer)永远是非空的（空指针优化）
  • 不保证三元组变量的顺序

​ 在Rust 1.34.0的标准库中，Vec的定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Vec<T> {
    buf: RawVec<T>,
    len: usize,
}

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

​ 其中，Global是一个默认的全局内存分配实现，其实际大小为0。在RawVec中不占任何空间。在上古版本aplha 1.0中，有一个更加直观的简化定义

1
2
3
4
5
pub struct Vec<T> {
    ptr: NonZero<*mut T>,
    len: uint,
    cap: uint,
}

​ 值得注意的是，两个版本虽然相近，但是len和cap的顺序却被调换了。

​ Unique<T>也是一个很有意思的类型，在此可以暂时看作非空指针。

空间分配与管理

​ 简单来说，向量的空间分配主要存在于两种情况——创建时和扩张时

​ 在创建一个向量时，任何显式或隐式地指定一个空向量的行为会致使空间不被预先分配，此时ptr : Unique<T>为空（即Unique::empty()）。这些行为包括但不限于：

  • 使用Vec::new()初始化

  • 使用vec![]宏

  • 调用Vec::with_capacity(0)

  • 用大小为0的类型作为Vec的泛型参数

    按照Rust文档的定义，在创建时分配内存的前提是有mem::size_of::<T>() * capacity() > 0

    以下是一个段证明代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
pub struct Empty(); // 空类型

fn main() {
    {
        println!("using vec![]");
        let vec: Vec<u8> = vec![];
        println!("  len: {}", vec.len());
        println!("  cap: {}", vec.capacity());
        println!("  ptr: 0x{:x}", vec.as_ptr() as u64);
    }
    {
        println!("using vec![] with elements");
        let vec: Vec<u8> = vec![1];
        println!("  len: {}", vec.len());
        println!("  cap: {}", vec.capacity());
        println!("  ptr: 0x{:x}", vec.as_ptr() as u64);
    }
    {
        println!("using vec::with_capacity(0)");
        let vec: Vec<u8> = Vec::with_capacity(0);
        println!("  len: {}", vec.len());
        println!("  cap: {}", vec.capacity());
        println!("  ptr: 0x{:x}", vec.as_ptr() as u64);
    }
    {
        println!("using 0-sized type");
        let vec: Vec<Empty> = vec![Empty()]; // 此处向量非空
        println!("  len: {}", vec.len());
        println!("  cap: {}", vec.capacity());
        println!("  ptr: 0x{:x}", vec.as_ptr() as u64);
    }
}

​ 获得的输出如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
using vec![]
  len: 0
  cap: 0
  ptr: 0x1
using vec![] with elements
  len: 1
  cap: 1
  ptr: 0x126931d6580
using vec::with_capacity(0)
  len: 0
  cap: 0
  ptr: 0x1
using 0-sized type
  len: 1
  cap: 18446744073709551615
  ptr: 0x1

​ 从输出中，可以看出：

  • 只有以非空的形式初始化向量，才会使向量分配有效内存，否则Vec中的指针为空
  • 以空类型创建向量并不会导致任何空间分配的行为
  • 以空类型创建的向量对应的cap是一个特殊值，对应的是usize::MAX（即2^64 - 1）

​ 除了在创建时分配内存，向量扩张时，如果出现已分配内存不足的情况，将会触发空间分配。这种分配通常会导致内存拷贝的发生。例如，Vec::push的实现有如下判断

1
2
3
4
5
6
pub fn push(&mut self, value: T) {
    // This will panic or abort if we would allocate > isize::MAX bytes
    // or if the length increment would overflow for zero-sized types.
	if self.len == self.buf.cap() {
		self.reserve(1);
	}

​ 这意味着，当对向量元素进行追加时，如果分配的内存已经不足，向量将会自动扩张。

​ Rust并未显式地保证任何扩张策略，但在目前的实现中，只有在临界条件下才会触发扩张，而且扩张的空间则是刚好够新增的元素使用。因此，在实际生产环境中，为了减少内存拷贝的触发次数，推荐预先指定好向量的容量，或者在适当时刻调用reserve以及reserve_exact来预分配内存。

内存的使用原则

  1. 在默认情况下，Vec会保证尽量最小的内存使用量

    1
    2
    3
    4
    5
    6
    7
    fn main() {
        let mut v = vec![0];
        let v2 = vec![0, 2, 3, 7];
        v.extend(v2.iter());
        println!("len of v: {}", v.len());
        println!("capacity of v : {}", v.capacity());
    }

    输出：

    1
    2
    len of v: 5
    capacity of v : 5

  2. Vec不会主动覆写任何已被移出向量元素原空间的内容，但也不保证这些空间不被用作其它用途

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    fn main() {
        let mut v = vec![2333, 3333, 6666];
        let pop_v3 = v.pop();
        let ptr = v.as_ptr();
        let v3 = unsafe {
            std::ptr::read(ptr.add(2))
        };
        println!("{}", pop_v3.expect("should not panic"));
        println!("{}", v3);
    }

    输出：

    1
    2
    6666
    6666

  3. 在保证写入内容有效的情况下，可以通过unsafe的方式在长度以外的范围写入数据，并手动将长度调整至此位置

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    fn main() {
        let mut v: Vec<i32> = Vec::with_capacity(3);
        unsafe {
            let ptr = v.as_mut_ptr();
            std::ptr::write(ptr, 5700);
            std::ptr::write(ptr.add(1), 2600);
            std::ptr::write(ptr.add(2), 3900);
            v.set_len(3);
        }
        println!("{:?}", v)
    }

    输出：

    1
    [5700, 2600, 3900]

  4. 不论何时，Vec所分配的内存都不会被优化到栈上，而是统一从堆上分配。（有一个crate实现了这种优化，可以在GitHub上看到）

  5. 不保证向量中元素被drop的顺序。