Rust语言教程(3) - 数组与向量

上一节我们采摘了不少低矮的果实，将其它语言学到的知识迁移到Rust 中来。这一节我们仍然继续采摘。
在数据结构中，最经常使用的就是定长的数组和变长的向量。

数组

Rust的数组除了是把类型和长度放在一个方括号里之外，没有什么特别的。我们直接上例子：

    let mut a_101 : [i32;3] = [0,0,0];
    a_101[0] = 1;
    println!("{:?}",a_101);

如果数组比较长，列举起来比较麻烦，可以采用"[值|长度]"这样的格式来进行初始化：

    let mut a_102 : [i64;100] = [0i64;100];
    a_102[99] = 100_i64;
    println!("{:?}",a_102);

切片

我们可以使用切片来对数组的内容进行操作。切片默认不能修改数据，所以也不需要获取所有权，使用起来跟我们熟悉的语言差不多。

可以采用"[n..]"的方式，取从第n个元素开始到结尾的切片。

例：

    let a_103 = &a_102[1..];
    println!("{:?}",a_103);

这样a_103获取的是一个99个元素的切片。
虽然a_102数组本身是mut可以修改的，但是切片a_103是只读的。

比如我们想给a_103中的下标赋值，就会报错：

174 |     a_103[0] = 1;
    |     ^^^^^^^^^^^^ `a_103` is a `&` reference, so the data it refers to cannot be written

解决方案也很简单，给切片也加上mut就好了。我们看个例子：

    let a_104 = &mut a_102[..10];
    a_104[0] = 0xFF;
    println!("{:?}",a_104);

输出结果为：

[255, 1, 2, 3, 4, 5, 6, 7, 8, 9]

多维数组

数组的元素仍然可以是数组，这样就构成了多维数组。

比如我们先来一个二维的：

let mut a_105 = [[1,2],[3,4]];

我们再堆一个三维的：

    let mut a_106 : [[[i32;2];2];2] = [[[0x55AA;2];2];2];
    println!("{:?}",a_106);

输出结果为：

[[[21930, 21930], [21930, 21930]], [[21930, 21930], [21930, 21930]]]

元素的访问方法也是我们熟悉的方式，我们来看个例子：

    let mut a_105 = [[1,2],[3,4]];
    a_105[0]= [5,5];
    a_105[1][1] = 1i32;
    println!("{:?}",a_105);

    let mut a_106 : [[[i32;2];2];2] = [[[0x55AA;2];2];2];
    a_106[0][0][0]= 0x10;
    println!("{:?}",a_106);

输出结果为：

[[5, 5], [3, 1]]
[[[16, 21930], [21930, 21930]], [[21930, 21930], [21930, 21930]]]

向量

数组一旦在编译期确定，容量就不可变。如果需要动态增删元素，可以使用向量。
向量使用起来很方便，通过vec!宏就可以生成一个空的容器，然后用push方法添加新元素。

我们看个例子：

    let mut vec1 = vec!();
    vec1.push(1);
    vec1.push(2);
    println!("{:?}",vec1);

输出结果为：

[1, 2]

我们也可以使用序列来生成向量：

    let mut vec2 :Vec<i32> = (1..=10).collect();
    println!("{:?}",vec2);

输出结果为：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

向量的长度和容量

与大家可能使用过的容器类似，Rust的向量也有长度和容量两个属性。长度表示当前容器中的元素数量，而容量表示最大容纳的元素数。

我们把上面例子中的向量的长度和容量打印一下：

    let mut vec1 = vec!();
    vec1.push(1);
    vec1.push(2);
    println!("{:?} {} {}",vec1, vec1.len(),vec1.capacity());

我们使用vec!宏而不是直接调用Vec::new其实就隐含了预分配容量的考虑。

如果我们想手动设置初始的容量的话，可以使用Vec的with_capacity方法。

let mut vec3 = Vec::with_capacity(10);

如果想把容量变小，可以再调用truncate方法将其变小，多余的数据将被抛弃。如果truncate的大小超过当前容量，则什么也不会发生。

    let mut vec3 = Vec::with_capacity(10);
    vec3.push(-1.0);
    vec3.truncate(2);
    println!("{:?}",vec3);

向量的切片

向量同样可以用切片进行访问和修改元素，我们看个例子：

    let vs1 = &mut vec1;
    vs1[0] = 100;
    println!("{:?}",vs1);

向量的插入

向量作为一个动态数据结构，当然不只是从末端插入这一种做法，可以从任意位置使用insert方法添加元素。
例：

    vec1.insert(0,100);

向量删除元素

有push，对应就有pop，删除末尾的元素。

我们还以之前的例子为例，pop会将最后push进来的2给pop出来：

    let mut vec1 = vec!();
    vec1.push(1);
    vec1.push(2);
    vec1.insert(0,100);
    let e1 = vec1.pop();
    println!("{:?} {} {}",vec1, vec1.len(),vec1.capacity());
    println!("{:?}",e1);

输出结果为:

[100, 1] 2 4
Some(2)

Some是可选对象，熟悉ocaml的同学应该不陌生，这是一种支持可能为空的结构。

对应于insert的是remove方法，可以指定删除某一位置上的元素。

例：

vec1.remove(1);

与pop不同的是, remove并不返回被删除的对象，删了就是没了。

最后是clear方法，将所有元素都清除掉，恢复成空向量：

vec1.clear()

只保留符合条件的元素

向量提供了retain方法用于只保留符合条件的元素。

比如我们只想保留偶数：

    let mut vec2 :Vec<i32> = (1..=10).collect();
    vec2.retain(|&x| x % 2 == 0);
    println!("{:?}",vec2);

输出结果为：

[2, 4, 6, 8, 10]

交换元素

Vec支持swap方法用于交换两个位置上的元素：

    let mut vec2 :Vec<i32> = (1..=10).collect();
    vec2.retain(|&x| x % 2 == 0);
    vec2.swap(1,2);
    println!("{:?}",vec2);

输出结果就变成：

[2, 6, 4, 8, 10]

反转

Vec支持reverse方法将列表反序，我们还在上面的例子上改造：

    let mut vec2 :Vec<i32> = (1..=10).collect();
    vec2.retain(|&x| x % 2 == 0);
    vec2.swap(1,2);
    vec2.reverse();
    println!("{:?}",vec2);

输出的结果变成：

[10, 8, 4, 6, 2]

排序

Vec支持sort方法对向量进行排序，目前的实现方法是归并排序的一种timsort。这是一种稳定排序，也就是对于值相同的元素，它们之间的原始顺序不会改变。

    let mut vec2 :Vec<i32> = (1..=10).collect();
    vec2.retain(|&x| x % 2 == 0);
    vec2.swap(1,2);
    vec2.reverse();
    vec2.sort();
    println!("{:?}",vec2);

结果又恢复成了[2, 6, 4, 8, 10]。

如果想用快速排序这种不稳定排序的话，Vec也支持一种快速排序的变种unstable_sort方法。这是结合了随机化快速排序和堆排序的一种排序方法，有兴趣的同学可以看下原理：https://github.com/orlp/pdqsort。

例：

vec2.sort_unstable();

这里需要注意一点Rust特色的东西，就是浮点数不能直接调用上面的两个排序方法。因为浮点数中有NaN，而NaN是没有偏序关系的。

口说无凭，我们实际来看一下：

    let mut vec_f = vec!();
    let mut v_1 = 1.0f64;
    for i in 1..=10 {
        vec_f.push(v_1);
        v_1 += 1.0;
    }
    vec_f.sort();

运行结果如下：

error[E0277]: the trait bound `f64: Ord` is not satisfied
   --> src/main.rs:222:11
    |
222 |     vec_f.sort();
    |           ^^^^ the trait `Ord` is not implemented for `f64`

sort需要Ord trait，而f64类型因为NaN的缘故实现不了Ord trait. trait可以先理解为其它语言中的接口或者抽象类。

这咋办呢？特事特办。针对浮点数的集合来说，偏序是实现不了的，但是针对要排序的向量，只要其中不含NaN，我们就可以对其进行排序：

    let mut vec_f = vec!();
    let mut v_1 = 1.0f64;
    for i in 1..=10 {
        vec_f.push(v_1);
        v_1 += 1.0;
    }
    vec_f.sort_by(|a, b| b.partial_cmp(a).unwrap());
    println!("{:?}",vec_f);

输出结果为：

[10.0, 9.0, 8.0, 7.0, 6.0, 5.0, 4.0, 3.0, 2.0, 1.0]

小结

上节我们学习了Rust的基本类型和流程控制语句，加上本节的不可变和可变两种容器数组和向量，有很多逻辑上的代码已经可以开始写了。而且应该还很舒适，没有太体会到Rust与其它语言的不同。