Rust 中支持扩容的动态数组

楔子

Rust 标准库包含了一系列非常有用的被称为集合的数据结构，与内置的数组与元组不同，这些集合将自己持有的数据存储在了堆上，这意味着数据的大小不需要在编译时确定，并且可以随着程序的运行按需扩大或缩小数据占用的空间。

不同的集合类型有着不同的性能特性与开销，我们需要学会如何为特定的场景选择合适的集合类型。Rust 当中主要有 3 个被广泛使用的集合：

• 动态数组（vector）：可以让你连续地存储任意多个值；

• 字符串（string）：字符的集合，我们之前提到过 String 类型，后续会更为深入地讨论它；

• 哈希映射（hash map）：可以让你将值关联到一个特定的键上；

本文我们先来介绍动态数组。

创建动态数组

动态数组允许你在单个数据结构中存储多个相同类型的值，这些值会彼此相邻地排布在内存中。动态数组非常适合在需要存储一系列相同类型值的场景中使用，例如商品信息或销售金额等等。

我们可以调用函数 Vec::new 来创建一个空动态数组：

fn main() {
    let v: Vec<i32> = Vec::new();
}

注意这段代码显式地指明了变量的类型，因为我们还没有在这个动态数组中插入任何值，所以 Rust 无法自动推导出我们想要存储的元素类型，这一点非常重要。

另外动态数组在实现时使用了泛型，我们将在后续学习如何为自定义类型添加泛型。但就目前而言只需要知道，标准库中的 Vec<T> 可以存储任何类型的元素，至于我们想存储哪一种，就把 T 换成相应的类型即可。

因此上面的语句向 Rust 传达了这样的含义：变量 v 是 Vec 类型、也就是动态数组，而且数组里面的元素类型是 i32。如果想存储 f64，那么就声明为 Vec<f64> 即可，总之 T 可以代表任意类型，至于到底代表哪一种，就看我们要存储哪一种类型的元素。

不过在实际的编码过程中，只要你向动态数组内插入了数据，Rust 便可以在绝大部分情形下推导出你希望存储的元素类型，我们只需要在极少数的场景中对类型进行声明。

fn main() {
    // 这里没有指定 v 的类型，理论上会报错
    let mut v = Vec::new();
    // 但我们 push 的一个元素
    // 所以 Rust 会将 v 推断成 Vec<i32> 类型
    v.push(123);
}

另外，使用初始值去创建动态数组的场景也十分常见，为此 Rust 特意提供了一个用于简化代码的 vec! 宏。这个宏可以根据我们提供的值来创建一个新的动态数组：

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

由于 Rust 可以推断出我们提供的是 i32 类型的初始值，并进一步推断出 v 的类型是 Vec<i32>，所以在这条语句中不需要对类型进行声明。当然我们也可以显式地标注类型：

fn main() {
    // v 是 Vec<i64> 类型
    let v: Vec<i64> = vec![1, 2, 3];
    // 此时 v2 是 Vec<u8> 类型
    // 因为数组中有一个 u8 类型的整数
    let v2 = vec![1, 2u8, 3];
    // 但是像下面则不行，因为类型冲突了
    // let v3 = vec![1, 2u8, 3u16];
    // let v4: Vec<u16> = vec![1, 2u8, 3];
}

以上就是动态数组的创建，下面来看看如何往动态数组中添加元素。

往动态数组添加元素

如果想往动态数组中添加元素，我们可以使用 push 方法。

fn main() {
    let mut v1: Vec<i64> = vec![1, 2, 3];
    let mut v2: Vec<i32> = Vec::new();

    v1.push(4);
    v2.push(1);
    v2.push(2);
    v2.push(3);
    println!("{:?}", v1);  // [1, 2, 3, 4]
    println!("{:?}", v2);  // [1, 2, 3]
}

为了在创建动态数组后将元素添加至其中，我们可以使用 push 方法。正如之前讨论过的，对于任何变量，只要我们想要改变它的值，就必须使用关键字 mut 来将其声明为可变的。

至于修改动态数组的元素，直接像普通数组那样使用索引去修改即可。

销毁动态数组也会销毁内部的元素

和其他的 struct 一样，动态数组一旦离开作用域就会被立即销毁。

fn main() {
    {
        let mut v1: Vec<i64> = vec![1, 2, 3];
    }  // v1 在这里离开作用域之后会被销毁
}

动态数组中的所有内容都会随着动态数组的销毁而销毁，其持有的整数将被自动清理干净。这一行为看上去也许较为直观，但当接触到指向动态数组元素的引用时就变得有些复杂了，一会儿我们来处理这种情况。

读取动态数组的元素

了解完如何去创建、更新及销毁动态数组，接下来就是读取了。有两种方法可以引用存储在动态数组中的值：

fn main() {
    let v = vec![1, 2, 3];
    // 和数组一样，动态数据也可以通过索引去获取
    let third = v[2];
    println!("第三个元素：{}", third);  // 第三个元素：3

    // 除此之外，还可以通过 get 方法，里面同样传递索引
    // 但是注意：使用 get 方法返回的是 Option<&T>
    let third = v.get(2);
    match third {
        // 显然这里的 i 是一个 &i32
        // 因为 third 是 Option<&i32>
        // 但是我们可以直接打印
        Some(i) => println!("第三个元素：{}", i),
        None => println!("第三个元素不存在")
    }
    /*
    第三个元素：3
    第三个元素：3
     */
}

然后需要注意的是，我们在获取元素的时候尽量获取它的引用，而不是获取值本身，举个例子：

fn main() {
    let v: Vec<String> = vec![String::from("hello")];
    let first = v[0];
}

上述代码是会发生编译错误的，要解释这个问题，我们需要先回顾一下以前的内容。我们说过像整数、浮点数这种数据，它们完全存储在栈上面，而栈上的数据在传递的时候一律会拷贝一份。所以在变量赋值之后，两个变量持有的是不同的数据，因此这两个变量都可以使用，而这样的数据我们称之为是可 Copy 的。

而对于 String 这种数据，都是指针在栈上，然后指针指向堆区的数据。而堆区的数据默认是不会拷贝的，因此变量传递之后，两个变量会引用同一份堆区数据。在 Python 里面会通过引用计数来记录堆数据有几个变量引用它，而 Rust 则是直接转移所有权（操作堆内存的权利），保证同一时刻只能有一个变量可以操作堆内存。

变量的所有权一点转移，那么它就失去了操作堆内存的权利，于是这个变量就不能再用了。等它离开作用域后，把它在栈上的数据销毁即可，至于堆数据和它就没关系了。如果希望它在赋值给别的变量之后还能继续用，那么就调用 clone 方法，把堆上的数据也拷贝一份（Rust 默认不会拷贝堆数据，需要开发者显式调用某个方法进行拷贝）。

因此对于 String 这样的数据，我们说它是可 Clone 的。

所以再来看一下 let first = v[0] 为什么会报错，如果 v 里面的数据是可 Copy 的，那么不会有任何问题，因为大家持有的数据是各自独立的。但现在 v 里面的数据是可 Clone 的，因此只会默认拷贝栈上数据，堆上数据是不会拷贝的，此时只能转移所有权。但问题是，如果一个元素的所有权被转移了， 那么整个数组就都不能用了，举个例子：

fn main() {
    // 变量 a 持有堆内存的所有权
    let a = String::from("hello");
    // 所有权从 a 转移到了 b
    let b = a;

    // b 作为元素放到了动态数组中
    // 显然 b 又将所有权转移给了 v[0]
    let v: Vec<String> = vec![b];
    // 相信上面的逻辑都很好理解，核心就在于
    // 堆内存在同一时刻只能有一个所有者

    // 那么问题来了，下面这段代码为啥会报错呢？
    // 这相当于将所有权又转移给了 first 啊
    let first = v[0];
}

其实这是 Rust 的一个机制，单独的变量在转移所有权的时候是没问题的，但要转移数组某个元素的所有权就不行了。因为一旦某个元素的所有权转移，那么该元素就不能再用了，而它又在数组里面，进而导致整个数组变得不可使用。

这样当我们再使用数组获取其它元素的时候就会报错，而这就会让人产生疑惑，为啥数组好端端的，突然就不能访问了呢？因此为了避免这个隐藏的 bug，Rust 干脆不允许转移数组内部元素的所有权。

因此执行 let first = v[0] 这种代码时，Rust 会认为数组 v 里面的元素都是可 Copy 的，也就是数据全部在栈上，不涉及堆，只有这样这行代码才是成立的。由于数据全部在栈上，那么拷贝完之后，你的是你的，我的是我的，彼此互不影响。而如果不是可 Copy 的，那么 Rust 就会报错。

那么我们该怎么做呢？很简单，获取它的引用不就好了。

fn main() {
    let v = vec![String::from("hello")];
    let first = &v[0];
}

这段代码是没有问题的，因为我们没有获取数组元素的所有权。

当然也可以使用 get，因为它获取的就是引用，并且返回的还是 Option 枚举。当指定的索引超出范围时会返回 None，而不会报出索引越界错误。

fn main() {
    let v = vec![String::from("hello")];
    let first = v.get(0);
    let second = v.get(1);

    for item in [first, second] {
        match item {
            Some(s) => println!("元素存在，内容：{}", s),
            None => println!("元素不存在")
        }
    }
    /*
    元素存在，内容：hello
    元素不存在
    */
}

而如果是通过中括号来访问，那么索引越界就会引发崩溃。

一旦程序获得了数组中某个元素的引用，借用检查器就会执行所有权规则和借用规则，来保证这个引用及其它任何指向这个动态数组的引用始终有效。回忆一下所有权规则，我们不能在同一个作用域中同时拥有可变引用与不可变引用。

而在下面这个例子中，我们持有了一个指向动态数组中首个元素的不可变引用，但却依然尝试向这个动态数组的结尾处添加元素，该尝试是不会成功的。

fn main() {
    let mut v: Vec<i32> = vec![1, 2, 3, 4];
    let first = &v[0];  // 数组第一个元素的不可变引用
    v.push(5);          // 数组的可变引用
    println!("{}", first);
}

编译这段代码将会导致下面的错误：

你也许会好奇，为什么获取第一个元素的引用需要关心动态数组结尾处的变化呢？此处的错误是由动态数组的工作原理导致的：动态数组中的元素是连续存储的，但如果已经没有空间在尾部添加新元素了，那么就需要分配新的内存空间，并将旧的元素移动过去。所以在本例中，第一个元素的引用可能会因为插入行为而指向被释放的内存，借用规则可以帮助我们规避这类问题。

最后还是要指出，get 方法获取的是引用，不管数组的元素是不是可 Copy 的，它获取的都是引用。

fn main() {
    let mut v: Vec<i32> = vec![1, 2, 3, 4];
    // 元素是可 Copy 的，可以直接获取
    // 会拷贝一份
    let first1 = v[0];
    // 使用过 get 获取，会拿到引用
    // 此时数组是不是可 Copy 的，无关紧要
    let first2 = v.get(0);
    match first2 {
        Some(i) => {
            println!("整数的引用可以直接打印: {}", i);
            println!("也可以解引用之后再打印: {}", *i);
        },
        None => ()
    }
    /*
    整数的引用可以直接打印: 1
    也可以解引用之后再打印: 1
    */
}

整个过程应该不难理解。

遍历动态数组的元素

假如你想要依次访问动态数组中的每一个元素，那么可以采用遍历的方式，而不需要使用索引来一个一个地访问它们。

fn main() {
    let v = vec![1, 2, 3];
    for i in v {
        println!("i = {}", i);
    }
    /*
    i = 1
    i = 2
    i = 3
    */
}

遍历方式和 Python 类似，但上面代码存在一个问题，就是在遍历结束之后 v 就不能再用了。因为动态数组是申请在堆上的，在遍历的时候会拿到它的所有权，因此正确的做法应该是获取它的引用，然后遍历。

fn main() {
    let v = vec![1, 2, 3];
    // 如果遍历数组的引用，那么变量 i 对应的也是引用
    // 比如这里的 i 就是 &i32 类型
    for i in &v {
        println!("i = {}, *i = {}", i, *i);
    }
    /*
    i = 1, *i = 1
    i = 2, *i = 2
    i = 3, *i = 3
    */
}

对于整数这样的标量来说，打印它的引用和打印它本身，效果是一样的。但如果要修改的话，就不一样了，举个例子。

fn main() {
    // 首先我们要修改数组里的元素
    // 那么变量必须要加上 mut 声明为可变
    let mut v = vec![1, 2, 3];
    // 如果遍历的是 &v，那么 i 拿到的是 &i32
    // 也就是元素的不可变引用，而我们不可以使用不可变引用去修改值
    // 因此要遍历 &mut v，这样得到每个元素就是 &mut i32
    for i in &mut v {
        // 将每一个元素乘以 2
        // 注意：i 是引用，此时必须要解引用才行
        // 而 i *= 2 显然是不合法的
        *i *= 2;
    }

    // 因为遍历的是引用，所以 v 的所有权并没有被剥夺
    println!("{:?}", v);  // [2, 4, 6]
}

为了使用 *= 运算符来修改可变引用指向的值，我们需要使用解引用运算符（*）来获得 i 绑定的值。如果是打印、调用方法的话，直接使用引用即可，会自动操作指向的值；但对加减法来说，需要先解引用才可以，因为引用直接不能进行运算。

再来总结一下遍历时的注意事项：

1）如果遍历的是 v，也就是动态数组本身，那么遍历结束之后 v 将无效。因为在遍历的时候，它的所有权就被剥夺了。并且无论数组里面的元素是不是可 Copy 的，都无关紧要，如果是可 Copy 的，那么遍历的时候就拷贝一份；不是可 Copy 的，那就获取所有权。咦，之前不是说不能获取所有权吗？很简单，因为之前是单独获取数组的某一个元素，为了不影响整个数组，所以不能让数组元素将所有权交出去。但现在是遍历，由于遍历之后数组就无效了，所以此时允许获取内部元素的所有权。

2）如果遍历的是 &v，那么遍历之后 v 还可以继续使用，因为所有权并没有交出去。并且遍历的是数组的引用，那么拿到的也是数组每一个元素的引用，而且是不可变引用。不管数组里的元素是不是可 Copy 的，拿到的都是引用。这样当遍历结束时，v 还可以继续使用。

3）如果遍历的是 &mut v，那么和遍历 &v 类似，只不过拿到的是元素的可变引用。当然在声明 v 的时候也要使用 mut，因为要获取可变引用，那么变量一定是可变的。不管是变量整体改变（重新赋值），还是修改内部数据，都要声明为 mut。

所以在遍历的时候，细节还是蛮多的。初次接触的时候，很多人都会因为对所有权和引用不是特别熟，而感到难以理解。

最后我们再来补充一点，举个例子：

fn main() {
    let mut v = vec![1, 2, 3];
    // 不管 v 是否可变，都可以拿到它的不可变引用
    // 只是我们不能通过不可变引用，去修改变量的值
    // 即使变量是可变的
    for &i in &v {
        // 然后遍历时使用的是 &i，不是 i
        // 遍历出来的是一个 &i32，那么 &i 的类型就是 &i32
        // 所以 i 就是 i32
    }
}

虽然遍历的是 &v，拿到的是 &i32，但变量是 &i。如果变量是 i，那么显然它是 &i32，这没问题；但如果是 &i，那么 &i 对应 &i32，因此 i 就是 i32。

可能这里有一些绕，总之虽然遍历得到的是引用，但我们可以通过 &i 的方式拿到值。并且通过这种方式遍历，要求数组里的元素是可 Copy 的。因为这种方式的目的很明确，就是在遍历的时候将元素拷贝一份，所以它要求元素必须是可 Copy 的，也就是数据都在栈上，否则报错。

此时就报错了，而且信息很明显，告诉我们元素不是可 Copy 的。因为拷贝的时候只拷贝栈上的数据，而遍历之后的 i 是 String 类型，它的数据还涉及到堆，但 Rust 默认又不会拷贝堆上数据，因此报错。

如果不报错，面对不可 Copy 的数据也允许这种遍历方式的话，那么变量 i 只能将数组里元素的所有权挨个夺走。并且遍历结束之后，数组不能再用了，因为内部的元素都失去所有权了。但我们遍历的是引用啊，而之所以遍历引用，就是为了能在遍历结束之后继续使用数组，所以就矛盾了。于是 Rust 要求元素是可 Copy 的，数据必须全部在栈上，这样拷贝之后彼此互不影响。

以上就是遍历动态数组的一些细节，在初次接触的时候，如果感到有些云里雾里的非常正常。因为 Rust 本身就不好学，我们唯一能做的就是多动手敲一敲。

动态数组结合枚举

在最开始的时候，我们说动态数组只能存储相同类型的值，这个限制可能会带来不小的麻烦，实际工作中总是会碰到需要存储一些不同类型值的情况。但幸运的是，当我们需要在动态数组中存储不同类型的元素时，可以定义并使用枚举来应对这种情况，因为枚举中的所有成员都被视为同一种枚举类型。

假设我们希望读取表格中的单元值，这些单元值可能是整数、浮点数或字符串，那么就可以使用枚举的不同成员来存放不同类型的值。所有的这些枚举成员都会被视作统一的类型：也就是这个枚举类型。然后，我们便可以创建一个持有该枚举类型的动态数组来存放不同类型的值。

enum Cell {
    Int(i32),
    Float(f64),
    Text(String),
}

fn main() {
    let row = vec![
        Cell::Int(33),
        Cell::Float(3.14),
        Cell::Text(String::from("hello world")),
    ];
}

为了计算出元素在堆上使用的存储空间，Rust 需要在编译时确定动态数组的类型。使用枚举的另一个好处在于它可以显式地列举出所有可以被放入动态数组的值类型，然后再搭配 match 表达式，Rust 就可以在编译时确保所有可能的情形都得到妥当的处理。

如果你没有办法在编写程序时穷尽所有可能出现在动态数组中的值类型，那么就无法使用枚举。为了解决这一问题，我们需要用到在后续会介绍的 trait。

以上就是动态数组的内容，当然我们这里都只是介绍了结构本身，其支持的方法我们还没有说，比如除了 push 添加元素，还有 pop 删除末尾的元素等等。我们会抽个时间专门去介绍这些方法，当然这些你也可以从标准库的 API 文档中进行查看。

或者你也可以使用 IDE：

我们看到方法非常多，可以自己试一试。

然后下一篇文章我们来介绍函数与闭包，至于更深入的字符串内容以及 HashMap，以后再介绍。