fuchencong

The way I am

0%

Rust 权威指南（07）：通用集合类型

发表于 分类于

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

使用动态数组存储多个值

动态数组 Vec 允许在单个数据结构中存储多个相同类型的值。这些值会彼此相邻地排布在内存中。

创建动态数组

使用如下方式创建一个动态数组：

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

这段代码必须显示增加一个类型标记，因为还没有在这个动态数组中添加任何值，Rust 无法自动推导出想要存储的元素类型。只要向动态数组中插入数据，Rust 绝大多时候能够推到出你希望存储的元素类型。

Rust 提供了使用初始值去创建动态数组的语法：

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

此时 Rust 将 v 推到为 Vec<i32>。

更新动态数组

使用 push 方法在动态数组中添加元素

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

    v.push(4);
    v.push(5);
    v.push(6);
}

读取动态数组中的元素

有两种方法可以读取动态数组中的元素：使用索引和 get 方法：

1
2
3
4
5
6
7
8
9
10
11
fn main() {
    let v = vec![1, 2, 3, 4];

    let third: &i32 = &v[2];
    println!("the third element is {}", third);

    match v.get(2) {
        Some(third_ele) => println!("the third element is {}", third_ele),
        None => println!("there is no third element"),
    }
}
  • 动态数组使用数字进行索引，索引值从 0 开始
  • 使用 & 和 [] 会直接返回元素的引用，而 get() 则会返回一个 Option<&T>
  • 当使用对应元素不存在的索引值去读取动态数组时，直接索引法会导致程序 panic，而 get 方法则返回 None

动态数组一旦离开作用域就会被立即销毁，其持有的元素也会随之销毁。

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

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

    let third: &i32 = &v[2];

    v.push(6);
    println!("the third element is {}", third);
}

编译该代码将导致如下错误：

1
2
3
4
5
6
7
4 |     let third: &i32 = &v[2];
  |                        - immutable borrow occurs here
5 |
6 |     v.push(6);
  |     ^^^^^^^^^ mutable borrow occurs here
7 |     println!("the third element is {}", third);
  |                                         ----- immutable borrow later used here

这里 v.push() 需要使用 v 的可变引用，而之前 third 则是数组第 3 个元组的不可变引用，借用规则可以帮忙规避如下问题：由于动态数组是连续存储的，插入新的元素后也许没有足够多的空间将所有元素依次相邻地放下，此时就需要重新分配内存空间，并将旧的元素移动到新的空间上。此时 third 的引用可能会因为插入行为而指向被释放的内存。

遍历动态数组中的值

可以使用如下方式直接遍历动态数组中的元素，此时将获得每一个元素的不可变引用：

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

    for i in &v {
        println!("{}", i);
    }
}

如果要修改数组的元素，可以使用 &mut v 的方式获得元素的可变引用：

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

    for i in &mut v {
        *i += 1;
    }
}

这段代码中首先需要使用解引用运算符（*）来获取 i 的绑定值。

使用枚举来存储多个类型的值

动态数组只能存储相同类型的值，当我们需要在动态数组中存储不同类型时，可以定义并使用枚举来应对该情况，因为枚举中的所有变体都被定义为同一种枚举类型。

1
2
3
4
5
6
7
8
9
10
11
enum SpreadsheetCell {
    Int(i32),
    Float(f64),
    Text(String),
}

let row = vec! [
    SpreadsheetCell::Int(3),
    SpreadsheetCell::Float(3.5),
    SpreadsheetCell::Text(String::from("test"))
];

如果无法在编写程序时穷尽所有可能出现的在动态数组中的值类型，那么就无法使用枚举。

使用字符串存储 UTF-8 编码的文本

字符串本身就是基于字节的集合，并通过功能性的方法将字节解析为文本。Rust 在语言核心中只有一种字符串类型，即字符串切片 str，它通常是以借用的形式（&str）出现。字符串切片是一些指向存储在别处的 UTF-8 编码字符串的引用（例如字符串字面量是存储在程序的二进制文件中，因此它们本身也是字符串切片的一种）。

String 类型定义在 Rust 标准库中而不是内置在语言的核心部分。

创建一个新的字符串

如下展示了如何创建一个新的 String：

  • 使用 String::new() 创建一个空的字符串，或者使用 String::from() 来基于字符串字面量生成 String
  • 对于那些实现了 Display trait 的类型可以调用 to_string 方法
1
2
3
4
5
6
fn main() {
    let s1 = String::new();

    let data = "initial contents";
    let s2 = data.to_string();
}

字符串是基于 UTF-8 编码，可以将任何合法的数据编码进字符串中。

更新字符串

String 的内容可以修改：

  • 可以使用 push_str() 向 String 中添加一段字符串切片
  • push() 接受单个字符作为参数，并将它添加到 String 中
  • 可以使用 + 运算符或者 format! 宏来拼接字符串

注意 + 运算符会调用一个 add 方法，它的签名类似：

1
fn add(self, s: &str) -> String
1
2
3
let s1 = String::from("A");
let s2 = String::from("B");
let s3 = s1 + &s2;

也就是说执行 s3 = s1 + &s2 时，在加法操作中仅对 s2 采用引用，而 self 则在加法操作之后不再生效，因此最终这条语句会取得 s1 的所有权，再将 s2 的内容复制到其中，最后再将 s1 的所有权作为结果返回。需要注意，**虽然 s 的参数类型是 &str，但是依然可以传递 &String 类型的参数，因为编译器会自动将 &String 类型的参数强制转换为 &str 类型。当调用 add 函数时，Rust 使用一种被称为 解引用强制转换 的技术，将 &s2 转换为 &s2[..]**。

对于复杂字符串的合并，可以使用 format! 宏，它会将结果包含在一个 String 中返回。

字符串索引

Rust 中的字符串并不支持索引，在 Rust 中使用索引语法去访问 String 中的内容，会收到错误提示。String 实际上是一个基于 Vec<u8> 的封装类型，对字符串中的字节索引并不总是能对应到一个有效的 Unicode 标量值。

1
2
3
4
5
6
fn main() {
    let s1 = String::from("ab");
    let s2 = String::from("中文");

    println!("{} {}", s1.len(), s2.len());
}
1
2
# cargo run
2 6

使用 UTF-8 编码还会引发另外一个问题，在 Rust 中实际可以通过 3 种不同的方式来看待字符串中的数据：字节、标量值（Unicode 标值，即 Unicode 中的 char 类型）和字形簇（即符合人类的字符概念）。字符串索引操作应该返回的类型是不明确的（字节、Unicode 码值、还是真正的文字字符），所以 Rust 直接拒绝对字符串进行索引。

字符串切片

如果真的想要使用索引来创建字符串切片，Rust 会要求你做出更加明确的标记。为了明确表明需要一个字符串切片，需要在索引的 [] 中填写范围来指定所需的字节内容，而不是在 [] 中使用单个数字进行索引。但是仍然要小心谨慎地使用范围语法来创建字符串切片，错误的范围会导致程序崩溃。

1
2
3
4
5
6
fn main() {
    let s1 = String::from("中文");

    println!("{}", &s1[0..3]);
    println!("{}", &s1[0..2]);
}
1
2
3
# cargo run
中
thread 'main' panicked at 'byte index 2 is not a char boundary; it is inside '中' (bytes 0..3) of `中文`', src/main.rs:5:21

遍历字符串的方法

Rust 提供了不同的方式来解析存储在计算机中的字符串数据，程序员可以自行选择所需要的解释方式：

  • 如果想要遍历每个 Unicode 标量值，可以对字符串调用 chars()。合法的 Unicode 标量值可能会需要占用 1 字节以上的空间
  • bytes() 方法则会依次返回每个原始字节
  • 从字符串中获取文字字符则相对复杂，标准库没有提供该功能，有这方面的需求可以从 crates.io 获取开源库
1
2
3
4
5
6
7
8
9
10
11
fn main() {
    let s1 = String::from("中文");

    for c in s1.chars() {
        println!("{}", c);
    }

    for b in s1.bytes() {
        println!("{}", b);
    }
}

在哈希映射中保存键值对

哈希映射 HashMap<K, V> 存储了从 K 类型键到 V 类型值之间的映射关系。当你不仅仅满足使用索引（动态数组）而需要使用特定的类型作为键来搜索数据时，哈希映射就会显得特别有用。

Rust 没有将 HashMap 包含在预导入模块中，所以使用哈希映射时需要将 HashMap 引入到当前作用域中。Rust 也没有提供一个可以用于构建哈希映射的内置宏。

创建一个新的哈希映射

和动态数组一样，哈希映射也将其数据存储在堆上。有两种方法来创建哈希映射

  • 使用 HashMap::new() 创建一个空的哈希映射，并使用 insert 方法来添加元素
  • 在一个由键值对组成的元组动态数组上使用 collect 方法。collect 方法可以将数据收集到很多数据结构中，这些数据结构也包括 HashMap
1
2
3
4
5
6
7
8
use std::collections::HashMap;

fn main() {
    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);
}
1
2
3
4
5
6
7
8
use std::collections::HashMap;

fn main() {
    let teams = vec![String::from("Blue"), String::from("Yellow")];
    let initial_scores = vec![10, 50];

    let scores: HashMap<_, _> = teams.iter().zip(initial_scores.iter()).collect();
}

这里的 HashMap<_, _> 不能省略，因为 collect 可以用作许多不同的数据结构，如果不指明类型的话，Rust 无法知道我们具体想要的类型。但是对于键值对的类型参数，可以使用 _ 占位，Rust 能够自动根据动态数组中的数据类型来推断出哈希映射所包含的类型。

哈希映射与所有权

对于实现了 Copy trait 的类型，它们的值会简单地复制到哈希映射中。而对于 String 这种持有所有权的值，其值会将会转移且所有权会转移给哈希映射中。如果只是将值的引用插入到哈希映射中，值是不会被转移到哈希映射中。这些引用所指向的值必须要保证，在哈希映射有效时自己也是有效的。

1
2
3
4
5
6
7
8
9
10
use std::collections::HashMap;


fn main() {
    let key_field = String::from("color");
    let value_field = String::from("blue");

    let mut map = HashMap::new();
    map.insert(key_field, value_field);
}

访问哈希映射中的值

可以通过将键传入 get 方法来获得哈希映射中的值，它返回一个 Option<&V>。也可以使用 for 循环来遍历哈希映射中的所有键值对（顺序不固定）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
use std::collections::HashMap;

fn main() {
    let key_field = String::from("color");
    let value_field = String::from("blue");

    let mut map = HashMap::new();
    map.insert(key_field, value_field);

    let k = String::from("color");
    let v = map.get(&k);
    println!("{:?}", v);

    for (key, value) in &map {
        println!("{}: {}", key, value)
    }
}

更新哈希映射

HashMap 中每个键任意时刻只能对应一个值。

  • 当我们将一个键值对插入到哈希映射后，接着使用同样的键并配以不同的值来继续插入，之前的键所关联的值就会被替换掉
  • entry() 可以接受键作为参数，并返回一个 Entry 枚举作为结果，它指明了键存在的是否存在。Entry 的 or_insert() 方法被定义为返回一个 Entry 键所指向值的可变引用。当这个值不存在时，就将参数作为新值插入到哈希表中，并将这个新值的可变引用返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();

    map.insert(String::from("yellow"), 10);
    map.insert(String::from("yellow"), 20);
    println!("{:?}", map);

    map.entry(String::from("yellow")).or_insert(50);
    map.entry(String::from("blue")).or_insert(50);
    println!("{:?}", map);
}
1
2
{"yellow": 20}
{"yellow": 20, "blue": 50}

下面的代码也展示了如何使用 Entry 来更新值：

1
2
3
4
5
6
7
8
9
10
11
12
13
use std::collections::HashMap;

fn main() {
    let text = "hello world wonderful world";

    let mut map = HashMap::new();

    for word in text.split_whitespace() {
        let count = map.entry(word).or_insert(0);
        *count += 1;
    }

}

哈希函数

为了提供 DoS 能力，Hashmap 默认使用了一个在密码学上安全的哈希函数，它确实不是最快的哈希算法，如果默认的哈希函数成为你的性能热点，你也可以指定其他哈希计算工具（实现了 BuildHasher trait 的类型）。