Skip to main content

常用集合类型

Rust 标准库中包含许多集合数据类型方便使用. 这些集合都是在堆上分配内存的, 这些集合类型如下:

  • vector: 用于存储可变数量的值
  • string: 表示字符的集合
  • hash map: 通过哈希实现键定位的字典

Vector 的用法​

vector 是顺序表的实现, 值在内存中的地址是连续的.

使用如下语法创建 vector:

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

// 或使用 Rust 的宏创建:
let v = vec![1, 2, 3];

更新 Vector:

let mut v = vec![1, 2, 3];
v.push(5);
v.push(6);
v.push(7);

读取 Vector 指定下标的值有如下两种方式:

let v = vec![1, 2, 3];
let third = &v[1];  // &i32
let third_get = v.get(1);   // Option<&i32>

根据当前情况自由选择使用 get 或直接下标访问, 使用下标的好处是清晰易懂, 但越界会有 panic, 使用 get 的话更安全, 越界的话会返回 None.

使用 Vector 时候的 ownership 和 borrow 规则和普通类型一致, 比如下面的代码会出现编译错误:

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

let third = &v[2];  // 元素的不可变引用

v.push(4);          // Vec 的可变引用 `&mut self`, 同时存在会编译出错

println!("third {}", third);

原因是: vector 是顺序表的实现, 在堆内存中分配元素空间, 当 vector 是可变时, 添加元素或删除元素可能导致容量变化的数组复制扩容/压缩操作, 此时如果允许 v 的元素不可变引用和 v 的可变引用(调用 push 时传入的 &mut self), 则在扩容时 third 引用的内存实际是被释放了的, 造成访问已被释放内存的问题. 因此在这里不能有元素的不可变引用和 Vector 的可变引用同时存在.

Vec 类型的实现详见官方文档

遍历 Vector 的方法如下:

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

可以在遍历过程中同时修改 Vec 每个元素(并非修改 Vec 本身, 只是对每个元素修改):

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

由于没有在遍历过程中对 vec 进行增删等修改, 因此元素修改本身是内存安全的. 在 for 循环遍历的过程中, for 循环可以保证不会同时修改整个 vector(修改的话就会编译出错).

可以在 Vector 中放入任意类型, 比如 enum 的例子如下:

enum MyEnum {
    Int(i32),
    Text(String),
    Float(f64),
}

let v = vec![
    MyEnum::Int(3),
    MyEnum::Text(String::from("hello")),
    MyEnum::Float(3.33),
];

Rust 需要在编译时获知将要放入到 Vector 中的数据类型, 这样才可以确定在每个元素在堆中分配的大小, 并且需要是相同类型的元素.

比如放入 String 的话实际是 String 的指针, 指针指向实际放 String 的堆内存区域.

Vec 的重要性质: 当 Vec 被 Drop 时会 Drop 它的所有元素(意味着所有元素的 Owner 是这个 Vec, 类似 struct 的情况, 所有成员的 Owner 都是那个 struct 对象). Borrow checker 可以保证 vector 的任意元素只有在 vec 存在时才可用.

String: UTF-8 编码的字符集合​

Rust 中 String 实际实现为字节集合, 在其上提供若干对字节处理为字符的方法.

那什么是 String 呢? 在 Rust Core 中只有一种 String 类型, 即字符串切片 str 和切片引用 &str. 而 String 类型是由 Rust 标准库提供的, 而非由 Rust 语言本身提供. String 是一种可扩展, 可变, 且在堆内存分配的 UTF-8 编码字符串类型. String 类型和字符串切片类型都是 UTF-8 编码的.

创建字符串​

let mut s = String::new(); // s 是一个空字符串.

在任意实现了 Display 的类型上, 都可以调用 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();

还可以通过 from 方法创建字符串:

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

修改字符串​

可以通过如下方式修改字符串:

let mut s = String::from("foo");
// 通过 push 追加
s.push_str("bar");

// 通过 push_str 追加字符串切片到字符串. 且追加切片时, 不会进行 move 转移所有权.
// 因为切片所在的内存区域并非堆上, 而是在文本段中.
let s2 = "bar";
s1.push_str(s2);

// 追加字符到字符串:
let mut s = String::from("lo");
s.push('l');

字符串拼接操作符 + 的工作原理​

可以通过 + 操作符拼接字符串:

// 使用 `+` 操作符拼接字符串
let s1 = String::from("Hello, ");
let s2 = String::from("world!");
let s3 = s1 + &s2; // 注意这里 s1 被 move 了, 之后就无法再使用 s1 了.

在最后一行中这样写的原因是 + 操作符实际就是在调用 add 方法, 它的方法签名是这样的:

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

看方法签名可以发现, 这个方法会获取 self 的所有权, 第二个参数是 &str, 因此才有上面的代码写法.

为什么 &str 参数使用的时候可以传入一个 &String 呢?

答案是 Rust 编译器会自动进行强制解引用(deref coercion), 它会将 &String 转换为 &String[..], 即获取这个字符串的整个切片, 这样就可以对应方法参数类型 &str 了.

因为 add 方法中第二个参数是引用(并没有 move), 因此在拼接后, 第二个参数仍然可用. 在 add 方法的实现中, 使用非常高效的方式去处理第二个参数, 而非单纯复制.

如果要拼接多个参数, 更好的办法是使用 format! 宏:

let s1 = String::from("tic");
let s2 = String::from("tac");
let s3 = String::from("toe");
let s = format!("{}-{}-{}", s1, s2, s3);

字符串中的字符访问​

由于 String 也是一种集合, 但如果通过下标访问会直接报错:

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

上面代码会有编译错误!

为什么呢?

原因是 String 的内部表示, 它是一个 Vec<u8> 的集合, 即字节集合. 但 UTF-8 字符并非一个字节表示一个字符, 而是可变长度的(比如 emoji 的一个字符会更长). 因此如果允许下标访问的话会造成取出一个字符的部分.

Rust 为了避免取单个 UTF-8 字节而可能出现错误, 因此会在此种情况下直接编译报错.

实际在看 UTF-8 字符串时有三种视角:

  • 字节数组
  • scalar value: 标量值
  • grapheme cluster: 字素簇

比如印地语的 नमस्ते 字符串, 对应的三种视角:

  • 字节数组: [224, 164, 168, 224, 164, 174, 224, 164, 184, 224, 165, 141, 224, 164, 164, 224, 165, 135]
  • 标量集合(即 Rust 中的 char 集合): ['न', 'म', 'स', '्', 'त', 'े']
  • 字素簇: ["न", "म", "स्", "ते"]

实际只有字素簇才是真正"人类理解"的这个字符串的组成部分. 而我们编程时肯定想要获取的是能够真正表示字符串中的"每个可读字符", 且由于顺序表总是想让它的下标访问是 O(1) 的, 但不同字符串中可读字符的长度不总是为 1 字节, 因此 Rust 不允许下标访问字符串.

正因为这个原因, 字符串的切片时也需要格外小心, 只有确认字符串中所有字符都是 ASCII 兼容的字符时, 切片才是安全的, 否则程序会出现 panic 让程序崩溃.

在 Rust 中提供了下面的字符串遍历方式:

// 字符视角
for c in "Зд".chars() {
    println!("{}", c);
}
// 输出如下:
// З
// д

// 字节视角
for b in "Зд".bytes() {
    println!("{}", b);
}
// 输出如下:
// 208
// 151
// 208
// 180

而目前 Rust 没有直接获取字素簇的内置方法, 只有使用外部库去获取这样的功能, 因为字素簇的获取非常复杂, Rust 标准库不会提供这样的功能.

Hash 实现的字典: HashMap​

Rust 提供了 HashMap<K, V> 用于存放键值对集合, 其中 K 会通过哈希定址进行存放.

下面仅介绍 HashMap 的主要 API:

// 创建和插入
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)
    .copied()   // 元素是 i32, copy 到栈上不会有太大开销.
    .unwrap_or(0);

// 枚举器遍历字典:
for (key, value) in &scores {
    println!("{}: {}", key, value);
}

// 更改某个键值: 直接对同一个键写值即可.
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Blue"), 25);

// 仅在不存在键的情况下写值: 第二次不会改变值了.
scores.entry(String::from("Yellow")).or_insert(50);
scores.entry(String::from("Yellow")).or_insert(10);

// 根据老的值更新新值: or_insert 会返回原值的引用, 解引用后更新值即可.
for word in text.split_whitespace() {
    let count = map.entry(word).or_insert(0);
    *count += 1;
}

HashMap 的 Ownership 规则和 Vec 的类似:

  • 针对 Copy 的数据类型, 直接 Copy 到字典中
  • 针对堆内存分配的数据类型, 会 move 到字典中

当然也可以在字典中存放堆内存分配数据的引用, 但需要保证该值的生命期至少和字典一致, 否则会编译出错.

HashMap 默认使用 SipHash 哈希算法, 虽然它不是最快的哈希算法, 但可以有效避免在哈希表上的 DoS 攻击, 因此 Rust 默认选择它. 如果需要更快的哈希算法, 可以先 benchmark 一下目前代码评估, 并切换到更快的哈希算法, 办法是提供不同的 hasher, hasher 实现了 BuildHasher 即可.