Rustlings Solution 可以参见我的Repo： Github Repo

Rust难点笔记 2. 链表 为一个基础数据结构开一个新篇？链表这么有牌面么？今天在Leetcode随机到了跳表，于是我准备学习下Rust链表先。乍一看链表应该不难啊，值得放进难点？看一下course.rs:人家开了一整章，好吧，我们知道Rust不允许悬垂指针，那我们的链表可咋整，且听我慢慢来学1 实现链表从简单的定义开始pub enum List { Empty, Elem(i32, List), }当尝试build这个的时候，会出现当前这个类型并不是定长的，Rust编译器认为栈上类型必须有固定长度，因此，我们按照提示，把List通过Box封装到堆上，栈上只留下一个定长的指针。更改为box封装后，我们的链表过编了，但是这还有点问题，一点都不优雅[] = Stack () = Heap [Elem A, ptr] -> (Elem B, ptr) -> (Empty, *junk*)链表头并不是一个指针，而是一个栈上元素，而后面的尾节点却在堆上，而我们期望的（显然，你应该已经了解C的链表了）[head] -> (val A, ptr) -> (val B, null)是这样的链表这是有意义的，前者在分割、合并链表的时候，都会有Copy到栈上、Copy到堆里的操作，但是后者只需要动动指针，也和我们最初的期望保持一致。由此，我们的定义改版为如下：struct Node { elem: i32, next: List, } pub enum List { Empty, More(Box<Node>), }在叙述中，这种enum会遵循Rust的编译器优化，More中包含了一个非0指针，而Empty是无数据的（More、Empty都是自定义的，叫啥都行），在这种情况下不会产生enum_tag的开销，即Rust不需要记住具体是哪种tag，非0就是More，为0就是Empty还有一点小问题，封装的可见性。材料里报的是error，我本地报的warning，但是不管哪种，我们都希望尽可能符合最小暴露原则，所以定义改为如下：pub struct List { head: Link, } enum Link { Empty, More(Box<Node>), } struct Node { elem: i32, next: Link, }接下来，我们为这个链表加上操作impl List { pub fn new() -> Self { List { head: Link::Empty } } pub fn push(&mut self, elem: i32) { // 在链表头插入数据 } }push会改变链表，所以需要一个可变借用，我们新建一个Node，然后把她的next指向旧head，把head指向他 pub fn push(&mut self, elem: i32) { let new_node = Box::new(Node { elem: elem, next: self.head, }); self.head = Link::More(new_node); }看起来很美好，但是估计没有这么简单Link没有实现Copy，我们也不能简单粗暴的实现一个Clone，如果直接赋值，会导致Link的所有权被移走，head悬垂了我们用一个不太优雅的小trick：mem::replace，在从head中偷出值的同时塞回去一个新值变成这样：pub fn push(&mut self, elem: i32) { let new_node = Box::new(Node { elem: elem, next: std::mem::replace(&mut self.head, Link::Empty), }); self.head = Link::More(new_node); }好吧，看着奇奇怪怪，在逻辑中引入了一些不逻辑的东西，但是我们没有什么办法了接着实现Pop，在弹出的同时返回一个Optionpub fn pop(&mut self) -> Option<i32> { match &self.head { Link::Empty => { None; } Link::More(node) => { self.head = node.next; Some(node.elem) } } }不需要编译，都能猜到肯定 self.head = node.next;有点问题，这里又产生move了我本来想说，那就不给大家演示了，结果一编译发现还有个问题两个愿望，一次满足：pub fn pop(&mut self) -> Option<i32> { match std::mem::replace(&mut self.head, Link::Empty) { Link::Empty => None, Link::More(node) => { self.head = node.next; Some(node.elem) } } }把head变成empty，同时换到node里，但是和push一样使用了一点trick链表的释放rust为绝大多数类型实现了drop，并且如果结构的每个字段都有drop，也会自动为结构实现drop但是材料给了一种问题情况：#[test] fn long_list() { let mut list = List::new(); for i in 0..100000 { list.push(i); } drop(list); }虽然这看上去是一个尾递归（递归发生在尾部，应当复用栈帧），但是在rust实现里并非如此impl Drop for List { fn drop(&mut self) { // NOTE: 在 Rust 代码中，我们不能显式的调用 `drop` 方法，只能调用 std::mem::drop 函数 // 这里只是在模拟编译器! self.head.drop(); // 尾递归 - good! } } impl Drop for Link { fn drop(&mut self) { match *self { Link::Empty => {} // Done! Link::More(ref mut boxed_node) => { boxed_node.drop(); // 尾递归 - good! } } } } impl Drop for Box<Node> { fn drop(&mut self) { self.ptr.drop(); // 糟糕，这里不是尾递归! deallocate(self.ptr); // 不是尾递归的原因是在 `drop` 后，还有额外的操作 } } impl Drop for Node { fn drop(&mut self) { self.next.drop(); } } 对于Box\<Node>来说，编译器的行为并不是尾递归，会爆栈材料给出一种方法impl Drop for List { fn drop(&mut self) { let mut cur_link = mem::replace(&mut self.head, Link::Empty); while let Link::More(mut boxed_node) = cur_link { cur_link = mem::replace(&mut boxed_node.next, Link::Empty); } } } 手动的换出每个节点，然后在while结束的时候就drop了优化类型定义和代码复杂度刚刚的代码中，除了replace很怪，还有一大坨的类型声明也很怪，毕竟我们C的链表声明一个结构体就够了有一个很显然的优化是enum Link和Option十分的类似pub struct List { head: Link, } type Link = Option<Box<Node>>; struct Node { elem: i32, next: Link, } Option提供了一个take函数，让我们不需要那个冗长的replacepub fn push(&mut self, elem: i32) { let new_node = Box::new(Node { elem: elem, next: self.head.take(), }); self.head = Some(new_node); }Option让我们的match可以变为mappub fn pop(&mut self) -> Option<i32> { self.head.take().map(|node| { self.head = node.next; node.elem }) }加入泛型我们会在签名处加入 <T\>，这样这个链表即时就支持泛型了pub struct List<T> { head: Link<T>, } type Link<T> = Option<Box<Node<T>>>; struct Node<T> { elem: T, next: Link<T>, } impl<T> List<T> { pub fn new() -> Self { List { head: None } } pub fn push(&mut self, elem: T) { let new_node = Box::new(Node { elem: elem, next: self.head.take(), }); self.head = Some(new_node); } pub fn pop(&mut self) -> Option<T> { self.head.take().map(|node| { self.head = node.next; node.elem }) } } impl<T> Drop for List<T> { fn drop(&mut self) { let mut cur_link = self.head.take(); while let Some(mut boxed_node) = cur_link { cur_link = boxed_node.next.take(); } } }

Rust难点笔记 1. 生命周期 [UPD2. 24.2.24] Rust难点笔记 1. 生命周期说在最前面：这是一篇笔记，而不是教程，难免有不周到的、比较主观的想法，敬请大家批评指正和理解这个系列是支撑我写rCore学习时边写边学产生的笔记，周期会比较长远期计划会包括[生命周期, 宏, 异步, 智能指针, 链表]01 生命周期为什么要有生命周期？ Rust的内存机制我们已经很熟悉了。生命周期和引用是强绑定的，就一句话：引用还在的时候，不能让引用的对象消失，从而造成悬垂指针问题因此，我们在编译的时候如果出现一个被引用的对象在其引用前被销毁，就会报 xxx does not live so long的错误，这就是对象存活时间小于引用的生命周期，Rust不允许02 生命周期标注编译器有的时候没办法推断生命周期，需要我们手动标注元素的存活周期。在了解生命周期标注的刚开始，最困扰我的问题就是：我标注的东西，只是一个标注，真的能保证程序安全么带着这个问题开始学看一下最常见的生命周期例子fn max(a: &i32, b: &i32) -> &i32 { if *a > * b { a } else { b } }看到这个函数的第一个结论是：返回值的&i32必须来自于a或b，否则，任何max函数体内创建的变量都会在离开函数时销毁。问题是编译器在编译时无法确定到底来自a还是b（程序员应该预期的是a和b都有可能），此时我们要声明a、b的返回值都是一样的（其实是，至少活的一样长，换句话说，我理解a是三者之间最短的那个的生命周期）在函数后声明生命周期fn max<'a>(a: &'a i32, b: &'a i32) -> &'a i32 { if *a > * b { a } else { b } }此时，我们声明了该函数的两个参数应当和返回值生命周期一样长。考虑如果不是max，是firstfn call_max(a: &i32) -> &i32 { let b = 2; max(a, &b) } fn max<'a>(a: &'a i32, b: &'a i32) -> &'a i32 { a }此时我们只需要要求a的生命周期和返回值一样长了，但是因为标注了a、b都要符合生命周期，导致call_max报错如果改为：fn max<'a, 'b>(a: &'a i32, b: &'b i32) -> &'a i32 { a }call_max就不再会报错了回到报错的case，我们看看为什么因为call_max中，原则上是不能返回b的引用的，b会在call_max退出时销毁。由于调用的时候，a、&b和max的返回值遵循同一个生命周期，rust会取其中最小的，（也就是&b）作为我们标注的生命周期而作为call_max的返回值，其在caller处还可能会被用，但是由于标注最短的原则，它的生命周期只覆盖到call_max函数结尾，这肯定是不行的。而把生命周期改为'b的时候，和'a解绑了，'a和传入call_max的a的生命周期一致，和call_max的返回值一致，而不依赖'b。所以可以通过03 生命周期的函数省略生命周期本来标的就乱七八糟的，编译器会在能推导的情况下生成默认的生命周期https://doc.rust-lang.org/reference/lifetime-elision.html文档里其实介绍了结构和特征的生命周期，但是目测是一法通万法通，先从函数开始可省略的函数参数都有独立生命周期所有参数共用生命后期，生命周期会被直接作用到返回值如果是方法，返回值会和&self的生命周期一致来看看例子第一个例子里是第一条规则，没填就分配独立的第二个例子同理，lvl不是引用，没有生命周期第三个例子，用到了一二两条，给输入参数放了个'a，而入参只有'a 一个生命周期第四个例子还是第一条规则这个用到了一三，如果有&Self，会和&Self的生命周期一致第一个例子无法为输出推断生命周期，因为没有输入第二个例子无法推断生命周期，因为s和t的生命周期默认独立，不能推断返回值的04 结构体生命周期类比函数生命周期，给出一个例子就好懂了struct ImportantExcerpt<'a> { part: &'a str, } fn main() { let novel = String::from("Call me Ishmael. Some years ago..."); let first_sentence = novel.split('.').next().expect("Could not find a '.'"); let i = ImportantExcerpt { part: first_sentence, }; }这个例子说明part必须和持有它的结构体活的至少一样久而这个代码就过不了#[derive(Debug)] struct ImportantExcerpt<'a> { part: &'a str, } fn main() { let i; { let novel = String::from("Call me Ishmael. Some years ago..."); let first_sentence = novel.split('.').next().expect("Could not find a '.'"); i = ImportantExcerpt { part: first_sentence, }; } println!("{:?}",i); }因为结构体本身活到了println处，而part引用只能活到前一个作用域05 方法生命周期struct ImportantExcerpt<'a> { part: &'a str, } impl<'a> ImportantExcerpt<'a> { fn level(&self) -> i32 { 3 } }注意，这里ImportantExcerpt的完整签名是ImportantExcerpt<'a>，生命周期声明也是结构体的一部分所以这里语法类似泛型06 几个不太聪明的例子例子来自course.rsRust的生命周期面对某些特定情况，可能不够聪明，比如：#[derive(Debug)] struct Foo; impl Foo { fn mutate_and_share(&mut self) -> &Self { &*self } fn share(&self) {} } fn main() { let mut foo = Foo; let loan = foo.mutate_and_share(); foo.share(); println!("{:?}", loan); }传入的虽然是可变借用，但是返回时实际上是一个不可变借用，所以理论上来说最终是不可变的share处又进行了一次不可变借用，语义上说，两个不可变借用是没问题的，但是显然编译器不会那么听我的话mut函数的生命周期标注实际上是这样的： fn mutate_and_share<'a>(&'a mut self) -> &'a Self { &'a *self }代表返回值loan和foo的可变借用 &mut self 生命周期相同，所以loan存续期间， &mut self也一直存续虽然本身是个安全的东西，但是现在还没有机制支持，只能按我们标注的情况判定为不合法了。再来看一个#![allow(unused)] fn main() { use std::collections::HashMap; use std::hash::Hash; fn get_default<'m, K, V>(map: &'m mut HashMap<K, V>, key: K) -> &'m mut V where K: Clone + Eq + Hash, V: Default, { match map.get_mut(&key) { Some(value) => value, None => { map.insert(key.clone(), V::default()); map.get_mut(&key).unwrap() } } } } 第一个map.get_mut(&key) 调用完成后，map的可变借用就可以结束了，但是因为我们的声明，这个借用一直存续到函数结束因此map.insert() 会报错，因为产生了另一个可变借用。

Rust入门笔记 6. 迭代器方法 在这段时间练习Rust过程中，大量的简单易用的迭代器方法让我觉得非常优美（尽管这么写起来可能一点都不好读），决定单开一篇整理一下迭代器的方法迭代器是什么所有实现了特征Iterator的类型都算迭代器，即使还没用过迭代器，但是只要用过for循环，就隐式的使用过迭代器了。Rust的for循环是一个语法糖，in后面的对象需要是一个迭代器，for循环反复调用迭代器的next，直到Next返回一个None。为什么要用迭代器而不直接用下标？其实Cpp的STL也大量的使用迭代器，在Rust里，我觉得主要原因是迭代器保证了不会出现越界问题。Rust保证安全性问题是有开销的，Vec每次下标访问都会检查边界，如果超出边界则panic我们平时常用的 a..b, a..=b 也都是迭代器，或者说，它们都是Range，同时实现了Iterator迭代器迭代器方法进入正题，以下列举迭代器方法首先是取元素以及遍历方法nextnext方法是迭代器最基本的功能，让迭代器指向第一个对象，返回一个 Option，它不需要参数，只需要一个Selflet a = vec![1, 2]; let mut iter = a.iter(); assert_eq!(Some(&1), iter.next()); assert_eq!(Some(&2), iter.next()); assert_eq!(None, iter.next());enumerate常用python的话对这个也不会陌生，enumerate同时返回迭代次数和对象，返回值为Option<(usize, Self::Item)>（的一个迭代器），相当于同时帮我们记录了迭代次数。比较常用的情况就是同时需要数组值和下标。fn main() { let vec = vec![222, 546, 231, 666, 10]; for (i, val) in vec.iter().enumerate() { println!("{} : {}", i, val); } } 0 : 222 1 : 546 2 : 231 3 : 666 4 : 10for_each()for_each实际上调用的是fold，它接受一个闭包作为参数，并把每次迭代出的值传递给闭包，作为闭包的参数，它没有返回值（或者说返回值是单元Unit()）fn main() { (1..=3).for_each(|x| { print!("{}, ", x); }); } // 1, 2, 3, take()take接受一个参数k，表示取迭代器的前k个元素，返回的是一个被截断过的迭代器这个方法会获取所有权fn main() { (1..=10).take(4).for_each(|x| { print!("{}, ", x); }); } // 1, 2, 3, 4, nth()、nth_back()返回的是剩余元素中第k个（倒数第k）位置的元素，并跳到（k的）下一个位置，中间所有的元素都会被消费fn main() { let vec = vec![222, 546, 231, 666, 10]; let mut iter = vec.iter(); println!("{:?}", iter.nth(2)); println!("{:?}", iter.nth(0)); assert_eq!(iter.nth(0), Some(&10)); assert_eq!(iter.nth(0), None); } // Some(231) // Some(666)fn main() { let vec = vec![222, 546, 231, 666, 10]; let mut iter = vec.iter(); println!("{:?}", iter.nth_back(2)); println!("{:?}", iter.nth(1)); assert_eq!(iter.nth(0), None); } // Some(231) ， 此时231， 666， 10都被消费了，iter还在开头 // Some(546)last()只取迭代器的最后一个元素，会消费整个迭代器。当然，返回的也是Option\<Self::Item\>以下是变换方法rev()翻转整个迭代器vec![0, 1, 2, 3, 4].iter().rev().for_each(|x|print!("{x}, ")); // 4, 3, 2, 1, 0, skip(k)跳过k个元素，相当于take的补assert_eq!(vec![2,3], (0..4).skip(2).collect::<Vec<_>>());step_by(k)调整迭代器步长//0, 2, 4, 6, 8, 10, (0..=10).step_by(2).for_each(|x| print!("{x}, "));zip()把两个迭代器合并为一个元组的迭代器let it = [1,3,5].iter().zip([2,4,6].iter()); it : vec![(&1,&2),(&3,&4),(&5,&6)]filter()接受一个闭包，把元素一个个传给闭包，该闭包返回一个个bool，留下所有闭包返回true的元素，组成一个迭代器(0..=10).filter(|x| x % 3 == 0) // 还是个迭代器，[0, 3, 9]collect()我意识到我要先说collect，不然只能用for说明结果还是迭代器collect把一个迭代器的元素组成一个新的集合，具体组合成啥由程序员指定或者由编译器推导（Rust的推导能力我觉得还是很强大的）let vec = (0..=100).collect::<Vec<_>>(); // 默认i32,0-100的一个vecmax()、sum()、min()、count()找到迭代元素里的最大值和求和（最小值、元素个数），sum需要指定结果类型let vec = vec![1, 5, 3, 4, 2]; let max = vec.iter().max().unwrap(); // 5 let sum = vec.iter().sum()::<i32>(); // 15all()、any()接受一个闭包，和filter一样的，区别是这两个是返回一个bool而不是一个迭代器，分别代表是否所有元素都满足闭包、是否由元素满足闭包find()接受一个和filter一样的闭包，区别是filter返回全部的迭代器，find返回第一个满足条件的元素map()、filter_map()map()接受一个闭包，把元素逐个传进闭包，把闭包的返回值组成一个迭代器。对于filter_map()来说，不会把None的东西压进迭代器，实现filter的能力fn main() { let numbers = vec![1, 2, 3, 4, 5]; // 使用 filter_map 方法将所有偶数映射为它们的平方根 let results: Vec<_> = numbers.iter().filter_map(|&x| { if x % 2 == 0 { Some((x, (x as f64).sqrt())) } else { None } }).collect(); println!("Filtered and mapped: {:?}", results); }flat_map()flat_map也是接受一个闭包，不过返回的是一系列迭代器，并把他们拍扁成一个迭代器fn main() { let words = vec!["hello", "world", "rust"]; let chars: Vec<_> = words.iter().flat_map(|&word| word.chars()).collect(); println!("{:?}", chars); // ['h', 'e', 'l', 'l', 'o', 'w', 'o', 'r', 'l', 'd', 'r', 'u', 's', 't'] }partition()根据闭包的布尔条件分拆成两个集合fn main() { let numbers = vec![1, 2, 3, 4, 5]; // 使用 partition 方法将奇数和偶数分开 let (even, odd): (Vec<_>, Vec<_>) = numbers .into_iter() .partition(|&x| x % 2 == 0); println!("Even numbers: {:?}", even); // [2, 4] println!("Odd numbers: {:?}", odd); // [1, 3, 5] } scan()、fold()scan和fold都接受两个参数，分别是初始值和一个闭包，传入闭包两个参数：累加值和当前元素区别是scan会把每次闭包返回的结果放一起，最后生成一个迭代器，而fold返回最终的结果fn main() { let numbers = vec![1, 2, 3, 4, 5]; // 使用 scan 方法计算累加和 let cumulative_sum: Vec<_> = numbers.iter().scan(0, |acc, &x| { *acc += x; Some(*acc) }).collect(); println!("{:?}", cumulative_sum); // [1, 3, 6, 10, 15] } fn main() { let numbers = vec![1, 2, 3, 4, 5]; let sum = numbers.iter().fold(0, |acc, &x| acc + x); println!("Sum: {}", sum); // 输出 15 }

Rust入门笔记 5.方法和关联函数 使用 impl "struct_name" 的方式声明关联函数struct Point { x: f64, y: f64, } impl Point { fn origin() -> Point { Point { x: 0.0, y:0.0 } } fn new(x: f64, y:f64) -> Point { Point {x:x, y:y} } }在第一个参数处声明一个Self类型的变量，以为结构创建方法self <=> self: Self &self <=> self: &Self &mut self <=> self: &mut Self // self 会拿走当前结构体实例(调用对象)的所有权，而 &self 却只会借用一个不可变引用，&mut self 会借用一个可变引用 struct Rectangle { p1: Point, p2: Point, } impl Rectangle { // 这是一个方法 // `&self` 是 `self: &Self` 的语法糖 // `Self` 是当前调用对象的类型，对于本例来说 `Self` = `Rectangle` fn perimeter(&self) -> f64 { let Point { x: x1, y: y1 } = self.p1; let Point { x: x2, y: y2 } = self.p2; 2.0 * ((x1 - x2).abs() + (y1 - y2).abs()) } }以self声明的方法会拿走调用者的所有权关联函数使用 :: 操作符来调用fn main() { let rectangle = Rectangle { // 关联函数的调用不是通过点操作符，而是使用 `::` p1: Point::origin(), p2: Point::new(3.0, 4.0), }; }方法使用 . 操作符调用println!("Rectangle perimeter: {}", rectangle.perimeter());struct Rectangle { width: u32, height: u32, } impl Rectangle { // 完成 area 方法，返回矩形 Rectangle 的面积 // fn area fn area(&self) -> u32 { self.width * self.height } } fn main() { let rect1 = Rectangle { width: 30, height: 50 }; assert_eq!(rect1.area(), 1500); }// 只填空，不要删除任何代码行! #[derive(Debug)] struct TrafficLight { color: String, } impl TrafficLight { pub fn show_state(&self) { // 如果这里使用 self 而不是 &self，就会拿走所有权 println!("the current state is {}", self.color); } } fn main() { let light = TrafficLight{ color: "red".to_owned(), }; // 不要拿走 `light` 的所有权 light.show_state(); // 否则下面代码会报错 println!("{:?}", light); }