【在主画面加入捷径】
       
【选择语系】
繁中 简中

Rust 程序设计教学:数组 (Array)、向量 (Vector)和切片 (Slice)

【赞助商连结】

    先前的程序中,变量仅表示单一的实例 (entity) 我们从本章开始,会介绍数种容器 (collections),容器有特定的内部结构,其作用在于装载数据,此外,容器会提供一些方法,让我们藉由操作容器,存取其中的数据。传统上,容器相关的内容多见于介绍数据结构 (data structure) 的书籍,有兴趣的读者可自行查阅相关数据。本章会介绍数组 (array)、向量 (vector) 和切片 (slice)。

    数组

    数组是一种线性的容器,储存同一种类型的数据,而其长度在生成后即固定下来,数组中的数据在内存中是连续而紧密排列的,如下图:

    数组

    数组的好处在于可快速存取数组中的数据,因为数组是透过索引值存取数据,但当要改变数组长度时,效率则较差,因为要复制数组中的数据。

    建立数组

    建立数组有两种方式,一种是直接将数据写在数组中,如以下范例:

    一种则是以 [T; N] (T: 类型,N: 长度) 这种方式初始化数组。范例如下:

    C/C++ 可用动态配置内存产生数组,在 Rust 中相对应的动作是使用向量 (vector)。向量是一种可动态改变大小的线性容器,我们将于下文介绍。

    存取数组数据

    数组使用非负整数作为存取数据的索引 (index),如下例:

    要注意的是,数组的索引值是从 0 开始,对于程序设计初学者来说,时常会觉得容易搞混。一个简单的想法是将索引值视为偏离值 (offset),如下图:

    数组偏离值

    也可将数据存入数组,如下例:

    走访数组

    使用数组等容器的好处之一,在于可以结合循环走访数组中的数据。如果我们想走访数组中的元素,其中一个方法是以数组的索引值来走访数组,如下例:

    或是使用迭代器,如下:

    然而,数组本身不能走访,所以以下程序代码是错误的:

    会引发以下错误讯息:

    如果要在走访数组时,修改其中的数据,可用索引值走访数组,如下:

    如果要使用迭代器,则可修改程序如下:

    其中的 *e 用到参考 (reference) 的概念,简单地说,参考存的是变量在内存中位置,我们透过解参考 (dereferencing) 取得变量本身。我们会于后续章节中介绍参考。

    数组的限制

    目前 Rust 的数组有一些使用上的限制,某些函式在数组长度大于 32 时无法使用。像是下列看起来正常无误的程序代码:

    却引发下列错误:

    这些 trait 的大小限制是 Rust 内部实现的问题,而不是一般程序语言中数组的正常行为,Rust 官方文件也有提到这个议题。在 Rust 改善这点前,我们有几个处理方式,包括:

    1. 自行实现相关 trait
    2. 避免使用这些方法
    3. 改用向量

    (1) 不是通用的方法,因为针对每个长度,都要重新实现一次,但若有需求,仍可考虑;(2) 则会限制了数组的使用场合;通常可考虑 (3)。

    向量

    向量 (vector) 是一种可动态改变长度的线性容器,其内部实现也是数组,但可动态增加长度。由于向量使用方式类似数组,但较数组灵活,实际上,向量使用的场合会比数组多。

    建立向量

    建立向量有两种方式,一种是以 vec! 宏直接建立,一种是先建立空的向量后再陆续加入数据。

    以下程序以 vec! 宏建立 vector:

    以下程序先建立向量后,再加入数据:

    push 的概念是,从向量尾端附加一个新的元素,就像是在一列火车尾端挂载一节车箱般。Rust 的向量从尾端加入数据的效率相当好,可视为常数时间。

    注:以算法的术语来说,为 amortized O(1)。

    存取向量数据

    和数组类似,向量也是以非负整数做为索引。见以下范例:

    同样地,也可以存入数据。如下例:

    走访向量

    类似于数组,如果要走访向量,可以使用数字为索引,如下例:

    或是使用迭代器,如下例:

    如果需要在走访向量时改变其值,可以用索引走访:

    或是使用迭代器:

    同样地,这里用到解参考。

    一些操作向量的方法

    以下用实例来介绍操作向量的方法 (methods):

    由本例,可以看到向量可动态改变长度,而不需手动进行数据的搬移。然而,向量内部仍然是数列,除了从尾端增加数据外,向量在增减长度时会牵涉到数据的拷贝,若有大量数据搬移的需求,可能要考虑改用其他的容器。

    vec.pop().unwrap() 这个部分的程序代码可能会令读者困惑,这是 Rust 的特殊容器 Option。该容器的用途是为了处理错误情形,在从向量尾端取出数据时,有可能取出的值为空值,故 Rust 将值包装在该容器中。这部分牵涉到 enum 的概念,将于后续章节中说明。

    切片

    切片 (slice) 是一种用来间接存取数组或向量的元素的类型,其内部包括指向数组或向量的参考和原本的数组或向量的长度。由于向量使用参考,故不需要拷贝数组或向量的数据。简单地说,切片不存放数据本身,而存放指向数据的内存位置,透过切片,可间接取得数据。

    建立切片

    建立切片的方法是先建立数组或向量后,再建立切片,如下例:

    有 C/C++ 经验的读者可能会觉得困惑,为什么我们可以对值取参考。其实,在内部,Rust 会建立一个暂时变量,再将其参考指向程序设计者指定的变量。

    存取切片数据

    如同数组,切片也可以用索引取出数据,如下例:

    若设定适当的权限,切片也可写入数据,如下例:

    走访切片

    切片的其中一个作用,在于可自动转为迭代器,范例如下:

    如果切片是由数组而来,而原数组元素个数在超过 32 个时,此方法不能使用,见前文说明。经笔者测试,若切片是由向量转来,则没有上述限制。

    设定好权限后,也可以在走访切片时改变其值,范例如下:

    如前述,若切片是由数组而来,同样会受到长度限制的问题。

    (案例选读) 插入排序法

    在本节中我们练习实现插入排序法 (insertion sort)。插入排序法是一种简单易懂的排序算法 (sorting algorithm),对于小型的数据效率佳。实现方式有两种,一种是额外建立一个串行,再将数据依序插入该串行中,一种则是原地修改数组,本节采用后者。

    数组在排序前如下示意图 (摘自维基百科):

    insertion sort (before)

    而排序后如下图 (摘自维基百科):

    insertion sort (after)

    将插入排序法写成伪代码如下:

    同样地,我们的范例程序代码用到 rand 套件,需于 Cargo.toml 中加入相关内容。

    这里附上范例程序代码,以供参考:

    在这里,我们暂不讲解关于函式的部分,而留在后续章节中另行介绍。简单地说,这个函式不受到数组长度的限制,可在终端机印出切片内的数据。对于有 C 程序设计经验的读者,会发现该函式接收切片后可从切片得到其长度,在内部,Rust 的切片和 C 的数组不同,带有长度的资讯。

    除了插入排序法外,还有一些排序算法可以用数组实现,举例如下:

    • Bubble sort
    • Selection sort
    • Bucket sort

    读者有兴趣的话,可自行试着练习看看这些算法。

    【赞助商连结】