常见集合（Collections）

发表于 更新于 分类于 ， ，

本文大部分内容翻译自：The Rust Programming Language

Rust标准库中包含一系列被称为集合（collections）的非常有用的数据结构。大部分其他数据类型都代表一个特定的值，集合可以包含多个值。

不同于内建的数组和元组类型，这些集合指向的数据是储存在堆上的，这意味着数据的数量不必在编译时就已知，并且还可以随着程序的运行增长或缩小。

1. Vector

vector允许我们在一个单独的数据结构中储存一个或多个值，所有值在内存中彼此相邻。vector只能储存相同类型的值。

1.1. 新建Vector

创建空vector来存储i32类型的值：

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

注意：这里我们增加了一个类型注解。因为没有向这个vector中插入任何值，Rust并不知道我们想要储存什么类型的元素。

vector是用泛型实现的，Vec<T>是一个由标准库提供的类型，可以存放任何类型。当Vec存放某个特定类型时，该类型位于尖括号中。

有初始值时，就不需要类型注解：

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

Rust提供了vec!宏，会根据我们提供的值来创建一个新的vector。上例中新建了一个包含“1”、“2”、“3”的Vec，推断为 i32是因为这是默认整型类型。

1.2. 更新Vector

用push方法向Vector增加元素：

1
2
3
4
5
6
let mut v = Vec::new();

v.push(5);
v.push(6);
v.push(7);
v.push(8);

1.3. vector离开作用域时元素被释放

类似于任何其他的struct，vector在其离开作用域时会被释放，如示例 8-4 所标注的：

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

    // 处理变量 v
} // <- 这里 v 离开作用域并被丢弃

当vector被丢弃时，它的所有内容也会被丢弃，即它包含的整数将被清理。

1.4. 读取vector中的元素

1.4.1. 索引或get方法

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

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

    match v.get(2) {
        Some(third) => println!("The third element is {}", third),
        None => println!("There is no third element."),
    }
}
  • &和[]返回一个引用
  • get方法以索引作为参数来返回一个Option<&T>

Rust提供了两种引用元素的方法的原因是，当尝试使用现有元素范围之外的索引值时可以选择让程序如何运行。例如：当有一个5个元素的vector访问索引100位置的元素：

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

let does_not_exist = &v[100];
let does_not_exist = v.get(100);
  • 对于第一个[]方法：当引用一个不存在的元素时， Rust会panic。
    • 这个方法更适用于当程序认为，尝试访问超过vector结尾的元素是一个严重错误，应该使程序崩溃
  • get方法被传递了一个数组外的索引：它不会panic，而是返回None。
    • 当出现超过vector范围的访问属于正常情况的时候，可以考虑使用它。
    • 代码中可以有处理Some(&element)或None的逻辑。
      • 例如，索引可能来源于用户输入的数字。如果它们不慎输入了一个过大的数字，那么程序就会得到None值。你可以告诉用户当前vector元素的数量，并再请求他们输入一个有效的值。这就比因为输入错误而使程序崩溃要友好的多。

1.4.2. 遍历vector中的元素

如果想要依次访问vector中的每一个元素，我们可以遍历其所有的元素，无需通过索引一次一个地访问：

1
2
3
4
let v = vec![100, 32, 57];
for i in &v {
    println!("{}", i);
}

也可以遍历可变vector的每一个元素的可变引用来改变他们：

1
2
3
4
let mut v = vec![100, 32, 57];
for i in &mut v {
    *i += 50;
}

为了修改可变引用所指向的值，在使用+=运算符之前，必须使用解引用运算符（*）获取i中的值。

1.5. 使用枚举来储存多种类型

vector只能储存相同类型的值，这是很不方便的，经常会有需要储存一系列不同类型的值的情况。幸运的是，枚举的成员都被定义为相同的枚举类型，所以当需要在vector中储存不同类型值时，我们可以使用枚举。

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

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

Rust在编译时就必须准确的知道vector中类型的原因：

  • 需要知道储存每个元素到底需要多少内存
  • 可以准确地知道这个vector中允许什么类型
    • 如果 Rust允许vector存放任意类型，那么当对vector元素执行操作时，一个或多个类型的值就有可能造成错误
    • 使用枚举外加match意味着Rust能在编译时就保证会处理所有可能的情况

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

2.1. 简介

  • string slices
    • Rust核心语言中只有一种string类型，就是string slice str
    • string slice通常以被借用的形式出现：&str
    • UTF-8编码
    • 字符串字面值（string literals）被储存在程序的二进制输出中，因此它们是string slice
  • String类型
    • 由Rust标准库提供，并没有被编入核心语言
    • 可增长、可变、有所有权、UTF-8编码

2.2. 新建字符串

例：

1
2
3
4
5
6
7
8
9
10
11
12
13
fn main() {
    // 创建空字符串
    let mut s = String::new();

    // 初始化String：用to_string方法
    let data = "initial contents";
    let s = data.to_string();
    // the method also works on a literal directly:
    let s = "initial contents".to_string();

    // 也可以用String::from从字符串字面值创建String
    let s = String::from("initial contents");
}

由于字符串是UTF-8编码的，所以可以包含任何可以正确编码的数据，如：

1
2
3
4
5
6
7
8
9
10
11
12
13
fn main() {
    let hello = String::from("السلام عليكم");
    let hello = String::from("Dobrý den");
    let hello = String::from("Hello");
    let hello = String::from("שָׁלוֹם");
    let hello = String::from("नमस्ते");
    let hello = String::from("こんにちは");
    let hello = String::from("안녕하세요");
    let hello = String::from("你好");
    let hello = String::from("Olá");
    let hello = String::from("Здравствуйте");
    let hello = String::from("Hola");
}

上面都是有效的String类型。

2.3. 更新字符串

可以使用+操作符和format!宏来拼接String。

2.3.1. 使用push_str附加（append）字符串

例：

1
2
3
4
fn main() {
    let mut s = String::from("foo");
    s.push_str("bar"); // push_str接收一个string slice，因为我们不需要获取参数的所有权
}

执行后，s中会包含“foobar”。

在将s2的内容附加到s1后，我们还想继续使用s2：

1
2
3
4
let mut s1 = String::from("foo");
let s2 = "bar";
s1.push_str(s2);
println!("s2 is {}", s2);

如果push_str方法获取了s2的所有权，就不能在最后一行打印出s2的值了。

2.3.2. 使用push附加（append）字符串

push方法获取一个单独的字符作为参数，并附加到String中：

1
2
let mut s = String::from("lo");
s.push('l');

执行后，s会包含 “lol”。

2.3.3. 使用+运算符拼接字符串

例：

1
2
3
4
5
fn main() {
    let s1 = String::from("Hello, ");
    let s2 = String::from("world!");
    let s3 = s1 + &s2; // 注意 s1 被移动了，不能继续使用
}

s3会包含“Hello, world!”。

s1在相加后不再有效的原因，以及使用s2的引用的原因，与使用+运算符时调用的函数签名有关。+运算符使用了add函数：

1
2
fn add(self, s: &str) -> String {
}

这并不是标准库中实际的签名。标准库中的add使用泛型定义，这里我们看到的add的签名使用具体类型代替了泛型，也正是使用 String值调用这个方法时发生的事。这个签名为我们理解+运算符的棘手部分提供了一些线索。

首先，s2使用了&，意味着我们使用第二个字符串的引用与第一个字符串相加。

  • 这是因为add函数的s参数只能将&str和String相加，不能将两个String值相加
  • 但既然&s2的类型是&String而不是&str，为什么上面的例子还能编译呢？
    原因：&String可以被强制转换（coerced）成&str。当add函数被调用时，Rust使用了一个被称为Deref强制转换（deref coercion）的技术。你可以理解为它把&s2变成了&s2[..]。因为add没有获取参数的所有权，所以s2在这个操作后仍然是有效的String。

其次，可以发现签名中add获取了self的所有权，因为self没有使用&。这意味着上例中s1的所有权将被移动到add调用中，之后就不再有效。所以虽然let s3 = s1 + &s2;看起来就像它会复制两个字符串并创建一个新的字符串，但实际上这个语句会获取s1的所有权，附加上从s2中拷贝的内容，并返回结果的所有权。换句话说，它看起来好像生成了很多拷贝，但实际上并没有：这个实现比拷贝要更高效。

2.3.4. 使用format!宏拼接字符串

如果想要级联多个字符串，+ 的行为就显得笨重了：

1
2
3
4
5
let s1 = String::from("tic");
let s2 = String::from("tac");
let s3 = String::from("toe");

let s = s1 + "-" + &s2 + "-" + &s3;

这时s的内容会是“tic-tac-toe”。在有这么多+和"字符的情况下，很难理解具体发生了什么。对于更为复杂的字符串链接，可以使用 format! 宏：

1
2
3
4
5
let s1 = String::from("tic");
let s2 = String::from("tac");
let s3 = String::from("toe");

let s = format!("{}-{}-{}", s1, s2, s3);

上面代码也会将s设置为“tic-tac-toe”。format!与println!的工作原理相同，但不会将输出打印到屏幕上，而是返回一个带有结果内容的String。宏format!生成的代码使用索引，并且不会获取任何参数的所有权。

2.4. 索引字符串

2.4.1. Rust的字符串不支持索引

在 Rust 中，如果你尝试使用索引语法访问 String 的一部分，会出现错误：

1
2
let s1 = String::from("hello");
let h = s1[0];

产生的编译错误：

1
2
3
4
5
6
7
8
9
10
11
12
$ cargo run
   Compiling collections v0.1.0 (file:///projects/collections)
error[E0277]: the type `String` cannot be indexed by `{integer}`
 --> src/main.rs:3:13
  |
3 |     let h = s1[0];
  |             ^^^^^ `String` cannot be indexed by `{integer}`
  |
  = help: the trait `Index<{integer}>` is not implemented for `String`

For more information about this error, try `rustc --explain E0277`.
error: could not compile `collections` due to previous error

错误和提示说明了全部问题：Rust的字符串不支持索引。那么接下来的问题是，为什么不支持呢？为了回答这个问题，我们必须先聊一聊Rust是如何在内存中储存字符串的。

String 是一个Vec<u8>的封装。让我们看一个正确编码的例子：

1
let hello = String::from("Hola");

在这里，len的值是4，意味着储存字符串“Hola”的Vec的长度是四个字节（这里每一个字母的UTF-8编码都占用一个字节）。

那下面这个例子又如何呢？（注意这个字符串中的首字母是西里尔字母的 Ze 而不是阿拉伯数字 3 。）

1
let hello = String::from("Здравствуйте");

当问及这个字符是多长的时候，有人可能会说是12。然而，Rust的回答是24。这是使用UTF-8编码“Здравствуйте”所需要的字节数，因为每个Unicode标量值需要两个字节存储。因此一个字符串字节值的索引并不总是对应一个有效的Unicode标量值。

考虑如下无效的Rust代码：

1
2
let hello = "Здравствуйте";
let answer = &hello[0];

我们已经知道answer不是第一个字符З。当使用UTF-8编码时，З的第一个字节是208，第二个是151，所以answer实际上应该是208，不过208自身并不是一个有效的字母。返回208可不是一个请求字符串第一个字母的人所希望看到的，不过它是 Rust在字节索引0位置所能提供的唯一数据。用户通常不会想要一个字节值被返回，即便这个字符串只有拉丁字母：即便&"hello"[0]是返回字节值的有效代码，它也应当返回104，而不是h。

为了避免返回意外的值并造成不能立刻发现的bug，Rust根本不会编译这些代码，并在开发过程中及早杜绝了误会的发生。

2.4.2. 字节、标量值和字形簇（Bytes and Scalar Values and Grapheme Clusters）

这引起了关于UTF-8的另外一个问题：从Rust的角度来讲，有三种相关方式可以理解字符串：字节、标量值和字形簇（最接近人们眼中字母的概念）。

比如这个用梵文书写的印度语单词“नमस्ते”，最终它储存在vector中的u8值看起来像这样：

1
2
[224, 164, 168, 224, 164, 174, 224, 164, 184, 224, 165, 141, 224, 164, 164,
224, 165, 135]

这里有18个字节，也就是计算机最终会储存的数据。如果从Unicode标量值的角度理解它们，也就像Rust的char类型那样，这些字节看起来像这样：

1
['न', 'म', 'स', '्', 'त', 'े']

这里有六个char，不过第四个和第六个都不是字母，它们是发音符号，本身并没有任何意义。最后，如果以字形簇的角度理解，就会得到人们所说的构成这个单词的四个字母：

1
["न", "म", "स्", "ते"]

Rust提供了多种不同的方式来解释计算机储存的原始字符串数据，这样程序就可以选择它需要的表现方式，而无所谓是何种人类语言。

最后一个Rust不允许使用索引获取String字符的原因是，索引操作预期总是需要常数时间（O(1)）。但是对于String不可能保证这样的性能，因为Rust必须从开头到索引位置遍历来确定有多少有效的字符。

2.5. 字符串slice

索引字符串通常是一个坏点子，因为字符串索引应该返回的类型是不明确的：字节值、字符、字形簇或者string slice。因此，如果你真的希望使用索引创建string slice 时，Rust会要求你更明确一些。

为了更明确索引并表明你需要一个string slice，相比使用[]和单个值的索引，可以使用[]和一个range来创建含特定字节的字符串 slice：

1
2
3
let hello = "Здравствуйте";

let s = &hello[0..4];

这里，s会是一个&str，它包含字符串的头四个字节。之前我们提到了这些字母都是两个字节长的，所以这意味着s将会是“Зд”。

如果获取&hello[0..1]会发生什么呢？答案是：Rust在运行时会panic，就跟访问vector中的无效索引时一样：

1
2
3
4
5
6
$ cargo run
   Compiling collections v0.1.0 (file:///projects/collections)
    Finished dev [unoptimized + debuginfo] target(s) in 0.43s
     Running `target/debug/collections`
thread 'main' panicked at 'byte index 1 is not a char boundary; it is inside 'З' (bytes 0..2) of `Здравствуйте`', src/main.rs:4:14
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

你应该谨慎使用这个操作，因为这么做可能会使你的程序崩溃。

2.6. 遍历字符串

操作字符串每一部分的最好的方法是明确表示需要字符还是字节。对于单独的Unicode标量值使用chars方法。对“नमस्ते”调用 chars方法会将其分开并返回六个char类型的值，接着就可以遍历返回的结果来访问每一个元素了：

1
2
3
for c in "नमस्ते".chars() {
    println!("{}", c);
}

上面代码会打印出如下内容：

1
2
3
4
5
6
न
म
स
्
त
े

另外，bytes方法返回每一个原始字节，可能会适合你的使用场景：

1
2
3
for b in "नमस्ते".bytes() {
    println!("{}", b);
}

上面代码会打印出组成String的18个字节：

1
2
3
4
5
224
164
// --snip--
165
135

不过要注意：有效的Unicode标量值可能会由不止一个字节组成。

从字符串中获取字形簇是很复杂的，所以标准库并没有提供这个功能。crates.io上有些提供这样功能的crate。

3. HashMap - 使用Hash Map储存键值对

3.1. 简介

HashMap<K, V>类型储存了一个键类型K对应一个值类型V的映射。它通过一个哈希函数（hashing function）来实现映射，决定如何将键和值放入内存中。

Hash Map可以用任何类型作为键（key）来寻找数据，而不像vector那样只能通过索引。

3.2. 新建HashMap

3.2.1. new新建空HashMap，insert添加元素

1
2
3
4
5
6
7
8
fn main() {
    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);
}

HashMap没有被prelude自动引用，标准库中对HashMap的支持也相对较少，例如，并没有内建的宏去构建它们。

与vector一样，HashMap将它们的数据储存在堆上。上面HashMap的键类型是String，值类型是i32。HashMap所有的键必须是相同类型，值也必须都是相同类型。

3.2.2. 在元组vector上使用迭代器（iterator）和collect

例：

1
2
3
4
5
6
7
8
9
fn main() {
    use std::collections::HashMap;

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

    let mut scores: HashMap<_, _> =
        teams.into_iter().zip(initial_scores.into_iter()).collect();
}
  • zip方法创建一个元组的迭代器，其中“Blue”与10是一对
  • collect方法将数据收集进一系列的集合类型，包括HashMap
  • HashMap<_, _>类型注解是必要的，因为可能collect为很多不同的数据结构，除非显式指定，否则Rust无从得知你需要的类型。对于键和值的类型参数来说，可以使用下划线占位，Rust能够根据vector中数据的类型推断出HashMap所包含的类型。

3.3. HashMap和所有权

对于像i32这样的实现了Copy trait的类型，其值可以拷贝进HashMap。对于像String这样拥有所有权的值，其值将被移动，而HashMap会成为这些值的所有者：

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

let field_name = String::from("Favorite color");
let field_value = String::from("Blue");

let mut map = HashMap::new();
map.insert(field_name, field_value);
// 这里 field_name 和 field_value 不再有效，
// 尝试使用它们看看会出现什么编译错误！

当insert调用将field_name和field_value移动到HashMap中后，将不能使用这两个变量。

如果将值的引用插入HashMap，这些值本身不会被移动进HashMap，但是这些引用指向的值必须在HashMap有效时也是有效的。

3.4. 访问HashMap中的值

get方法：

1
2
3
4
5
6
7
8
9
10
11
fn main() {
    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);

    let team_name = String::from("Blue");
    let score = scores.get(&team_name);
}

这里，score是与蓝队分数相关的值，应为Some(10)。

  • get返回Option<V>，结果被装进Some
  • 如果某个键在哈HashMap中没有对应的值，get返回None

可以使用与vector类似的方式来遍历HashMap中的每一个键值对，也就是for循环：

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

let mut scores = HashMap::new();

scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);

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

这会以任意顺序打印出每一个键值对：

1
2
Yellow: 50
Blue: 10

3.5. 更新HashMap

3.5.1. 覆盖一个值

1
2
3
4
5
6
7
8
9
10
fn main() {
    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Blue"), 25);

    println!("{:?}", scores);
}

会打印出 {“Blue”: 25}。原来的值“10”被覆盖了。

3.5.2. 在键没有对应值时插入 - entry

1
2
3
4
5
6
7
8
9
10
11
fn main() {
    use std::collections::HashMap;

    let mut scores = HashMap::new();
    scores.insert(String::from("Blue"), 10);

    scores.entry(String::from("Yellow")).or_insert(50);
    scores.entry(String::from("Blue")).or_insert(50);

    println!("{:?}", scores);
}

Entry的or_insert方法：

  • 键对应的值存在：就返回这个值的可变引用
  • 键对应的值不存在：将参数作为新值插入并返回新值的可变引用

上例会打印出 {“Yellow”: 50, “Blue”: 10}。第一个entry调用会插入黄队的键和值50，第二个entry调用不会改变HashMap，因为蓝队已经有了值10。

3.5.3. 根据旧值更新一个值

另一个常见的HashMap的应用场景是找到一个键对应的值并根据旧的值更新它。

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

let text = "hello world wonderful world";

let mut map = HashMap::new();

for word in text.split_whitespace() {
    // 第一次看到某个单词时插入值 0，否则在原值上加1
    let count = map.entry(word).or_insert(0);
    *count += 1;
}

println!("{:?}", map);

上面代码会打印出 {“world”: 2, “hello”: 1, “wonderful”: 1}。

  • split_whitespace方法会迭代text由空格分隔的子slice。
  • or_insert方法返回这个键的值的一个可变引用（&mut V）。
    • 这里我们将这个可变引用储存在count变量中，所以为了赋值必须首先使用星号（*）解引用count。这个可变引用在for循环的结尾离开作用域，这样所有这些改变都是安全的并符合借用规则。

3.6. Hash函数

HashMap默认使用一种叫做SipHash的Hash函数，它可以抵御涉及哈希表（hash table）的拒绝服务（Denial of Service, DoS）攻击。然而这并不是可用的最快的算法，不过为了更高的安全性值得付出一些性能的代价。如果性能监测显示此哈希函数非常慢，以致于你无法接受，可以指定一个不同的hasher来切换为其它函数。

hasher是一个实现了BuildHasher trait的类型。你不需要从头开始实现你自己的hasher，crates.io有其他人分享的实现了许多常用Hash算法的hasher库。

参考资料

[1] 常见集合：https://kaisery.github.io/trpl-zh-cn/ch08-00-common-collections.html