Rust常见集合

1. 简介

Rust 标准库中包含一系列被称为「集合」（collections）的非常有用的数据结构。不同于内建的数组和元组类型，这些集合指向的数据是储存在堆上的，这意味着数据的数量不必在编译时就已知，并且还可以随着程序的运行增长或缩小。

2. 向量（vector）

vector 的数据类型为Vec<T>，它允许我们在一个单独的数据结构中储存多于一个的值，它在内存中彼此相邻地排列所有的值。

• vector 只能储存相同类型的值。

2.1 创建向量

创建一个新向量的基本语法示例如下：

// 方式一：新建一个空的向量
let v: Vec<i32> = Vec::new();
// 方式二：使用初始值来新建向量
// vec! 为 Rust 提供的一个宏
let v = vec![1, 2, 3];

【注】在向量的结尾增加新元素时，在没有足够空间将所有所有元素依次相邻存放的情况下，可能会要求分配新内存并将老的元素拷贝到新的空间中。

2.2 更新向量

• 向一个向量末尾追加元素，可以使用 push 方法：

let mut v = Vec::new();
// Rust 根据下面代码可以判断出向量的数据类型
// 故声明时可以不指定向量类型
v.push(5);
v.push(6);

• 向一个向量末尾移除元素，可以使用 pop 方法：

let mut v = Vec::new();
v.push(5);
v.push(6);
v.pop();

【注】要想能够更新向量，必须使用 mut 关键字使其可变。

2.3 读取向量

有两种方法引用向量中储存的值：索引 [] 和 get 方法。

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

let x = &v[100];
let y = v.get(100);

• get 方法返回的是 Option<&T> 类型。
• 使用 [] 方法时，当索引溢出，Rust 会 panic；使用 get 方法时，当索引溢出，Rust 不会 panic，相应地，其返回值为 None 值。

2.4 遍历向量

可以使用 for 循环结构来遍历向量中的每一个元素：

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

3. 字符串（string）

• Rust 的核心语言中只有一种字符串类型：str，即字符串 slice，它通常以被借用的形式出现：&str。字符串 slice 是一些储存在别处的 UTF-8 编码字符串数据的引用。
• String 类型是由标准库提供的，而没有写进核心语言部分，它是可增长的、可变的、有所有权的、UTF-8 编码的字符串类型。
• Rust 标准库中还包含一系列其他字符串类型，比如 OsString、OsStr、CString 和 CStr。

【主】本文主要讨论的是标准库提供的 String 字符串。

3.1 创建字符串

创建一个新字符串的基本语法示例如下：

// 方式一：新建一个空字符串
let mut s = String::new();
// 方式二：从字符串字面值创建字符串
let s = "initial contents".to_string();
let s = String::from("initial contents");

【注】字符串是 UTF-8 编码的，所以可以包含任何可以正确编码的数据。

3.2 更新字符串

• 拼接两个 String 字符串可以直接使用 + 或 format! 宏来实现。

let s1 = String::from("Hello, ");
let s2 = String::from("world!");
let s3 = s1 + &s2; 	// 注意 s1 被移动了，不能继续使用

+ 运算符使用了 add 函数，其函数签名如下：

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

由 add 函数的 s 参数可知：只能将 &str 和 String 相加，不能将两个 String 值相加，而且 add 获取了 self 的所有权。之所以能够在 add 调用中使用 &s2 是因为 &String 可以被强转成 &str。 对于更为复杂的字符串拼接，可以使用 format! 宏，它返回一个带有结果内容的 String，并且不会获取任何参数的所有权。

let s1 = String::from("tic");
let s2 = String::from("tac");
let s3 = String::from("toe");

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

• 向一个字符串末尾追加字符，可以使用 push_str 方法。push_str 方法采用字符串 slice，因为并不需要获取参数的所有权。

let mut s = String::from("foo");
s.push_str("bar");

3.3 索引字符串

Rust 的字符串不支持索引访问字符串字符。这是由于 String 采用 UTF-8 编码，而不同语言字符占用的字节数不同，因此 Rust 无法在常数时间内判断用户期待返回的字符占用的字节数及在字符串中对应的位置。String 是一个 Vec<u8> 的封装，本质上它存储的是一个个 u8 的数值，对字符串长度的计算即是 Vec<u8> 的长度，也就是字符串占用的字节数。

• 虽然 Rust 不支持索引单个字符串，但可以使用 range 来创建包含特定字节的字符串 slice。需要注意的是，range 必须是一个合理的字符边界，即不能在多字节字符中间中断，否则 Rust 会 panic。

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

let s = &hello[0..4];		// Зд

3.4 遍历字符串

• 如果需要操作单独的 Unicode 标量值，可以使用 chars 方法：

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

• 如果需要返回每一个原始字节，可以使用 bytes 方法：

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

4. 哈希表（hash map）

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

• 哈希表可以用于需要任何类型作为键来寻找数据的情况，而不是像数组那样通过索引。
• 类似于向量，哈希表也是同质的：所有的键必须是相同类型，值也必须都是相同类型。

【注】在这三个常用集合中，HashMap 是最不常用的，所以并没有被 prelude 自动引用。

哈希函数

• Rust 中的 HashMap 默认使用一种「密码学安全的」（“cryptographically strong” ）哈希函数，它可以抵抗拒绝服务（Denial of Service, DoS）攻击。
• 不过这并不是可用的最快的算法。如果性能监测显示此哈希函数非常慢，以致于你无法接受，你可以指定一个不同的 hasher 来切换为其它函数。hasher 是一个实现了 BuildHasher trait 的类型。

4.1 创建哈希表

创建一个新哈希表的基本语法示例如下：

use std::collections::HashMap;
// 方式一：新建一个空哈希表
let mut scores = HashMap::new();
// 方式二：使用向量的 collect 方法
// 将两个向量按键值对转化为一个哈希表
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();

【注】_ 用于占位，Rust 能够根据向量中数据的类型推断出 HashMap 所包含的类型。

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

4.2 访问哈希表

• 可以通过 get 方法并提供对应的键来从哈希表中获取值：

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);

• 可以使用与向量类似的方式来遍历哈希表中的每一个键值对，即 for 循环：

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);
}

4.3 更新哈希表

• 覆盖一个值：如果我们插入了一个键值对，接着用相同的键插入一个不同的值，与这个键相关联的旧值将被替换。
• 只在键没有对应值时插入：哈希表有一个特有的 API，叫做 entry，它获取我们想要检查的键作为参数。entry 函数的返回值是一个枚举 Entry，它代表了可能存在也可能不存在的值。

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 方法在键对应的值存在时就返回这个值的可变引用，如果不存在则将参数作为新值插入并返回新值的可变引用。

• 根据旧值更新一个值：另一个常见的哈希表的应用场景是找到一个键对应的值并根据旧的值更新它。比如统计一段文本中每个单词的出现数量：

use std::collections::HashMap;

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;
}

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