50、动态数组（Vectors）

Vectors

静态数组的优点也是他们的缺点：他们的大小必须在编译时预先知道。如果我们尝试创建一个大小仅在运行时已知的数组，我们将会收到编译错误：

let n = 10;
let numbers: [u32; n];

error[E0435]: attempt to use a non-constant value in a constant
 --> src/main.rs:3:20
  |
2 | let n = 10;
3 | let numbers: [u32; n];
  |                    ^ non-constant value

静态数组并不适合我们的票据管理系统——我们不知道在编译时需要存储多少tickets。显然，动态数组Vec更适合这一点。

Vec

Vec是一种可以“增长”的数组类型，由标准库提供同。我们可以使用Vec::new函数创建一个空数组：

let mut numbers: Vec<u32> = Vec::new();

然后使用push方法将元素push到vector里：

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

新值将添加到vector的末尾。

如果在创建的时候知道值，我们也可以使用vec!宏创建vector。

let numbers = vec![1, 2, 3];

访问元素

用于访问元素的语法与数组相同：

let numbers = vec![1, 2, 3];
let first = numbers[0];
let second = numbers[1];
let third = numbers[2];

注意：索引必须是usize类型

我们也可以使用get方法，该方法的返回值是Option<&T>：

let numbers = vec![1, 2, 3];
assert_eq!(numbers.get(0), Some(&1));
// You get a `None` if you try to access an out-of-bounds index
// rather than a panic.
assert_eq!(numbers.get(3), None);

访问时会进行边界检查，就像数组中的元素那样，它具有O(1)的时间复杂度。

内存分布

Vec是一个heap-allocated（堆分配）的数据结构。

当我们创建Vec时，它会在堆上分配内存来存储元素。

如果我们运行这个代码：

let mut numbers = Vec::with_capacity(3);
numbers.push(1);
numbers.push(2);

我们可以得到以下的内存布局：

Vec可以跟踪三件事：

• 指向预留的堆区域的指针。
• vector的长度，即vector中有多少个元素
• vector的容量，即堆上保留的空间中可以容纳的元素数量

这个布局看起来很熟悉：它跟String完全一样！

这不是一个巧合：在幕后，String被定义为bytes vector（字节vector）Vec<u8>：

#[derive(PartialEq, PartialOrd, Eq, Ord)]
#[stable(feature = "rust1", since = "1.0.0")]
#[lang = "String"]
pub struct String {
    vec: Vec<u8>,
}

练习

这一节的练习是让我们实现一个斐波那契数列，经典老题了啊。

我也是简单编写了一个函数，算是完美使用到了vec的动态这个特性吧：

// Given a number `n`, return the `n+1`th number in the Fibonacci sequence.
//
// The Fibonacci sequence is defined as follows:
//
// - The first number of the sequence is 0.
// - The second number of the sequence is 1.
// - Every subsequent number is the sum of the two preceding numbers.
//
// So the sequence goes: 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on.
//
// We expect `fibonacci(0)` to return `0`, `fibonacci(1)` to return `1`,
// `fibonacci(2)` to return `1`, and so on.
pub fn fibonacci(n: u32) -> u32 {
    // TODO: implement the `fibonacci` function
    //
    // Hint: use a `Vec` to memoize the results you have already calculated
    // so that you don't have to recalculate them several times.

    if n == 0 {
        0
    } else {
        let mut nums = Vec::new();
        nums.push(0);
        nums.push(1);
        for i in 1..n {
            nums.push(nums[nums.len() - 1] + nums[nums.len() - 2]);
        }
        *nums.last().unwrap()
    }
}

这一节的学习就先到这了。