Question

向量（ Vec<T> ） 是标准库提供在堆分配的动态数组。

底层使用普通数组存储单类型元素。

数据结构示意：

  +=====+=====+=====+
  | ptr | cap | len |   stack
  +=====+=====+=====+
   |
   v
  +==========//=====+
  |  array ...    |   heap
  +==========//=====+
  

struct Vec<T> {
  buf: RawVec<T> {
    ptr,
    cap,
  },
  len: usize,
}

• len : 有效元素数量。
• cap : 存储空间大小（单位：元素）。

创建

常见做法是用 vec! 宏以数组相同的方式创建。如元素列表，或初始化值及大小。

let v = vec![1, 2, 3];     // 初始化值列表。
assert_eq!(v, [1, 2, 3]);

let v = vec![1; 3];      // [元素初始化值; 长度]
assert_eq!(v, [1, 1, 1]);

也可以直接调用类型构造。

let mut v: Vec<i32> = Vec::new();

let mut v: Vec<i32> = Vec::with_capacity(10);  // 预分配存储空间。
assert_eq!(v.len(), 0);
assert_eq!(v.capacity(), 10);

操作

使用索引访问元素，可返回元素指针。

fn main() {
  let mut x = vec![1i64; 3];
  x[0] = 100;

  // reference
  let r = &mut x[1];
  *r = 200;

  // pointer
  unsafe {
    let p: *mut i64 = &mut x[2];
    *p = 300;
  }

  assert_eq!(x, [100, 200, 300]);
}

追加或弹出数据。

fn main() {
  let mut v = vec![0; 0];

  v.push(1);
  v.push(2);
  v.push(3);

  assert_eq!(v.pop(), Some(3));
  assert_eq!(v.pop(), Some(2));
  assert_eq!(v.pop(), Some(1));
  assert_eq!(v.pop(), None);
}

方法 get 返回 Option ，如果超出范围则是 None 。

fn main() {
  let v = vec![1, 2, 3, 4, 5];

  // get: returns a reference to an element or subslice
  
  assert_eq!(v.get(1), Some(&2));   
  assert_eq!(v.get(0..2), Some(&[1, 2][..]));

  assert_eq!(v.get(100), None);
  assert_eq!(v.get(100..200), None);
}

引用，遍历（修改）元素。

fn main() {
  let mut v = vec![1, 2, 3, 4];

  for x in &v {
    println!("{:?}", x);
  }

  for x in &mut v {
    *x += 100;
  }
  
  assert_eq!(v, [101, 102, 103, 104]);
}

利用枚举存储不同类型数据。

fn main() {

  #[derive(Debug)]
  enum Value {
    I(i32), F(f64), S(&'static str), 
  }

  let v = vec![Value::I(1), Value::F(2.34), Value::S("abc")];
  println!("{:?}", v);
}

扩容

当元素数量超出底层数组容量（capacity）限制时，重新分配底层数组（2x）。这可能导致元素地址改变，且需要复制数据。所以，提前分配足够空间，有助于提升性能。

fn main() {
  let mut v: Vec<i64> = Vec::with_capacity(2);

  for x in 0..5 {
    v.push(x);
    println!("{:p}, {:?}", &v[0], &v.capacity());
  }
}

$ cargo r

0x55f22a5e29d0, 2
0x55f22a5e29d0, 2
0x55f22a5e2a60, 4
0x55f22a5e2a60, 4
0x55f22a5e2a60, 8

• 对于 vec![] 、 with_capacity(0) 等操作，底层不会为其分配堆内存。
  只有 size_of<T> * cap > 0 时才会实际分配。
• 不会为了优化将元素保存到栈（stack）内存。
• 即便 len == 0 ，也不会自动收缩内存，需手工调用 shrink 操作。

fn main() {
  let mut v = vec![0, 1, 2, 3, 4, 5, 6];

  v.pop();
  v.remove(2);          // 导致 memmove!
  assert_eq!(v.capacity(), 7);

  v.shrink_to_fit();      // 尽可能收缩。
  assert_eq!(v.capacity(), 5);
}