Rust Notes

本文最后更新于：1 年前

Lecture 1

语言特性

高效：Python 解释器，java 虚拟机，而 rust 没有运行时，在 bare metal（裸机）上运行。

安卓基于 java，苹果 swift，有相应的垃圾回收机制，易卡顿，而 rust 没有垃圾收集机制。

可靠：用类型系统和所有权模型来确保内存安全性和线程安全性，在编译时消除各种潜在的问题。

好用：文档丰富，编译器（提供更改方法）。

Rust 语言应用

  • Servo 浏览器引擎，Redox 操作系统，Linux 操作系统驱动和模块的支持

  • 清华大学：操作系统教学 rCore，性能所 MadFS 文件系统，IO 500 遥遥领先

  • Cargo 能够大规模添加依赖（第三方库），不需要像 C++ 花时间去寻找并下载源码

rust 基础语法

C++ cin cout 读取失败时，将流转换为非法，而 rust 则会显式地处理异常

1
2
3
4
io::stdin()
  .read_line(&mut guess)
  .expect("Failed to read line");
println!("You guessed: {guess}");

猜数获取数字以及猜测语句

1
2
3
4
// (1..=100) 代表 1-100 左闭右闭
let secret_number = rand::thread_rng().gen_range(1..=100);
// trim()前后处理空格，parse() 解析（转换类型）
let guess: u32 = guess.trim().parse().expect("Please type a number!");

变量绑定

1
2
3
4
5
6
let x = 17; // 变量绑定，且隐式推断类型
let x: i16 = 17; // 显式绑定类型
let x = 5;
x += 1; // error: re-assignment of immutable variable x
let mut y = 5;
y += 1; // OK!

变量类型

  • 布尔 bool：两个值 true/false。
  • 字符 char：用单引号，例如 'R'、' 计', 是 Unicode 的。
  • 数值：分为整数和浮点数，有不同的大小和符号属性。
    • i8、i16、i32、i64、isize
    • u8、u16、u32、u64、usize
    • f32、f64
  • 其中 isize 和 usize 是指针大小的整数，因此它们的大小与机器架构相关。
  • 字面值 (literals) 写为 10i8、10u16、10.0f32、10usize 等。
  • 字面值如果不指定类型，则默认整数为 i32，浮点数为 f64。
  • 数组 (arrays)、切片 (slices)、str 字符串 (strings)、元组 (tuples)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 数组
let arr1 = [1, 2, 3]; // (array of 3 elements)
let arr2 = [2; 32]; // (array of 32 `2`s)
// 切片
let arr = [0, 1, 2, 3, 4, 5];
let total_slice = &arr; // Slice all of `arr`
let total_slice = &arr[..]; // Same, but more explicit
let partial_slice = &arr[2..5]; // [2, 3, 4]
// 字符 String 和 &str，可以分别当做 C++ 中的 string 和 const char*
let s: &str = "galaxy";
let s2: String = "galaxy".to_string();
let s3: String = String::from("galaxy");
let s4: &str = &s3;
// 向量
// Explicit typing
let v0: Vec<i32> = Vec::new();
// v1 and v2 are equal
let mut v1 = Vec::new();
v1.push(1);
v1.push(2);
v1.push(3);
let v2 = vec![1, 2, 3];
// v3 and v4 are equal
let v3 = vec![0; 4];
let v4 = vec![0, 0, 0, 0];
// 输出向量中的所有元素
println!("Task 10: The array is {:?}", v2);

类型转换

1
2
3
4
// 使用 as 进行类型转换 (cast)
let x: i32 = 100;
let y: u32 = x as u32;
// 一般来说只能在可以安全转换的类型之间进行转换操作

引用

  • 在类型前面写 & 表示引用类型： &i32。
  • 用 & 来取引用（和 C++ 类似）。
  • 用 * 来解引用（和 C++ 类似）。
  • rust 中引用和一般意义的指针是不一样的。

条件语句

1
2
3
4
5
6
7
8
if x > 0 {
	10
} else if x == 0 {
	0
} else {
	println!("Not greater than zero!");
	-10
}

循环语句，三种循环 \(\begin{cases}\text{while}\\\text{loop = while true } \\\text{for}\end{cases}\)

迭代器

  • n..m 创建一个从 n 到 m 半闭半开区间的迭代器。
  • n..=m 创建一个从 n 到 m 闭区间的迭代器。
  • 很多数据结构可以当做迭代器来使用，比如数组、切片，还有向量 Vec 等等。
1
2
3
4
5
let xs = [0, 1, 2, 3, 4];
// Loop through elements in a slice of `xs`.
for x in &xs {
	println!("{}", x);
}

匹配语句，其中 _ 匹配所有情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 单变量版本
let x = 3;
match x {
  1 => println!("one fish"), // <- comma required
  2 => {
    println!("two fish");
    println!("two fish");
  }, // <- comma optional when using braces
  _ => println!("no fish for you"), // "otherwise" case
}
// 元组版本
let x = 3;
let y = -3;
match (x, y) {
  (1, 1) => println!("one"),
  (2, j) => println!("two, {}", j),
  (_, 3) => println!("three"),
  (i, j) if i > 5 && j < 0 => println!("On guard!"),
  (_, _) => println!(":<"),
}

模式绑定

1
let (a, b) = ("foo", 12);

函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 函数头
fn foo(x: T, y: U, z: V) -> T {
	// ...
}
// T 类型参数 x ，U 类型参数 y ，V 类型参数 z，返回 T 类型
// Rust 必须显式定义函数的参数和返回值的类型。
// 实际上编译器是可以推断函数的参数和返回值的类型的，但是 Rust 的设计者认为显式指定更好

// 函数返回
// 函数最后一个表达式是其返回值，可以使用 return 提前返回
fn square(n: i32) -> i32 {
	n * n
}
fn squareish(n: i32) -> i32 {
	if n < 5 { return n; }
	n * n
}

print! 和 println!

1
2
3
4
5
6
7
8
9
let x = "foo";
print!("{}, {}, {}", x, 3, true);
// => foo, 3, true
println!("{:?}, {:?}", x, [1, 2, 3]);
// => "foo", [1, 2, 3]
let y = 1;
println!("{0}, {y}, {0}", x);
// => foo, 1, foo

format!

1
2
let fmted = format!("{}, {:x}, {:?}", 12, 155, Some("Hello"));
// fmted == "12, 9b, Some("Hello")"

panic! 处理错误的方式，并不优雅

1
2
3
if x < 0 {
	panic!("Kaboom!");
}

assert! 和 assert_eq!

  • 如果条件 condition 不成立， assert!(condition) 会导致恐慌。
  • 如果 left != right， assert_eq!(left, right) 会导致恐慌。

unreachable! 用于表达不会达到的分支，如果达到就会导致恐慌

unimplemented! 标注没有实现的功能，panic!("not yet implemented") 的简写

lecture 2

Rust 语言最 core 的语法，语言 = 核心语法 + 标准库

所有权

  • 资源管理的需求：内存使用的安全和性能

    内存资源：\(\begin{cases}全局对象：事先分配的内存空间段，启动时分配，结束时回收\\局部对象：分配在栈上，进入函数时分配，退出函数时回收\\动态对象：分配在堆上，需要时分配，不需要时回收\end{cases}\)

  • 对于小型程序，new 之后不 delete 无所谓，程序结束之后会自动删除；但是对于大型 24h 网络服务端程序，容易出现问题，总有分配内存失败的时候

  • 内存管理方式，用户指定和垃圾回收，前者要求编写者的严谨，后者分为小回收和大回收，

    安卓手机卡的原因：处于大回收状态，逻辑不明确，性能差

  • C艹 将构造和分配集成在一起：

    • 拷贝构造：在语义上实现一个对象变两个对象（二进制串的拷贝）。

    • 移动构造：在语义上实现将一个对象的资源转移给另一个对象。

  • 空指针、悬垂指针（指针所指对象被释放，但指针没有做修改）、双重释放（两个对象的指针指向同一块内存空间，两个对象均释放）等问题导致运行时错误。

计算机技术本质上是实现一个 Trade-off

  • Rust 中的每个值都有所有者 (owner)。

  • 同一时刻只有一个所有者。

  • 当所有者失效，值也将被丢弃。

这是

一份数据只有一个所有者，如果超出作用域，其绑定数据自动释放

1
2
3
4
5
6
7
8
9
fn foo() {
  // Creates a Vec object.
  // Gives ownership of the Vec object to v1.
  let mut v1 = vec![1, 2, 3];
  v1.pop();
  v1.push(4);
  // At the end of the scope, v1 goes out of scope.
  // v1 still owns the Vec object, so it can be cleaned up.
}

以下代码在编译过程中出错，所有权的转移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
  let v1 = vec![1, 2, 3];
  // Ownership of the Vec object moves to v2.
  let v2 = v1;
  println!("{}", v1[2]); // error: use of moved value `v1`
----------------------Compile Error-----------------------
error[E0382]: borrow of moved value: `v1`
  |
2 |     let v1 = vec![1, 2, 3];
  |         -- move occurs because `v1` has type `Vec<i32>`, which does not implement the `Copy` trait
3 |     // Ownership of the Vec object moves to v2.
4 |     let v2 = v1;
  |              -- value moved here
5 |     println!("{}", v1[2]); // error: use of moved value `v1`
  |                    ^^ value borrowed here after move

在函数调用的时候，如果传入参数过多，还要将所有权还回去，比较麻烦

使用借用，所有权本身没有变化，相当于是借用一下数据

1
2
3
4
5
6
7
8
let v = vec![1, 2, 3];
// v_ref is a reference to v.
let v_ref = &v;
// Moving ownership to v_new would invalidate v_ref.
// error: cannot move out of `v` because it is borrowed
let v_new = v;
// Cancel the effect of NLL (non-lexical lifetime)
println!("{:?}", v_ref);

rust 语言是一门面向编译器语言，可以认为写不出运行有问题的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 借用与函数
fn length(vec_ref: &Vec<i32>) -> usize {
  // vec_ref is auto-dereferenced when you call methods on it.
  vec_ref.len()
}
// 可变借用
fn push(vec_ref: &mut Vec<i32>, x: i32) {
	vec_ref.push(x);
}
// Copy (特型)
// i32、f64、char、bool 可以拷贝
// 生命周期检查
let y: &i32;
{
  let x = 5;
  y = &x; // error: `x` does not live long enough
}
println!("{}", *y);

向量的三种迭代方式，不可变借用 &V、可变借用 &mut V、所有权 V

1
2
3
4
5
6
7
8
9
10
11
12
13
14
let mut vs = vec![0,1,2,3,4,5,6];
// Borrow immutably
for v in &vs { // Can also write `for v in vs.iter()`
  println!("I'm borrowing {}.", v);
}
// Borrow mutably
for v in &mut vs { // Can also write `for v in vs.iter_mut()`
  *v = *v + 1;
  println!("I'm mutably borrowing {}.", v);
}
// Take ownership of the whole vector
for v in vs { // Can also write `for v in vs.into_iter()`
  println!("I now own {}! AHAHAHAHA!", v);
}

切片是一种特殊的引用，代表序列中的一个指定片段

1
2
let a = [1, 2, 3, 4, 5];
let slice = &a[1..3];

结构化数据

有两种 struct 和 enum，mod 相当于 C艹 中的 namespace

结构体用 CamelCase 命名方式，里面的域用 snake_case 命名方式。

语法糖，对别的方法进行一种实现，写起来简便

1
2
3
4
5
struct Foo { a: i32, b: i32, c: i32, d: i32, e: i32 }
let mut x = Foo { a: 1, b: 1, c: 2, d: 2, e: 3 };
let x2 = Foo { e: 4, .. x };
// Useful to update multiple fields of the same struct:
x = Foo { a: 2, b: 2, e: 2, .. x };

Rust 的枚举要强很多，是和类型，用来表示多选一的数据（代数数据类型，如笛卡尔坐标系）

变体 \(无数据、有命名的数据域(结构体)、无命名的数据域(元组变体)\)，如

1
2
3
4
5
6
7
8
9
10
11
12
13
14
enum Resultish {
  Ok,
  Warning { code: i32, message: String },
  Err(String)
}
// 使用 Resultish::each 来访问并匹配数据
match make_request() {
  Resultish::Ok =>
  println!("Success!"),
  Resultish::Warning { code, message } =>
  println!("Warning: {}!", message),
  Resultish::Err(s) =>
  println!("Failed with error: {}", s),
}

枚举类型还可以递归

1
2
3
4
5
6
7
8
9
10
enum List {
	Nil,
	Cons(i32, List),
}
// 但上述枚举类型会报错，会趋于无穷大，使用 Box 加以限制
let boxed_five = Box::new(5);
enum List {
  Nil,
  Cons(i32, Box<List>), // OK!
}

方法与所有权

方法的第一个参数（名字为 self）决定这个方法需要的所有权种类，分类更加细致：

  • &self：方法借用对象的值。 一般情况下尽量使用这种方式，类似于 C++ 中的常成员函数。
  • &mut self：方法可变地借用对象的值。 在方法需要修改对象时使用，类似于 C++ 中的普通成员函数。
  • self：方法获得对象的所有权。 方法会消耗掉对象，同时可以返回其他的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
impl Point {
  fn distance(&self, other: Point) -> f32 {
    let (dx, dy) = (self.x - other.x, self.y - other.y);
    ((dx.pow(2) + dy.pow(2)) as f32).sqrt()
  }
  fn translate(&mut self, x: i32, y: i32) {
    self.x += x;
    self.y += y;
  }
  fn mirror_y(self) -> Point {
    Point { x: -self.x, y: self.y }
  }
}

  • 一般会创建一个名为 new 的关联函数起到构造函数的作用。

    Rust 没有内置的构造函数语法，也不会自动构造。

  • 方法、关联函数不能重载、方法不能继承

模式匹配

对结构体进行解构

1
2
3
4
5
6
7
pub struct Point {
  x: i32,
  y: i32,
}
match p {
  Point { x, y } => println!("({}, {})", x, y)
}

使用引用的方式匹配

1
2
3
4
5
6
7
let x = 17;
// 打印数值或者修改值
let mut x = 17;
match x {
  ref r if x == 5 => println!("{}", r),
  ref mut r => *r = 5
}

内部绑定（使用 @ ）

模式匹配的穷尽性，否则会报错（使用 _ 表示其他情况）

for 循环的模式匹配

1
2
3
4
5
let v = vec![1, 2, 3];
for (i, x) in v.iter().enumerate() {
  print!("v[{i}] = {x} ");
}
// v[0] = 1 v[1] = 2 v[2] = 3

lecture 3（标准库）

编码

C艹 语言 11 比 98 增加 unordered_map

C 里面的 string 为 \0 操作，即使是访问字符串长度也需要 \(O(n)\) 的空间

而 C艹 使用 std::string 更加方法，对负数进行补码操作，便于加法

  • Rust 的字符串处理机制比较复杂。
    • 主要是用 UTF-8 编码的 Unicode 字符序列。
    • 不是空字符 '\0' 结尾的 C 风格字符串，可以包含空字符。
  • 主要有两大类： &str 和 String。

字符的标识，与信息论有关：

模拟电路（信号是连续变化的，模拟类型更多，但不抗干扰，教室里的钟表）

数字电路（低电位和高电位，0V 和 5V，能抗干扰，数字手表）

ASCII 码 0 是 48，A 是 65，a 是 97

  • 编码：字符在计算机内部的表示方式

  • 早期： ASCII 码，以英文字符为主， 7 位二进制

  • 中文： GB 2312-1980《信息交换用汉字编码字符集》， 6,763 个汉字，两个字节

    • GB 18030-2005《信息技术中文编码字符集》， 70,244 个汉字，两个字节或四个字节

  • Unicode：试图把全世界的文字都纳入进来，收集了 144,697 个字符，四个字节

    • 常用 UTF-8 的形式来表示，变长一到四个字节，rust 便使用这种编码

  • 会出现乱码问题

Unicode 中文乱码速查表

xxxxxx 示例 特点 产生原因
古文码 鐢辨湀瑕佸ソ濂藉涔犲ぉ澶╁悜涓? 大都为不认识的古文，并加杂日韩文 以 GBK 方式读取 UTF-8 编码的中文
口字码 ����Ҫ�¨2�ѧϰ������ 大部分字符为小方块 以 UTF-8 的方式读取 GBK 编码的中文
符号码 由月è|å￥½å￥½å-|ä1 天天向上 大部分字符为各种符号 以 ISO8859-1 方式读取 UTF-8 编码的中文
拼音码 óéÔÂòaoÃoÃѧϰììììÏòéÏ 大部分字符为头顶带有各种类似声调符号的字母 以 ISO8859-1 方式读取 GBK 编码的中文
问句码 由月要好好学习天天向?? 字符串长度为偶数时正确，长度为奇数时最后的字符变为问号 以 GBK 方式读取 UTF-8 编码的中文，然后又用 UTF-8 的格式再次读取
锟拷码 锟斤拷锟斤拷要锟矫猴拷学习锟斤拷锟斤拷锟斤拷 全中文字符，且大部分字符为“锟斤拷”这几个字符 以 UTF-8 方式读取 GBK 编码的中文，然后又用 GBK 的格式再次读取
烫烫烫 烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫 字符显示为“烫烫烫”这几个字符 VC Debug 模式下，栈内存未初始化
屯屯屯 屯屯屯屯屯屯屯屯屯屯屯屯屯屯屯屯屯屯 字符显示为“屯屯屯”这几个字符 VC Debug 模式下，堆内存未初始化

&str 和 String

&str

  • &str 是字符串切片，是切片的一种。
  • 形如 "string literals" 的字符串字面值是 &str 类型的1。
  • &str 是静态分配空间的，且固定大小。
  • 不能用方括号来做形如 some_str[i] 的索引，因为每个 Unicode 字符可能有多个字节。
  • 正确的做法是在 chars() 中迭代：
    • for c in "1234".chars() { ... }

String

  • String 是分配在堆上的，可以动态增长。
    • 和 Vec 类似，实际上就是在 Vec<u8> 外面包了一层。
  • 也不能用下标来索引。
    • 可以通过 s.nth(i) 来访问某个字符。
  • 通过取引用的方式可以获得 &str。

Option 枚举类型

1
2
3
4
enum Option<T> {
  None,
  Some(T),
}
  • Option 是一个枚举类型，同时也是泛型类型。
  • 为某种已有类型提供了表示没有或者空值的概念。
  • 在 Rust 中，在需要返回空值时，推荐使用 Option。
    • 而不是返回诸如 NaN、 -1、 null 等特殊的值。
  • 类型 T 可以是任何类型，没有限制。

一个处理除数为 0 的情况：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
fn divide(numerator: f64, denominator: f64) -> Option<f64> {
if denominator == 0.0 {
    None
  } else {
    Some(numerator / denominator)
  }
}
// The return value of the function is an option
let result = divide(2.0, 3.0);
// Pattern match to retrieve the value
match result {
  // The division was valid
  Some(x) => println!("Result: {x}"),
  // The division was invalid
  None => println!("Cannot divide by 0"),
}

典型用途：

初始值（求列表最大值）、函数定义域不是全集、表示简单的错误情况（未定义）、结构体的可选域或者可拿走的域、可选的函数参数、空指针

错误处理

  • 对于不可恢复的错误，使用恐慌 panic!。
    • 数组越界、栈越界、算术运算溢出……
  • 对于可恢复的错误，使用 Result。
    • 文件操作、网络操作、字符串解析……
1
2
3
4
enum Result<T, E> {
  Ok(T),
  Err(E)
}
  • Result 与 Option 类似，除了正常结果外，还可以表示错误状态。
  • 也定义了 unwrap 和 expect 等方法。
  • 可以通过 ok 或 err 等方法转换成 Option。
    • 把 Ok 或者 Err 的值作为 Some，另一种变成 None。
  • 也可以进行类似 Option 的操作。
    • and、 or……

其处理原则，对返回值为 Result 的函数，一定要显式地处理（否则编译器报 warning ）

1
2
use std::io::Error;
type Result<T> = Result<T, Error>;

?操作符

配合 Result 类型

1
2
3
4
5
fn read_username_from_file() -> Result<String, io::Error> {
  let mut username = String::new();
  File::open("hello.txt")?.read_to_string(&mut username)?;
  Ok(username)
}

配合 Opition 类型

1
2
3
fn last_char_of_first_line(text: &str) -> Option<char> {
  text.lines().next()?.chars().last()
}

相当于可以提前传播错误，对上述两种类型对于 Err 和 None 就可以提前返回

究竟是恐慌还是不恐慌？就看能否给调用代码恢复的机会。

unwrap/expect 的场合：作为原型代码中的错误处理占位符

容器

Vec<T>：连续空间、可增长的序列，末尾可以高效增删、会发生增长和收缩

VecDeque<T>：双端向量，两端可以高效增删，用环状缓冲区

LinkedList<T>：双向链表，不能随机索引

HashMap<K, V> / BTreeMap<K, V>：字典（映射）类型，一般使用 HashMap<K, V>，需要满足 K: Hash + Eq，需要有序的时候用 BTreeMap<K, V> ，需要满足 K: Ord

两者访问复杂度分别为 \(O(1)\) 和 \(O(\log n)\) ，哈希表的使用举例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 (key, value) in &scores {
	println!("{}: {}", key, value);
}
// 用于统计字母出现次数
let mut count: BTreeMap<char, usize> = BTreeMap::new();
for ch in "abcbcddef".chars() {
  // {'a': 1, 'b': 2, 'c': 2, 'd': 2, 'e': 1, 'f': 1}
  count.entry(ch).and_modify(|e| *e += 1).or_insert(1);
}

collect() 的使用

1
2
3
4
5
6
7
8
9
10
// 将数据从列表转化为 BTreeSet
let mut data = vec![0, 1, 2, 3, 0];
let set: BTreeSet = data.iter().collect();
// 将数据中每个数乘以原来的两倍
let input = vec![1, 2, 3];
let result: Vec<i32> = input.iter().map(|x| x * 2).collect();
// 使用 zip() 将两个数据叠加
let a = vec![1, 2, 3];
let b = vec![2, 3, 4];
let result: Vec<i32> = a.iter().zip(b.iter()).map(|(x, y)| x + y).collect();

early，向量 lazy

B树外存，二叉树内存

迭代器

对序列的一种抽象

1
2
3
4
5
pub trait Iterator {
  type Item;
  fn next(&mut self) -> Option<Self::Item>;
  // More fields omitted
}

大数据方法 map revuse

自动测试

软件工程：回归测试（列出对所有的情况，每次开发判断能否通过）

评测系统是独立于程序的系统，用于测试；单元测试嵌入程序当中，在内部进行测试

cargo 提供了相应测试 test，在函数前面加上 #[test] 以标注这是一个测试函数

1
2
3
4
5
#[test]
fn it_works() {
  let result = 2 + 2;
  assert_eq!(result, 4);
}

习惯每写一个函数，就在文件后面实现对它的单元测试，也可以调换过来，测试驱动编程

1
2
3
4
5
6
7
fn vector_length(data: &Vec<i32>) -> usize {
  vector_length.len()
}
#[test]
fn test_vector_length() {
  assert_eq!(vector_length(&vec![1, 2, 3]), 3);
}

持续集成，CICD，每次 push 一次就会自动跑脚本，判断测试是否失败

Tutorial

习题评讲

  • 使用元组实现相当于解包压包

  • 使用 a.inter().map(|x| x * 2).collect() 等价于

    1
    2
    3
    4
    let ret - vec![];
    for x in &a{
      rec.push(x * 2);
    }

  • 随机数的选取，如果不希望抽重，使用随机种子打乱然后顺序取

  • json 是传输数据格式中非常重要的格式：字符串、字典、数字，标准中没有注释，最后没有逗号。

  • general 的工作一定有人写，合并命令行参数第三方库 merge

  • f64 没有实现偏序关系 Ord ，这是因为 NaN 不满足全序关系，从而 NaN 与所有数比较都是 false

OJ 相关知识

请求和响应，前端属于客户端，不涉及跨主机访问

HTTP 请求

例子：https://www/baidu.com/

GET:

HOST: www.baidu.com

Content-Type: html

HTTP 响应

一个例子：

HTTP 200 OK

Content-Type: application

json 序列化与反序列化

#[derive: deserialize]

result 转成 json 文件

互斥锁

yse std::sync::{Arc, Mutex};

保证数据只能被一个线程加以修改，但要防止死锁（情况如下）

1
2
let lock_a = A.luck().unwrap();
let lock_b = B.luck().unwrap();

在上锁的时候，所有错误不要出现恐慌

不同提交隔离

一个小段子：C艹中的 中分配内存出错时，没有出现内存错误的异常

Lecture 4

泛型

C 语言中没有泛型，如 quicksort() bisearch() 没有对数据类型进行泛化，而是交给程序员进行处理（手动传入 compare() 函数）

Rust 中第一个泛型，将类型作为参数，变成泛型枚举类型

1
2
3
4
enum Result<T, E> {
  Ok(T),
  Err(E),
}

python 不需要泛型，其有底层 Object 类型，并且是动态语言

对上述泛型枚举类型，在实现相应方法的时候其函数返回值也是 <T, E>，其也可以使用参数作为传入

1
2
3
fn foo<T, U>(x: T, y: U){
  // ...
}

特型(trait)

一定程度上对应面向对象编程的多态性，对于下一段美观打印、同时比较多个参数结构体实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
struct Point { 
  x: i32, 
  y: i32, 
}
impl Point {
	fn format(&self) -> String {
		format!("({}, {})", self.x, self.y)
	}
	fn equals(&self, other: Point) -> bool {
	self.x == other.x && self.y == other.y
  }
}

可以抽象出共同特点(trait)，相当于 C艹 中的虚函数

1
2
3
4
5
6
7
8
9
10
// write trait
trait PrettyPrint {
  fn format(&self) -> String;
}
// write actual function
impl PrettyPoint for Point {
  fn format(&self) -> String {
    format!("({}, {})", self.x, self.y)
  }
}

C++ 中标准库由快速排序和插入排序混合版实现

python java 使用 Tim-Sort 归并排序

C++ 背上了很大的历史包袱，每次遇到问题都需要加入新的概念

特型约束的泛型类型示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
enum Result<T, E> {
	Ok(T),
	Err(E), 
}
trait PrettyPrint {
	fn format(&self) -> String; 
}
impl<T: PrettyPrint, E: PrettyPrint> PrettyPrint for Result<T, E> {
	fn format(&self) -> String {
    match *self {
      Ok(t) => format!("Ok({})", t.format()),
      Err(e) => format!("Err({})", e.format()), 
    }
  }
}

特型可以拿到其“子特型”的方法

1
2
3
4
5
6
7
8
9
10
trait Parent {
  fn foo(&self) {
    // ...
  }
}
trait Child: Parent {
  fn bar(&self) {
    self.foo();
  }
}

#[derive(Debug)] 能够让对应的数据结构获得相应实现，不用重新编写，共有以下自动核心特性

1
2
Clone, Copy, Debug, Default, Eq
Hash, Ord, PatialEq, PartialOrd

特型的自动获得需要满足其所有成员都能自动获得指定的特型，如 Eq 不能在包含 f32 的结构体类型上自动获得，因为 f32 不是 Eq 的（浮点数中的 NAN 与任意数比较都是错误的，不满足全序关系中的自反性）

Debug 特型用于输出调试信息，如

1
2
3
4
#[derive(Debug)]
struct Point { x: i32, y: i32, }
let origin = Point { x: 0, y: 0 };
// println!("The origin is: {:?}", origin);

Default 特型用于定义一个默认值，如 0 或者 ""

Eq 和 PartialEq 等价关系和部分等价关系，都有对称性和传递性，前者还有自反性

Hash 表示可哈希的类型，H 类型是抽象的哈希状态，可以计算哈希值，而如果同时出现了 Eq 特型，需要满足以下重要性质

x == y -> hash(x) == hash(y)

PartialOrd 和 Ord 表示偏序和全序，都有反对称性和传递性，前者还要满足完全性（对所有的 a 和 b，有 a <= b 或者 b <= a 成立），后者可以按照字典序排序

关联类型的需求：例如，图的表示：邻接矩阵/链表

Sized 和 ?Sized 前者表示在编译时固定大小，后者大小是动态的（如 [T], str），一般跟指针相关的泛型才会出现后者（如 Box）

特型甚至可以为所有类型写，如 i32，但不推荐。为了写一个特型实现的 impl 代码段，要么拥有该特性，要么拥有该类型。

Drop 表示可以销毁的特型，但一般情况下不需要手动实现 Drop

特型对象

考虑以下特型和实现

静态分发：在编译的时候给定了相应特性的函数

动态分发：在运行的时候决定相应特性的函数，但只有运行之后才能使用，其他情况只能当成一个特型来使用，编译器不知道对应的类型信息（已经被抹去）

对象安全性，需要满足一定条件，关联函数要求除接收方之外，其他地方都不能出现 Self 类型（否则获取到对应的类型），不能以 Sized 为超特型，接收方是引用或者指针形式的类型（Self, Box<Self>）

课件上问题：不可变的引用是可以 Clone 的。

生命周期

考虑以下情况：

  1. 获取了一项资源。
  2. 乙方通过引用借用了甲方的这项资源。
  3. 甲方对这项资源使用完毕，对它进行释放。
  4. 乙方还保留着对这项资源的引用，并开始使用它。
  5. 乙方挂了……

如何保证第 3 步和第 4 步的顺序关系？一般情况下，引用具有隐式的生命周期，不需要额外关注，但也可以显式地指定生命周期

1
2
3
fn bar<'a>(x: &'a i32) {
	// ...
}

fn borrow_x_or_y<'a>(x: &'a str, y: &'a str) -> &'a str; 保证引用 x 和 y 的生命周期至少会和返回的引用生命周期一样长，若只需要前者和返回值的生命周期一样长，则可以分开为 'a 与 'b fn borrow_p<'a, 'b>(p: &'a str, q: &'b str) -> &'a str;，如以下编译期间会报错

1
2
3
4
5
6
7
8
9
10
11
struct Pizza(Vec<i32>);
struct PizzaSlice<'a> {
  pizza: &'a Pizza, // <- references in structs must
  index: u32, // ALWAYS have explicit lifetimes
}
  let s2; {
  let p2 = Pizza(vec![1, 2, 3, 4]);
  s2 = PizzaSlice { pizza: &p2, index: 2 };
  // no good - why?
}
drop(s2); // to undo NLL

如果结构体或者枚举类型的成员是引用，那么就需要显式地指定生命周期

1
2
3
4
struct Foo<'a, 'b> {
  v: &'a Vec<i32>,
	s: &'b str, 
}

Lecture 5

所有权是 rust 语言资源管理的灵魂，特型是 rust 语言灵活运用的灵魂。

共享不修改，修改不共享——rust 设计哲学

项目管理

模块系统

  • 包 (packages)：Cargo 的一项功能，可以让用户构建、测试、分享箱。
  • 箱 (crates)：也叫单元包，是由模块构成的一棵树，能够产生一个库或者可执行文件。
  • 模块 (modules)：与 use 配合，控制路径的组织结构、作用域和访问权限。
  • 路径 (paths)：命名项目的方式，这里的项目可以指结构体、函数、模块等。

在模块中加上 pub 关键字便可以让其他用户访问，模块相当于 C艹 中的 namespace，模块之间可以嵌套，如下

1
2
3
4
5
6
7
8
mod english {
  pub mod greetings { /* ... */ }
  pub mod farewells { /* ... */ }
}
mod chinese {
  pub mod greetings { /* ... */ }
  pub mod farewells { /* ... */ }
}

可以把模块写成单独的文件 lib.rs，用于整合所有的模块

1
2
3
4
// lib.rs
mod english;
// english.rs
pub mod greetings { /*...*/ }

也可以用目录来组织模块，把模块当做目录名使用

还可以在 Cargo 中使用自己编写的箱

1
2
3
[dependencies]
myfoo = { git = "https://github.com/me/foo-rs" }
mybar = { path = "../rust-bar" }

Cargo 相关

单元测试直接附着在源代码中，#[test]，集成测试放在 tests/*.rs 中，基准测试程序放在 benches/*.rs（类似作坊中的基准模块）

feature 是在构建时做选择性的开关（与 bug 不同）

使用 rust 语言，Cargo 编写脚本

1
2
[package]
build = "build.rs"

可以将自己写的软件包发布到 crate.io ，原子性的库。

语法补充

属性

#! [no_std] 禁用标准库，#[derive(Debug)] 自动获得特型

#[inline(always)] 提示编译器内联优化，#[cfg(target_os = "linux")] 定义条件编译。

inter procedure o

操作符

运算类 > 操作类 > 位运算类 > 逻辑类，其背后的原因是 a + b == c 应该被理解为 (a + b) == c，后者是源于逻辑二元运算存在短路情况

使用特型来重载操作符，定义在 std::ops 下，有如下重载操作符：Neg, Not, Deref, DerefMut | Mul, Div, Mod | Add, Sub...

类型转换

使用 From 和 Into 实现自定义类型转换，前者实现之后后者会自动实现，例如实现对数转换

1
2
3
4
5
6
7
8
9
impl Into<f64> for Log2 {
    fn into(self) -> f64 {
        // return log_2 of the value
        self.0.ln() / std::f64::consts::LN_2
    }
}
// 调用取得对数
    let log2_4: f64 = Log2(4.0).into();
    let log2_8: f64 = Log2(8.0).into();

命名规范

标识符

  • CamelCase：类型、特型

  • snake_case：箱、模块、函数、方法、变量

  • SCREAMING_SNAKE_CASE：常量和静态变量

  • T（单个大写字母）：类型参数

  • 'a（撇 + 短的小写名字）：生命周期参数

构造函数和转换函数

  • new, new_with_stuff：构造函数

  • from_foo：转换构造函数

  • as_foo：低开销非消耗性转换

  • to_foo：高开销非消耗性转换

  • into_foo：消耗性转换

智能指针

Box<T>

用于在堆上分配空间存放数据，其拥有 T 类型的对象，其指针是唯一的，类似 C艹 中的 std::unique_ptr，是动态分配

std::rc::Rc<T>

是 Referenced counted 的缩写，代表指针的别名个数

共享所有权的指针类型，相当于 C艹 中的 std::shared_ptr，并且其一直符合 rust 的借用规则，当且仅当引用计数为 1 时才能修改

1
2
3
4
5
let mut shared = Rc::new(6);
println!("{:?}", Rc::get_mut(&mut shared)); // ==> Some(6)
let mut cloned = shared.clone(); // ==> Another reference
println!("{:?}", Rc::get_mut(&mut shared)); // ==> None
println!("{:?}", Rc::get_mut(&mut cloned)); // ==> None

gc 垃圾回收机制，如果有各种变量相互引用形成一种环，就不能释放，导致空间的浪费：

  • A 有一个 B 的 Rc，B 也有一个 A 的 Rc，两者的引用计数都是 1。

  • 由于构成了环，两个对象都不会被释放，从而引起内存泄露。

可以使用弱引用来避免（与 C艹 中的 weak_ptr 类似） ，Rc::downgrade() 降级成 Weak。

对于图 (V, E)，对顶点拥有所有权，但是对于边来说，不能拥有对顶点的所有权，可以使用弱引用来实现

但这样会引入双重计数，增加开销。

std::cell::Cell<T>

为 Copy 类型提供内部可变性的格子类型，用 get() 从 Cell 中取值，用 set() 更新 Cell 的值。

std::cell::RefCell<T>

可为任意类型提供内部可变性，当 borrow() 一个 RefCell<T> 时，得到的是 Ref<T>，而不是 &T。

const T 和 *mut T

相当于 C 语言的裸指针。

常用库

  • 正则表达式: reges
  • 日志: log （源于航海，各种级别分开，error, warning）
  • 日期: chrono
  • HTTP 客户端: reqwest
  • 增强错误处理: thiserror , anyhow
  • 数据库: rusqlite, r2d2

数据库

分类

数据库是以一定方式存储在一起、能够给多个用户共享、具有尽可能小的冗余度、与应用程序彼此独立的数据集合。

  • 关系数据库：创建在关系模型基础上的数据库，给予集合代数
    • Oracle 国外数据库，早些年中国各大银行使用，现在国产化
    • ProsgreSQL
      • MySQL
      • SQLite

  • 非关系型数据库
    • 文档数据库（json 转换为二进制文件），如 MongoDB
    • 键值数据库（类似 HashMap），如 LevelDB

操作

数据查询：选择、投影、连接、并、交、差

Excel 表中 vlookup 函数用于合并数据，指定键值

数据操作：新增、删除、修改、查询

SQL 简介

常用命令：

  • 创建表格 CREATE TABLE
  • 查询数据 SELECT
  • 插入数据 INSERT
  • 更新数据 UPDATE
  • 删除数据 DELETE
  • 删除表格 DROP TABLE

DBA IT 认证，Oracle 数据管理库职业

在 rust 中使用 SQL

软件包 rusqlite

1
2
3
4
5
6
7
8
9
10
11
fn main() -> Result<()> {
  let conn = Connection::open_in_memory()?;
  conn.execute(
    "CREATE TABLE person (
    id INTEGER PRIMARY KEY,
    name TEXT NOT NULL,
    data BLOB
    )",
    (), // empty list of parameters.
  )?;
}

还可以与 Web 框架联合使用

创建数据库连接池，将连接池作为 Data<T> 传给请求处理代码

Lecture 6

当今许多设备都是多核的，并发是现代语言必须具备的特性，

闭包

概念与类型推导

闭包的概念和匿名函数、lambda 函数相似，其可以绑定在变量上：

1
2
3
let square = |x: i32| -> i32 { x * x };
println!("{}", square(3));
// => 9

类型可以推导，参数类型和返回值类型都可以不显示地给出

1
2
3
4
let square_v4 = |x: u32| { (x * x) as i32 };
let square = |x| { x * x };
println!("{}", square(-2.4));
// => 5.76

捕捉

闭包还可以包含其所在的环境（可以调用外面的参数，称为捕捉）

1
2
3
let magic_num = 5;
let magic_johnson = 32;
let plus_magic = |x: i32| x + magic_num;

闭包绑定后如果尝试借用，如果在上述代码后面加入以下代码，借用编译器则会报错

1
let more_magic = &mut magic_num; // Err!

移动闭包

可以使用 {...} 让闭包超过作用域来恢复，调用函数和被调用函数 Caller, Callee，也可以使用 move 关键字强制闭包获得环境变量的所有权，为移动闭包

1
2
3
4
5
6
7
fn make_closure(x: i32) -> Box<dyn Fn(i32) -> i32> {
  let f = move |y| x + y;
  Box::new(f)
}
let f = make_closure(2);
println!("{}", f(3));
// => 5

特型闭包

闭包与所有权，只能调用一次，满足 rust 借用规则。与所有权相似，闭包也具有闭包特型，Fn, FnMut, FnOnce 分别代表借用、可变借用、所有权

如何正确地返回闭包？如下，使用动态的生命周期以及移动语义解决

1
2
3
4
fn box_up_your_closure_and_move_out() -> Box<dyn Fn(i32) -> i32> {
  let local = 2;
  Box::new(move |x| x * local)
}

Lambda 函数本质上是 C++/Rust 在调用处创建一个未知名字的类/结构体，然后传入环境的相关值，最后调用一个未知名字的函数。

并发

线程进程、并发并行概念

二进制可执行文件在执行之后，成为进程，在 CPU 中存放：寄存器，堆，栈，操作系统指令。

Program Point 指向进程下一个指令（在X86 中称为 PC）

线程是轻量级，有 CPU 存放的寄存器、堆、栈、操作系统指令单元，但内存是相互共享的，但不引入通信的开销（网络、进程通信）

并发是程序同时有多个正在运行的线程，而并行是指多个处理单元，要求更高，真正意义的同时处理。

并发执行

考虑下面代码，假设两个线程，一个执行 foo()，一个执行 bar()

1
2
3
4
5
6
7
8
9
let mut x = 0;
fn foo() {
  let mut y = &mut x; *y = 1;
  println!("{}", *y); // foo expects 1
}
fn bar() {
  let mut z = &mut x; *z = 2;
  println!("{}", *z); // bar expects 2
}

这两个线程的执行顺序不是每次都能保证的，如果将两个函数当做两台 ATM 机，则会发生严重的后果。

并发编程的难点：数据共享、数据竞争、同步（保证所有线程都有正确的世界观，共享缓冲区）、死锁

死锁发生有四个条件：互斥、持有资源、非抢占、等待成环

一个形象的例子：

N 个哲学家坐在一张圆桌周围，交替地进行吃饭和思考。每个哲学家需要一双筷子用来吃饭，但是一共只有 N 根筷子，每两个哲学家之间有一根。

哲学家的行为用算法描述如下：

  • 拿起他左侧的那根筷子（获取一个资源的锁）。
  • 拿起他右侧的那根筷子（获取一个资源的锁）。
  • 吃饭（使用资源）。
  • 将两根筷子放回原处（释放资源的锁）。

对所有哲学家来说，依据算法，所有人都拿到左侧的筷子，而此时桌上没有筷子，从而所有人卡在第二步

线程

Rust 标准库提供了线程 std::thread，每个线程有自己的栈和状态，使用闭包来指定线程的行为

线程句柄

1
2
3
4
5
use std::thread;
let handle = thread::spawn(|| {
  "Hello, world!"
});
println!("{:?}", handle.join());

join() 会阻塞当前线程的执行，直到句柄对应的线程终止，其返回 Ok 或者 Err

thread::park() 可以暂停自己的执行，之后可以通过现成的 unpark() 来继续执行

线程与所有权

线程的创建也要满足所有权的规则（包括闭包和所有权的规则），例如使用 move 来创建移动闭包，获得所有权

1
2
3
4
5
use std::thread;
for i in 0..10 {
  thread::spawn(move || {
  	println!("I'm #{}!", i);
}

共享线程状态

Rust 类型系统包含要求满足并发承诺的特型

  • Send 表示可以在线程间安全转移

  • Sync 表示可以在线程间（通过引用）安全共享

Send 类型可以将它的所有权在线程间转移，如果一种类型没有实现 Send，那么它只能留在原来的线程里。

Sync 类型在多个线程使用时不会引发内存安全问题，基本所有类型都是 Sync 的。以下为一个共享线程状态示例

1
2
3
4
5
6
7
8
9
10
11
use std::thread;
use std::time::Duration;
fn main() {
  let mut data = vec![1, 2, 3];
  for i in 0..3 {
    thread::spawn(move || {
      data[i] += 1;
    });
  }
  thread::sleep(Duration::from_millis(50));
}

此时 data 有多个所有者，使用 Arc<T> ，代表原子性的引用计数指针（Atomic Reference-Counted），但如果只是在初始化加入 Arc，编译也不通过。

Arc 也不具有内部可变性，需要添加互斥锁（Mutual Exclusion），保证它包含的值只有一个线程能够访问；如果一个线程锁定了互斥锁，但是发生了恐慌，此时该互斥锁进入中毒状态，该锁不会被释放

高并发任务、超算比赛主要资源共享，Open Np，消息传递 npi

通道

通道（channels）可以用来同步线程之间的状态，用于在线程之间传递消息，也可以用来提醒其他现成关于数据就绪、事件已经发行的情况

std::sync::mpsc 实现多生产者、单消费者的通信功能

同步：不同进程之间是需要等待的，异步：发送的东西放入（相当于无限大的）缓冲区，相互之间不需要等待

使用 channel<T>() 函数创建一对连接的 (Sender<T>, Receiver<T>)

go 语言有 GC 机制，导致编程开销大

对哲学家筷子问题，可以使用最后一个哲学家用相反方向拿筷子或者传递令牌规定拿筷子的哲学家。

编程 > Rust
#Rust
Rust Notes
https://lr-tsinghua11.github.io/2022/09/11/%E7%BC%96%E7%A8%8B/Rust%20%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E8%AF%BE%E5%A0%82%E7%AC%94%E8%AE%B0/
作者
Learning_rate
发布于
2022年9月11日
许可协议