《通过链表学习rust》笔记
1. 创建项目
$ cargo new --lib lists
Created library `lists` package
$ cd lists
2. 差的栈实现
第一种链表实现方式会在 src/first.rs
中编写,在 Cargo 自动生成的 src/lib.rs
开头写上一行:
pub mod first;
2.1. 内存布局
什么是链表呢?定义如下:
List a = Empty | Elem a (List a)
和类型(sum type)链表 List 要么是空表 Empty,要么持有一个元素 Elem,同时后面跟着下一个链表 List
和类型:可以具有不同类型的值的类型
用 Rust 写出这个函数式版的定义:
enum List {
Empty,
Elem(i32, List),
}
但是这里出现了递归定义
$ cargo build
Compiling lists v0.1.0
error[E0072]: recursive type `first::List` has infinite size
--> src/first.rs:2:1
|
2 | pub enum List {
| ^^^^^^^^^^^^^ recursive type has infinite size
3 | Empty,
4 | Elem(i32, List),
| ---- recursive without indirection
|
= help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `first::List` representable
rust无法计算出List
类型的大小,所以要用指针来代替
enum List {
Empty,
Elem(i32, Box<List>),
}
但是这种定义涉及到内存在栈和堆上的分配问题,比如:
let a: List = List::Elem(100, Box::new(List::Empty));
println!("{:?}", a);
let b: List = List::Elem(10, Box::new(a));
println!("{:?}", b);
运行得到
Elem(100, Empty)
Elem(10, Elem(100, Empty))
内存布局:
[] = 栈
() = 堆
[Elem A, 指针] -> (Elem B, 指针) -> (Empty 垃圾数据)
- rust的枚举体的内存分配:
- 枚举类型的变量需要用一些整数
tag
来指示它是该枚举类型中的哪一种变体(variant) - 同时它需要足够的空间来存储 T1、T2、… Tn 中最大的类型(可能需要额外的空间来满足内存对齐的要求)
- 枚举类型的变量需要用一些整数
- 有两个关键问题:
1.我们给一个没有存储数据信息的结点分配了空间
- Empty 变体只含有一位的信息
- 却占用了一个元素加一个指针的空间,因为它随时可能转变为 Elem 变体
- 为了减少多分配的空间,我们可以用一个新的类型来避免
enum List { Empty, ElemThenEmpty(i32), ElemThenNotEmpty(i32, Box<List>), }
这样无需为
Empty
分配空间了,但它没有解决第2个问题,内存分配不一致的问题- 其中一个结点却没有被分配堆空间
- 第1个结点分配在了栈上
空指针优化 每个枚举变量都会有标志来标明它是哪种变体。但如果是这样的枚举类型:
enum Foo { A, B(NonNullPtr), }
空指针优化就能起作用了。它可以节省标签占用的空间 如果是变体 A,就将储存内容全部置零 反之,非零内容则代表变体 B
- 为了应用空指针优化,又解决内存分配不一致的问题:
- 思想
- 对于我们声明的类型而言,如果说枚举体能让它持有若干值中的一种,那么结构体就能使它同时拥有多个值
- 据此,我们可以将原来的 List 类型拆成两部分:List 与 Node 类型
- 我们最好把存放元素的空间,与为下一链表所分配的空间分开考虑
- 这样一个链表要么是空表,要么“持有一个元素,同时后面跟着下一个链表”
- 应用空指针优化,需要把枚举体写成如下形式
enum List { Empty, Elem(Box<_>), }
- 我们通过用一个完全独立的类型来实现「持有一个元素,同时后面跟着下一个链表」
- 解决内存分配不一致问题
- 所以有链表结点都存在堆上
- 要保存的元素用结构体来表达
struct Node { elem: i32, next: List, }
- 另一种可能的布局:
[指针] -> (Elem A, 指针) -> (Elem B, 空指针) -> (Empty)
```
- 思想
得到新的链表:
#[derive(Debug)]
struct Node {
elem: i32,
next: List,
}
#[derive(Debug)]
enum List {
Empty,
Elem(Box<Node>),
}
使用链表:
fn main() {
let a = List::Elem(Box::new(Node {elem: 100, next: List::Empty}));
println!("a: {:?}", a);
match a {
List::Elem(ref node) => {
println!("a.elem: {:?}", node.elem);
println!("a.next: {:?}", node.next);
}
List::Empty => println!("a.elem: Empty"),
}
let b = List::Elem(Box::new(Node {elem: 10, next: a}));
println!("b: {:?}", b);
match b {
List::Elem(ref node) => {
println!("b.elem: {:?}", node.elem);
println!("b.next: {:?}", node.next);
}
List::Empty => println!("b.elem: Empty"),
}
}
得到结果:
a: Elem(Node { elem: 100, next: Empty })
a.elem: 100
a.next: Empty
b: Elem(Node { elem: 10, next: Elem(Node { elem: 100, next: Empty })
})
b.elem: 10
b.next: Elem(Node { elem: 100, next: Empty })
为了让别人能使用 List,我们将List访问权限设置为公有 pub:
struct Node {
elem: i32,
next: List,
}
pub enum List {
Empty,
More(Box<Node>),
}
但编译出错了:
❯ cargo build
Compiling lists v0.1.0 (/home/wilson/experiments/rust/lists) error[E0446]: private type `Node` in public interface
--> src/main.rs:10:8
|
2 | struct Node {
| ----------- `Node` declared as private
...
10 | Elem(Box<Node>),
| ^^^^^^^^^ can't leak private type
error: aborting due to previous error
For more information about this error, try `rustc --explain E0446`.
error: could not compile `lists`
To learn more, run the command again with --verbose.
问题在于公有枚举体的所有内部变体也都是公有的,而私有类型不能出现在公有的地方。理论上我们可以也把 Node 设为公有类型,但这不符合 Rust 编程风格,我们应该将实现细节隐藏起来。为达成这一点,我们可以将 List 设成结构体:
#[derive(Debug)]
struct Node {
elem: i32,
next: Link,
}
#[derive(Debug)]
enum Link {
Empty,
Elem(Box<Node>),
}
#[derive(Debug)]
pub struct List {
head: Link,
}
fn main() {
let a = Link::Elem(Box::new(Node {elem: 100, next: Link::Empty}));
println!("a: {:?}", a);
match a {
Link::Elem(ref node) => {
println!("a.elem: {:?}", node.elem);
println!("a.next: {:?}", node.next);
}
Link::Empty => println!("a.elem: Empty"),
}
let b = Link::Elem(Box::new(Node {elem: 10, next: a}));
println!("b: {:?}", b);
match b {
Link::Elem(ref node) => {
println!("b.elem: {:?}", node.elem);
println!("b.next: {:?}", node.next);
}
Link::Empty => println!("b.elem: Empty"),
}
let list = List {head: b};
println!("list: {:?}", list);
println!("list.head: {:?}", list.head);
}
运行后得到:
❯ cargo run
Compiling lists v0.1.0 (/home/wilson/experiments/rust/lists)
Finished dev [unoptimized + debuginfo] target(s) in 0.24s
Running `target/debug/lists`
a: Elem(Node { elem: 100, next: Empty })
a.elem: 100
a.next: Empty
b: Elem(Node { elem: 10, next: Elem(Node { elem: 100, next: Empty }) })
b.elem: 10
b.next: Elem(Node { elem: 100, next: Empty })
list: List { head: Elem(Node { elem: 10, next: Elem(Node { elem: 100
, next: Empty }) }) }
list.head: Elem(Node { elem: 10, next: Elem(Node { elem: 100, next:
Empty }) })
2.2. New 方法
我们创建好了链表的数据结构,现在要加入的是它的方法。首先是 new
方法
impl List {
fn new() -> Self {
List {head: Link::Empty}
}
}
可以用
Self
指代impl
块所实现的类型
2.3. 所有权初探
在 Rust 中,方法就是一类特殊的函数。它们拥有无须指明类型的 self
参数,self 参数主要有三种形式:self
、&mut self
、&self
。它们分别代表了 Rust 中主要的三种所有权:
self
代表值(value)- 值意味着真正的所有权
- 你可以移动它、销毁它、改变它
- 或者以引用的方式借出它
- 当你按值传递对象时,它会被移动到新的变量
- 值意味着真正的所有权
&mut self
:可变引用- 可变引用意味着对你不拥有的对象暂时有独占的访问权利
- 只要有了可变引用,那你就可以为所欲为了
&self
:共享引用- 共享引用意味着对你不拥有的对象暂时有共享的访问权利
2.4. Push 方法
因为push
会改变链表,所以我们用&mut self
impl List {
pub fn push(&mut self, elem: i32) {
let node = Node {
elem,
next: mem::replace(&mut self.head, Link::Empty),
}
self.head = Link::More(Box::new(node));
}
}
2.5. Pop 方法
pop
方法也会改写list
,所以仍用&mut self
。但pop
会遇到链表为空和链表非空的情况,所以:
impl List {
pub fn pop(&mut self) {
match mem::replace(&mut self.head, Link::Empty) {
Link::Empty => None,
Link::More(pnode) => {
self.head = pnode.next;
Some(pnode.elem)
}
}
}
}
2.6. 单元测试
- 一般来说,我们会尽量将我们的测试放在代码旁边
- 我们通常为测试创建一个新的名称空间,以避免与“真正的”代码发生冲突
- 我们可以使用mod来创建一个全新的内联文件
- 我们所要做的就是编写一个函数,并用
#[test]
标注它
// in first.rs
#[cfg(test)] // 只在测试时才编译这个模块,否则模块内的List导入但未使用
mod test {
use super::List; //因为我们创建了一个新模块,所以需要显式地导入`List`来使用它
#[test]
fn basics() {
// Check empty list behaves right
assert_eq!(list.pop(), None);}
}
- 因为我们创建了一个新模块,所以需要显式地导入
List
来使用它 - 因为我们只有在测试时使用了
List
,所以我们应该指出,只有在运行测试时才应该编译整个测试模块
2.7. Drop 方法
如果一个类型实现了一个称为Drop的特征,那么它就有一个析构函数,Drop
的声明如下:
pub trait Drop {
fn drop(&mut self);
}
为List
实现Drop
impl Drop for List {
fn drop(&mut self) {
let mut cur_link = mem::replace(&mut self.head, Link::Empty);
while let Link::More(pnode) = cur_link {
cur_link = mem::replace(&mut pnode.next, Link::Empty);
}
}
}
3 一个好的单链接堆栈
让我们添加一个名为second.rs
的新文件
// in lib.rs
pub mod first
pub mod second
3.1. 使用 Option
实际上可以改进的地方如下:
enum
用Option
表达enum Link { Empty, More(Box<Node>), }
相当于
Option<Box<Node>>
,再用type Link = Option<Box<Node>>
,于是我们得到新的List
数据结构写法:struct List { head: Link, } type Link = Option<Box<Node>>; struct Node { elem: i32, next: Link, }
mem::replace
可以用take
表示 实际上mem::replace(&mut option, none)
是非常常见的用法,rust用take
方法来实现pub fn take(&mut self) -> Option<T>
所以
mem::replce(&mut self.head, Link::Empty);
就相当于self.head.take()
match option { None => None, Some(x) => Some(y)}
是一个非常常见的习惯用法,它被称为map
map
接受一个函数,在Some(x)
中的x
上执行,生成Some(y)
中的y
- 我们可以编写一个合适的
fn
并将其传递给map
,但我们更愿意编写内联操作pub fn pop(&mut self) -> Option<i32> { self.head.take().map(|node| { self.head = node.next; Some(node.elem) }) }
3.2. Generic
把具体类型转变为泛型<T>
List
数据结构struct List<T> { head: Link<T>, } type Link<T> = Option<Box<Node<T>>>; struct Node<T> { elem: T, next: Link, }
-
List
的方法impl<T> List<T> { pub fn new() -> Self { List {head: None} } pub fn push(&mut self, elem: T) { let node = Node { elem, next: self.head.take(), } self.head = Some(node); } pub fn pop(&mut self) -> Option<T> { self.head.take().map(|node| { self.head = node.next; Some(node.elem) }) } } impl<T> Drop for List<T> { let cur_link = self.head.take(); while let Some(cur_node) = cur_link { cur_link = cur_node.next.take(); } }
3.3. Peek
我们所需要做的就是返回对列表头元素的引用(如果它存在的话)
impl List {
pub fn peek(&mut self) -> Option<&T> {
self.head.as_ref().map(|node| {
&node.elem
})
}
pub fn peek_mut(&mut self) -> Option<&mut T> {
self.head.as_mut().map(|node| {
&mut node.elem
})
}
}
加入测试
mod test {
#[test]
fn peek() {
let mut list = List::new();
assert_eq!(list.peek(), None);
assert_eq!(list.peek_mut(), None);
list.push(1); list.push(2); list.push(3);
assert_eq!(list.peek(), Some(&3));
assert_eq!(list.peek_mut(), Some(&mut 3));
}
}
但是当我们要修改值时要注意:
mod test {
#[test]
fn peek() {
let mut list = List::new();
list.push(1); list.push(2); list.push(3);
list.peek_mut().map(|&mut elem| {
elem = 100;
});
}
}
事实证明,这样写闭包的参数并不能说明value
是一个可变引用。相反,它创建了一个模式,将与闭包的参数进行匹配;|&mut value|
的意思是 “参数是一个可突变的引用,但请将它指向的值复制到value
中即可”。如果我们只是使用|value|
,那么value
的类型将是&mut i32
mod test {
#[test]
fn peek() {
let mut list = List::new();
list.push(1); list.push(2); list.push(3);
list.peek_mut().map(|elem| {
*elem = 100;
});
}
}
3.4. IntoIter
rust中迭代器的声明如下:
pub trait Iterator {
type Item;
fn next(&mut self) -> Option<Self::Item>;
}
迭代器产生Option<Self::Item>
的原因是接口合并了has_next
和get_next
概念。每个类型需要实现三种类型的迭代器:
Into
迭代:T
Mut
迭代:&mut T
- 迭代:
&T
- 创建一个
IntoIter
类型pub struct IntoIter<T>(List<T>);
- 为
List<T>
实现into_iter
方法,将List<T>
类型转换为IntoIter<T>
类型impl<T> List<T> { pub fn into_iter(self) -> IntoIter<T> { IntoIter(self) } }
- 为
IntoIter<T>
类型实现Iterator
特性impl<T> Iterator for IntoIter<T> { type Item = T; pub fn next(&mut self) -> Option<Self::Item> { self.0.pop() } }
- 写测试代码
mod test { #[test] fn into_iter() { let mut list = List::new(); list.push(1); list.push(2); list.push(3); let mut iter = list.into_iter(); assert_eq!(iter.next(), Some(3)); assert_eq!(iter.next(), Some(2)); assert_eq!(iter.next(), Some(1)); assert_eq!(iter.next(), None); } }
3.5. Iter
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,
next: self.head.take(),
});
self.head = Some(new_node);
}
pub fn pop(&mut self) -> Option<T> {
self.head.take().map(|pnode| {
self.head = pnode.next;
pnode.elem
})
}
pub fn peek(&self) -> Option<&T> {
self.head.as_ref().map(|node| &node.elem)
}
pub fn peek_mut(&mut self) -> Option<&mut T> {
self.head.as_mut().map(|node| &mut node.elem)
}
}
impl<T> Drop for List<T> {
fn drop(&mut self) {
let mut cur_link = self.head.take();
while let Some(mut cur_node) = cur_link {
cur_link = cur_node.next.take();
}
}
}
pub struct IntoIter<T>(List<T>);
impl<T> List<T> {
pub fn into_iter(self) -> IntoIter<T> {
IntoIter(self)
}
}
impl<T> Iterator for IntoIter<T> {
type Item = T;
fn next(&mut self) -> Option<T> {
self.0.head.take().map(|node| {
self.0.head = node.next;
node.elem
})
}
}
pub struct IterRef<'a, T>(Option<&'a Node<T>>);
impl<T> List<T> {
pub fn iter_ref<'a>(&'a self) -> IterRef<'a, T> {
IterRef(self.head.as_deref())
}
}
impl<'a, T> Iterator for IterRef<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
self.0.map(|node| {
self.0 = node.next.as_deref();
&node.elem
})
}
}
#[cfg(test)]
mod test {
use super::List;
#[test]
fn sec_list() {
let mut list = List::new();
list.push(1);
list.push(2);
list.push(3);
assert_eq!(list.peek(), Some(&3));
assert_eq!(list.peek_mut(), Some(&mut 3));
if let Some(elem) = list.peek_mut() {
*elem = 100;
}
assert_eq!(list.peek(), Some(&100));
list.peek_mut().map(|elem| *elem = 3);
// Check normal removal
assert_eq!(list.pop(), Some(3));
assert_eq!(list.pop(), Some(2));
// Push some more just to make sure nothing's corrupted
list.push(4);
list.push(5);
// Check normal removal
assert_eq!(list.pop(), Some(5));
assert_eq!(list.pop(), Some(4));
// Check exhaustion
assert_eq!(list.pop(), Some(1));
assert_eq!(list.pop(), None);
let mut list = List::new();
list.push(1);
list.push(2);
list.push(3);
let mut iter = list.into_iter();
assert_eq!(iter.next(), Some(3));
assert_eq!(iter.next(), Some(2));
assert_eq!(iter.next(), Some(1));
assert_eq!(iter.next(), None);
let mut list = List::new();
list.push(1);
list.push(2);
list.push(3);
let mut iter_ref = list.iter_ref();
assert_eq!(iter_ref.next(), Some(&3));
assert_eq!(iter_ref.next(), Some(&2));
assert_eq!(iter_ref.next(), Some(&1));
}
}
3.6. IterMut
根据IterRef
的实现:
impl<'a, T> Iterator for IterRef<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {...}
}
去糖后的真实代码是
impl<'a, T> Iterator for IterRef<'a, T> {
type Item = &'a T;
fn next<'b>(&'b mut self) -> Option<&'a T> {...}
}
next
的签名在输入和输出的生命期之间没有建立任何约束! 为什么我们要关心这个问题?这意味着我们可以无条件地重复调用 next
!
let mut list = List::new();
list.push(1); list.push(2); list.push(3);
let mut iter = list.iter();
let x = iter.next().unwrap();
let y = iter.next().unwrap();
let z = iter.next().unwrap();
对于共享引用来说,这绝对是好的,因为整个要点就是你可以同时拥有大量的引用。然而可变引用不能共存。关键就是它们是排他性的。
最终的结果是,使用安全代码编写IterMut
明显更难了(我们还没有讨论到这意味着什么……)。令人惊奇的是,IterMut
实际上可以完全安全地实现许多结构!我们将从以下几个方面入手。
我们先把Iter
代码改成可变的:
pub struct IterMut<'a, T> {
next: Option<&'a mut Node<T>>,
}
impl<T> List<T> {
pub fn iter_mut(&mut self) -> IterMut<'_, T> {
IterMut {next: self.head.as_deref_mut()}
}
}
impl<'a, T> Iterator for IterMut<'a, T> {
type Item = &'a mut T;
fn next(&mut self) -> Option<Self::Item> {
self.next.map(|node| {
self.next = node.next.as_deref_mut();
&mut node.elem
})
}
}
> cargo build
error[E0596]: cannot borrow `self.head` as mutable, as it is behind a `&` reference
--> src/second.rs:95:25
|
94 | pub fn iter_mut(&self) -> IterMut<'_, T> {
| ----- help: consider changing this to be a mutable reference: `&mut self`
95 | IterMut { next: self.head.as_deref_mut() }
| ^^^^^^^^^ `self` is a `&` reference, so the data it refers to cannot be borrowed as mutable
error[E0507]: cannot move out of borrowed content
--> src/second.rs:103:9
|
103 | self.next.map(|node| {
| ^^^^^^^^^ cannot move out of borrowed content
好吧,看起来我们这里有两个不同的错误。第一条看起来非常清楚,甚至告诉我们如何修复它!你不能将共享引用升级到可变引用,所以iter_mut
需要采用&mut self
。
pub fn iter_mut(&mut self) -> IterMut<'_, T> {
IterMut { next: self.head.as_deref_mut() }
}
那另一个呢?
哎呀! 其实我在上一节写iter impl
的时候不小心出了一个错误,我们只是运气好,才成功的!
我们刚刚第一次接触到Copy
的魔力。当我们介绍所有权时,我们说当你转移资源后,你将不能再使用它。对于某些类型,这是很有道理的。我们的好朋友Box
为我们管理着堆上的分配,我们当然不希望两段代码都认为他们需要释放它的内存。
然而对于其他类型来说,这就是垃圾。整数没有所有权语义,它们只是无意义的数字!这就是为什么整数被标记为Copy
的原因。众所周知,Copy
类型是可以通过比特复制来完美拷贝的。因此,它们有一个超级能力:当移动时,旧的值仍然可以使用。因此,你甚至可以将Copy
类型从一个引用中移出而不需要replace
替换!
rust
中的所有数字基元 (i32, u64, bool, f32, char
, 等等…) 都是 Copy
。你也可以声明任何用户定义的类型也是Copy
,只要它的所有组件都是Copy
。
关键是为什么这段代码能用,共享引用也是Copy
! 因为&
是Copy
,Option<&>
也是Copy
。所以当我们做self.next.map
的时候,因为Option
只是被Copy
了,所以很正常。现在我们不能这样做,因为&mut
不是Copy
(如果你复制了一个&mut
,你就会有两个&mut
到内存的同一个位置,这是禁止的)。相反,我们应该正确地对Option
应用take
来获取它。
fn next(&mut self) -> Option<Self::Item> {
self.next.take().map(|node| {
self.next = node.next.as_deref_mut();
&mut node.elem
})
}
cargo build
卧槽,IterMut
编译通过了!
我们来测试一下:
#[test]
fn iter_mut() {
let mut list = List::new();
list.push(1); list.push(2); list.push(3);
let mut iter = list.iter_mut();
assert_eq!(iter.next(), Some(&mut 3));
assert_eq!(iter.next(), Some(&mut 2));
assert_eq!(iter.next(), Some(&mut 1));
}
> cargo test
Running target/debug/lists-5c71138492ad4b4a
running 6 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::iter_mut ... ok
test second::test::into_iter ... ok
test second::test::iter ... ok
test second::test::peek ... ok
test result: ok. 7 passed; 0 failed; 0 ignored; 0 measured
它正常工作了,卧槽,为什么?
我们刚刚实现了一段代码,它接收了一个单链的列表,并返回一个列表中的每一个元素的可变的引用(最多一次)。而且它是经过静态验证的,所以是完全安全的。
如果你问我的话,这是个大问题。这有几个原因:
- 我们对
Option<&mut>
使用了take
,所以我们有专属的访问权来获取可变的引用。不需要担心有人再看它 - Rust明白,把一个可变引用共享到指向结构的子字段中是可以的,因为没有办法 “往上走”,而且它们肯定是不相干的
事实证明,你也可以应用这个基本逻辑来为一个数组或一棵树获得一个安全的IterMut
! 你甚至可以把迭代器做成DoubleEnded
,这样你就可以从前面和后面同时消耗迭代器了! 哇!
pub struct IterMut<'a, T>(Option<&'a mut Node<T>>);
impl<'a, T> List<T> {
pub fn iter_mut(&'a mut self) -> IterMut<'a, T> {
IterMut(self.head.as_deref_mut().map(|node| node))
}
}
impl<'a, T> Iterator for IterMut<'a, T> {
type Item = &'a mut T;
fn next(&mut self) -> Option<Self::Item> {
self.0.take().map(|node| {
self.0 = node.next.as_deref_mut();
&mut node.elem
})
}
}
4 一个持久的单链栈
好了,我们已经掌握了可变单链栈的技巧。
让我们通过编写一个持久不变的单链列表,从单一所有权转向共享所有权。这将是函数式程序员所熟悉和喜爱的列表。你可以得到头或者尾巴,把一个链表的头放在另一个链表的尾巴上……基本上就是这样。
在这个过程中,我们大体上只会熟悉Rc
和Arc
,但这将为下一个改变游戏的列表做准备。
让我们添加一个新的文件,叫做third.rs
。
pub mod frist;
pub mod second;
pub mod third;
4.1 Layout
好了,回到布局的画板上。
关于持久化列表最重要的一点是,你基本上可以无代价的操作列表的尾部。
比如说,在持久化列表中,这是一个常见的工作量:
list1 = A -> B -> C -> D
list2 = tail(list1) = B -> C -> D
list3 = push(list2, X) = X -> B -> C -> D
但在最后,我们希望内存是这样的:
list1 -> A ---+
|
v
list2 ------> B -> C -> D
^
|
list3 -> X ---+
Boxes
不能达到这个效果,因为B
的所有权是共享的。谁应该释放它?如果我删除list2
,会释放B
吗?如果使用了Boxes
的话,意味着我们希望如此。
函数式语言–实际上几乎所有其他语言–都可以通过使用垃圾回收来解决这个问题。有了垃圾收集的魔力,B
只有在每个人都停止查询它之后才会被释放。万岁!
Rust没有任何类似于这些语言的垃圾收集器。他们有跟踪GC,它会在运行时挖出所有的内存,并自动找出哪些是垃圾。相反,Rust今天所拥有的是引用计数。引用计数可以被认为是一个非常简单的GC。对于许多工作应用来说,它的消耗明显低于跟踪收集器,如果你设法建立周期,消耗量可以忽略不计。但是,嘿,这就是我们的全部了! 值得庆幸的是,对于我们的案例来说,我们永远不会遇到周期问题(你可以试着自己证明这一点–我肯定不会)。
那么我们如何进行引用计数的垃圾收集呢?Rc
! Rc
就像Box一样,但我们可以复制它,只有当所有由它派生的Rc被析构时,它的内存才会被释放。不幸的是,这种灵活性付出了严重的代价:我们只能对它的内部进行共享引用。这意味着我们无法真正从其中任一个列表中取出数据,也无法对它们进行修改。
那么我们的布局会是什么样子呢?嗯,之前我们有:
pub struct List<T> {
head: Link<T>,
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
我们能只把Box
改为Rc
吗?
// in thrid.rs
use std::rc::Rc;
pub struct List<T> {
head: Link<T>,
}
type Link<T> = Option<Rc<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
cargo build
warning: field is never used: `head`
--> src/third.rs:4:5
|
4 | head: Link<T>,
| ^^^^^^^^^^^^^
|
= note: #[warn(dead_code)] on by default
warning: field is never used: `elem`
--> src/third.rs:10:5
|
10 | elem: T,
| ^^^^^^^
warning: field is never used: `next`
--> src/third.rs:11:5
|
11 | next: Link<T>,
| ^^^^^^^^^^^^^
似乎是合法的。Rust继续是完全琐碎的写作。我敢打赌,我们可以用Rc
找到并替换Box
,然后就可以了。
4.2. Basics
我们现在已经知道了很多Rust
的基础知识,所以我们可以再做很多简单的事情。
对于构造函数,我们又可以直接复制粘贴。
impl<T> List<T> {
pub fn new() -> Self {
List {head: None}
}
}
push
和pop
已经没有意义了。相反,我们可以提供append
和tail
,它们提供的东西大致相同。
让我们从append
开始。它接收一个list
和一个元素,然后返回一个List
。就像可变 list
的情况一样,我们要做一个新的节点,它的下一个值是旧的 list
。唯一新奇的是如何获得下一个值,因为我们不允许改变任何东西。
我们祈祷的答案就是Clone
特性。Clone
几乎被每个类型都实现了,它提供了一种通用的方法来获取 “另一个像这个一样的”,它只给定一个共享引用,在逻辑上是不相干的。它就像C++
中的复制构造函数,但它从来没有被隐式调用。
特别是Rc
使用Clone
作为增量引用数的方式。所以,我们不是把一个Box
移到子列表中,而是直接克隆旧列表的头部。我们甚至不需要在头部进行匹配,因为Option
暴露了一个Clone
实现,它完全可以完成我们想要的事情。
好吧,让我们试试看:
pub fn append(&self, elem: T) -> List<T> {
List {head: Some(Rc::new(Node {
elem,
next: self.head.clone(),
}))}
}
> cargo build
warning: field is never used: `elem`
--> src/third.rs:10:5
|
10 | elem: T,
| ^^^^^^^
|
= note: #[warn(dead_code)] on by default
warning: field is never used: `next`
--> src/third.rs:11:5
|
11 | next: Link<T>,
| ^^^^^^^^^^^^^
哇,Rust对实际使用字段的态度真的很精明。它告诉我们,没有消费者能够真正观察到这些字段的使用情况! 不过,我们目前看来还是不错的。
tail
是这个操作的逻辑反转。它接收一个列表,然后返回整个列表,并删除第一个元素。所有这些都是克隆列表中的第二个元素(如果它存在的话)。让我们试试这个。
pub fn tail(&self) -> List<T> {
List { head: self.head.as_ref().map(|node| node.next.clone()) }
}
> cargo build
error[E0308]: mismatched types
--> src/third.rs:27:22
|
27 | List { head: self.head.as_ref().map(|node| node.next.clone()) }
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `std::rc::Rc`, found enum `std::option::Option`
|
= note: expected type `std::option::Option<std::rc::Rc<_>>`
found type `std::option::Option<std::option::Option<std::rc::Rc<_>>>`
Hrm, 我们搞砸了。map
期望我们返回一个Y
,但这里我们返回的是Option<Y>
。幸运的是,这是另一种常见的Option
模式,我们可以使用and_then
让我们返回一个Option
。
pub fn tail(&self) -> List<T> {
List {head: self.head.as_ref().and_then(|node| node.next.clone()) }
}
> cargo build
好极了!
现在我们有了tail
,我们应该提供head
,它返回对第一个元素的引用。这只是从可变列表中peek
查看到的:
pub fn head(&self) -> Option<&T> {
self.head.as_ref().map(|node| &node.elem)
}
漂亮!
这样的功能已经足够我们测试了:
#[cfg(test)]
mod test {
use super::List;
#[test]
fn baiscs() {
let list = List::new();
assert_eq!(list.head(), None);
let list = list.append(1).append(2).append(3);
assert_eq!(list.head(), Some(&3));
let list = list.tail();
assert_eq!(list.head(), Some(&2));
let list = list.tail();
assert_eq!(list.head(), Some(&1));
let list = list.tail();
assert_eq!(list.head(), None);
// 确认空链表tail也工作
let list = list.tail();
assert_eq!(list.head(), None);
}
}
> cargo test
Running target/debug/lists-5c71138492ad4b4a
running 5 tests
test first::test::basics ... ok
test second::test::into_iter ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test third::test::basics ... ok
test result: ok. 5 passed; 0 failed; 0 ignored; 0 measured
完美!
Iter
也与我们的可变列表相同:
pub struct Iter<'a, T> {
next: Option<&'a Node<T>>,
}
impl<T> List<T> {
pub fn iter(&self) -> Iter<'_, T> {
Iter { next: self.head.as_deref() }
}
}
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
self.next.map(|node| {
self.next = node.next.as_deref();
&node.elem
})
}
}
#[test]
fn iter() {
let list = List::new().append(1).append(2).append(3);
let mut iter = list.iter();
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&1));
}
cargo test
Running target/debug/lists-5c71138492ad4b4a
running 7 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test second::test::into_iter ... ok
test second::test::peek ... ok
test third::test::basics ... ok
test third::test::iter ... ok
test result: ok. 6 passed; 0 failed; 0 ignored; 0 measured
谁说过动态类型更容易?
注意,我们不能为这种类型实现IntoIter
或IterMut
。我们只能对元素进行共享访问。
4.3. Drop
和可变列表一样,我们也有一个递归的析构器问题。诚然,对于不可变列表来说,这并不是一个很糟糕的问题:如果我们曾经在某个地方碰到过另一个列表的头的节点,我们不会递归地放弃它。然而这仍然是一个我们应该关心的事情,如何处理并不是那么清楚。我们之前是这样解决的。
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();
}
}
}
问题是loop
中
cur_link = boxed_node.next.take();
这是在Box
里面修改Node
,但是我们不能用Rc
来做,它只给我们共享的访问权,因为任意数量的其他Rc
都可能指向它。
但是如果我们知道我们是最后一个知道这个节点的列表,其实把Node
移出Rc
就可以了。然后我们也可以知道什么时候停止:每当我们不能把Node
提取出来的时候。
而你看,Rc
有一个方法正是这样做的:try_unwrap
:
impl<T> Drop for List<T> {
fn drop(&mut self) {
let mut head = self.head.take();
while let Some(node) = head {
if let Ok(mut node) = Rc::try_unwrap(node) {
head = node.next.take();
} else {
break;
}
}
}
}
> cargo test
Compiling lists v0.1.0 (/Users/ABeingessner/dev/too-many-lists/lists)
Finished dev [unoptimized + debuginfo] target(s) in 1.10s
Running /Users/ABeingessner/dev/too-many-lists/lists/target/debug/deps/lists-86544f1d97438f1f
running 8 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::into_iter ... ok
test second::test::iter ... ok
test second::test::iter_mut ... ok
test second::test::peek ... ok
test third::test::basics ... ok
test third::test::iter ... ok
test result: ok. 8 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
好极了,干得漂亮!
4.4. Arc
使用不可变链表的一个原因是为了跨线程共享数据。毕竟共享的可变状态是万恶之源,解决这个问题的一个方法就是永远杀死可变部分。
只是我们的列表根本不是线程安全的。为了做到线程安全,我们需要原子地摆弄引用计数。否则,两个线程可能会尝试递增引用计数,而只有一个会发生。那么列表可能会过早地被释放!
为了获得线程安全,我们必须使用Arc
。Arc
与Rc
完全相同,只是引用计数是原子化修改的。如果你不需要的话,这有一点开销,所以Rust
暴露了这两个功能。我们需要做的就是把每一个对 Rc
的引用替换为 std::sync::Arc
。就是这样。我们的线程安全了。
但这提出了一个有趣的问题:我们如何知道一个类型是否是线程安全的?我们会不会不小心搞砸了?
不!在 Rust
中,你不能搞砸线程安全。
之所以如此,是因为Rust
用两个特性以一流的方式来模拟线程安全。Send
和Sync
.
如果一个类型可以安全地移动到另一个线程,那么它就是Send
。如果一个类型在多个线程之间共享是安全的,那么它就是Sync
。也就是说,如果T
是Sync
,&T
就是Send
。在这种情况下,安全意味着不可能引起数据竞争,(不要误解为更一般的竞争条件问题)。
这些都是标记性特征,这是一种花哨的说法,它们是完全不提供接口的特征。你要么是发送,要么不是。这只是一个其他API
可以要求的属性。如果你不是适当的Send
,那么静态上就不可能被发送到不同的线程! 很好!
Send
和Sync
也是根据你是否完全由Send
和Sync
类型组成而自动派生的特征。这类似于只有由Copy
类型构成时才能实现Copy
,但如果你是Copy
类型,我们就会自动去实现它。
几乎每个类型都是Send
和Sync
。大多数类型都是Send
,因为它们完全拥有自己的数据。大多数类型是Sync
,因为跨线程共享数据的唯一方法是把它们放在一个共享引用的后面,这使得它们是不可改变的。
然而,有一些特殊的类型违反了这些属性:那些具有内部可变性的类型。到目前为止,我们只真正地与继承的可变性(也就是外部可变性)进行了交互:一个值的可变性是由它的容器的可变性继承而来的。也就是说,你不能因为你觉得喜欢而随机突变一个不可变值的某个字段。
内部可变性类型违反了这一点:它们让你通过共享引用进行改变。内部可变性有两大类:单元格cells
,它只在单线程上下文中工作;以及在多线程上下文中工作的锁locks
。由于显而易见的原因,当你能使用单元格cells
时,单元格cell
开销更小的。还有原子atomics
,它是类似锁的原语。
那么这些和Rc
和Arc
有什么关系呢?好吧,它们都使用内部可变性作为它们的引用计数。更糟糕的是,这个引用计数是在每个实例之间共享的!Rc
只是使用一个单元格cell
,这意味着它不是线程安全的。Arc
使用原子atomic
,这意味着它是线程安全的。当然,你不能通过把一个类型放在Arc
中就神奇地使它成为线程安全的。Arc
只能像其他类型一样派生出线程安全。
我真的真的不想深入讨论原子内存模型或非派生的Send实现的细节。不用说,随着您深入了解Rust的线程安全故事,事情会变得更加复杂。作为一个高级使用者,你真的不需要去思考它。
4.5. Final Code
use std::rc::Rc;
type Link<T> = Option<Rc<Node<T>>>;
pub struct List<T> {
head: Link<T>,
}
struct Node<T> {
elem: T,
next: Link<T>,
}
impl<T> List<T> {
pub fn new() -> Self {
List { head: None }
}
pub fn append(&self, elem: T) -> Self {
List {
head: Some(Rc::new(Node {
elem,
next: self.head.clone(),
})),
}
}
pub fn tail(&self) -> Self {
List {
head: self.head.as_ref().and_then(|node| node.next.clone()),
}
}
pub fn head(&self) -> Option<&T> {
self.head.as_deref().map(|node| &node.elem)
}
}
pub struct IterRef<'a, T>(Option<&'a Node<T>>);
impl<T> List<T> {
pub fn iter_ref(&self) -> IterRef<'_, T> {
IterRef(self.head.as_deref())
}
}
impl<'a, T> Iterator for IterRef<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
self.0.map(|node| {
self.0 = node.next.as_deref();
&node.elem
})
}
}
impl<T> Drop for List<T> {
fn drop(&mut self) {
let mut head = self.head.take();
while let Some(node) = head {
if let Ok(mut node) = Rc::try_unwrap(node) {
head = node.next.take();
} else {
break;
}
}
}
}
#[cfg(test)]
mod test {
use super::List;
#[test]
fn basics() {
let list = List::new();
assert_eq!(list.head(), None);
let list = list.append(1).append(2).append(3);
assert_eq!(list.head(), Some(&3));
let list = list.tail();
assert_eq!(list.head(), Some(&2));
let list = list.tail();
assert_eq!(list.head(), Some(&1));
let list = list.tail();
assert_eq!(list.head(), None);
let list = list.tail();
assert_eq!(list.head(), None);
}
#[test]
fn iter_ref() {
let list = List::new().append(1).append(2).append(3);
let mut iter_ref = list.iter_ref();
assert_eq!(iter_ref.next(), Some(&3));
assert_eq!(iter_ref.next(), Some(&2));
assert_eq!(iter_ref.next(), Some(&1));
}
}
5. A Bad Safe Deque
现在,我们已经看到了Rc
,听说了内部可变,这给了一个有趣的想法…也许我们可以通过Rc
实现可变。如果是这样的话,也许我们可以完全安全地实现一个双链表!
在这个过程中,我们将会熟悉内部的可变性,并且可能会艰难地认识到安全并不意味着正确。双链表很难,而且我总是在某个地方犯错误。
让我们添加一个名为fourth.rs
的新文件
// in lib.rs
pub mod first;
pub mod second;
pub mod third;
pub mod fourth;
免责声明:这一章基本上证明了这是一个非常糟糕的想法。
5.1. Layout
我们设计的关键是RefCell
类型。RefCell
的核心是一对方法:
fn borrow(&self) -> Ref<'_, T>;
fn borrow_mut(&self) -> RefMut<'_, T>;
borrow
和borrow_mut
的规则与&
和&mut
的规则完全相同:你可以随意调用borrow
,但borrow_mut
要求排他性。
RefCell
并不是静态地强制它们,而是在运行时强制它们。如果你违反了规则,RefCell
就会panic
,让程序崩溃。为什么它返回这些Ref
和RefMut
的东西?它们的行为和Rc
很像,只是引用而已。他们还会保持RefCell
的借用,直到它们超出了范围。我们稍后会讲到。
现在,有了Rc
和RefCell
,我们可以成为… 一个难以置信的冗长的、可普遍突变的、不能收集周期的垃圾收集语言。Y-yaaaaay……
好了,我们要做双链路。这意味着每个节点都有一个指向上一个节点和下一个节点的指针。同时,List
本身也有一个指向第一个节点和最后一个节点的指针。这样我们就可以在列表的两端快速插入和删除。
所以,我们可能想要这样的东西:
use std::rc::Rc;
use std::cell::RefCell;
pub struct List<T> {
head: Link<T>,
tail: Link<T>,
}
type Link<T> = Option<Rc<RefCell<Node<T>>>>;
struct Node<T> {
elem: T,
next: Link<T>,
prev: Link<T>,
}
5.2. Building
好了,我们先从建立列表开始。这个新系统很直接,new
还是很琐碎的,只要把所有字段都None
掉就可以了。另外,由于它变得有点笨拙,让我们再使用一个Node
构造函数
impl<T> Node<T> {
fn new(elem: T) -> Rc<RefCell<Self>> {
Rc::new(RefCell::new(Node {
elem,
prev: None,
next: None,
}))
}
}
impl<T> List<T> {
pub fn new() -> Self {
List { head: None, tail: None }
}
}
> cargo build
**一堆死代码警告但已建立成功**
耶!
现在,让我们尝试写push
到列表的前面。因为双链表要复杂得多,所以我们需要做更多的工作。单链表操作可以简化为简单的一行操作,而双链表操作则相当复杂。
特别地,我们现在需要特别处理空列表周围的一些边界情况。大多数操作将只触及头部或尾部指针。然而,当切换到空列表或从空列表切换时,我们需要同时编辑这两个列表。
对我们来说,验证我们的方法是否合理的一个简单方法是,我们保持以下不变性:
- 每个节点都应该有两个指向它的指针
- 列表中间的每个节点由其前任和后继指向,而两端的节点则由列表本身指向。
让我们试一试吧:
pub fn push_front(&mut self, elem: T) {
// 新节点需要+2个链接,其他节点都应该是+0
let new_node = Node::new(elem);
match self.head.take() {
Some(old_head) => {
//非空列表,需要连接old_head
old_head.prev = Some(new_head.clone()); // +1 new_head
new_head.next = Some(old_head); // +1 old_head
self.head = Some(new_head); // +1 new_head, -1 old_head
// 总计:+2 new_head, +0 old_head -- OK!
}
None => {
// 空列表,需要设置尾部
self.tail = Some(new_head.clone()); // +1 new_head
self.head = Some(new_head); // +1 new_head
// 总计:+2 new_head -- OK!
}
}
}
> cargo build
error[E0609]: no field `prev` on type `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>`
--> src/fourth.rs:39:26
|
39 | old_head.prev = Some(new_head.clone()); // +1 new_head
| ^^^^ unknown field
error[E0609]: no field `next` on type `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>`
--> src/fourth.rs:40:26
|
40 | new_head.next = Some(old_head); // +1 old_head
| ^^^^ unknown field
好吧。编译器错误。良好的开端。
为什么我们不能访问节点上的prev
和next
字段?之前我们只有Rc<Node>
时,它可以工作。看来RefCell
有点碍事了。我们应该查阅一下文档。
具有动态检查借位规则的可变内存位置
有关更多信息,请参阅模块级文档
共享可变容器。Cell<T>
和RefCell<T>
类型的值可以通过共享引用(即共同的&T
类型)发生突变,而大多数Rust
类型只能通过唯一引用(&mut T
)发生突变。我们说Cell<T>
和RefCell<T>
提供了“内部突变性”,与典型的Rust类型表现出“继承突变性”相反。
Cell
类型有两种:Cell<T>
和RefCell<T>
。Cell<T>
提供了get
和set
方法,这些方法可以通过一个方法调用来更改内部值。Cell<T>
只与实现复制的类型兼容。对于其他类型,必须使用RefCell<T>
类型,在突变之前获取写锁。
RefCell<T>
使用Rust
的生命周期来实现“动态借用”,在这个过程中,人们可以声明对内部值的临时、独占、可变访问。RefCell<T>
的借用是在“运行时”被跟踪的,不像Rust的原生引用类型是在编译时完全静态跟踪的。因为RefCell<T>
的借用是动态的,所以可以尝试去借用一个已经被可变地借用的值;当这种情况发生时,会导致线程panic
。
何时选择内部可变性
比较常见的继承可变性,必须有唯一的访问权限才能改变一个值,是使Rust能够有力地推理指针别名的关键语言元素之一,从而静态地防止崩溃bug。因此,继承的可变性是首选,而内部可变性是最后的手段。由于单元格类型在不允许突变的地方可以实现突变,所以在某些情况下,内部突变可能是合适的,甚至是必须使用的,如:
- 将继承的可变性根引入共享类型
- 逻辑不可变方法的实现细节
Clone
的可变实现
在共享类型中引入继承变异性根部
共享的智能指针类型,包括Rc<T>
和Arc<T>
,提供了可以在多方之间克隆和共享的容器。因为包含的值可能是多重别名的,所以它们只能作为共享引用而不是可变引用借来。如果没有单元格,就根本不可能改变共享框中的数据。
在共享指针类型中放置RefCell<T>
来重新引入可变性是很常见的
use std::collections::HashMap;
use std::cell::RefCell;
use std::rc::Rc;
fn main() {
let shared_map: Rc<RefCell<_>> = Rc::new(RefCell::new(HashMap::new()));
shared_map.borrow_mut().insert("africa", 92388);
shared_map.borrow_mut().insert("kyoto", 11837);
shared_map.borrow_mut().insert("piccadilly", 11826);
shared_map.borrow_mut().insert("marbles", 38);
}
注意,这个例子使用的是Rc<T>
,而不是Arc<T>
。RefCell<T>
用于单线程场景。如果在多线程环境中需要共享的可变性,可以考虑使用Mutex<T>
。
嘿,Rust的文档仍然很棒。
我们关心的是以下这一行:
shared_map.borrow_mut().insert("africa", 92388);
尤其是borrow_mut
的东西。 似乎我们需要显式借用RefCell
。 .
运算符不会为我们这样做。 奇怪, 咱们试试吧:
pub fn push_front(&mut self, elem: T) {
let new_head = Node::new(elem);
match self.head.take() {
Some(old_head) => {
old_head.borrow_mut().prev = Some(new_head.clone());
new_head.borrow_mut().next = Some(old_head);
self.head = Some(new_head);
}
None => {
self.tail = Some(new_head.clone());
self.head = Some(new_head);
}
}
}
> cargo build
warning: field is never used: `elem`
--> src/fourth.rs:12:5
|
12 | elem: T,
| ^^^^^^^
|
= note: #[warn(dead_code)] on by default
嘿,它构建通过了! Docs又赢了。
list new_head Node Node Node
+-------+ +--+--------+--+ +-----------+--+ +-----------+--+ +-----------+-----+
| head <----+ | prev | +----->prev | +----> prev | +----> prev | |
+-------| +--------+ | +--------+ | +--------+ | +--------+ |
| tail <----+ | next <-----+ | next <------+ | next <------+ | next | |
+-------+ | +--------+ +--------+ +--------+ +--------+ |
| | elem | | elem | | elem | | elem | |
| +--------+ +--------+ +--------+ +--------+ |
| |
| |
+--------------------------------------------------------------------+
list
+-------+ new_head
| head <----+--+--------+ +-------+
+-------| | | prev <----+-+ None |
| tail <----+ +--------| | +-------+
+-------+ | next <----+
+--------+
| elem |
+--------+
list new_head old_head
+-------+ +---+--------+--+ +------------+ +--+-------+
| &head<----+ | prev | +--------> prev | | | None |
+-------| +--------+ | +--------+ | +-------+
| &tail<----+ | next <-------+ | next <----+
+-------+ | +--------+ | +--------+
| | elem | | | elem |
| +--------+ | +--------+
| |
+-------------------+
5.3. Breaking
pop_front
应该与push_front
具有相同的基本逻辑,但必须是向后的。 咱们试试吧:
pub fn pop_front(&mut self) -> Option<T> {
// 需要取出old_head,确保它是 -2
self.head.take().map(|old_head| { // -1 old_head
match old_head.borrow_mut().next.take() {
Some(new_head) => { // -1 new_head
// 非空list
new_head.borrow_mut().prev.take(); // -1 old
self.head = Some(new_head); // +1 new
// 总计:-2 old, +0 new
}
None => {
// 空list
self.tail.take(); // -1 old
// 总计:-2 old, (no new)
}
}
old_head.elem
})
}
> cargo build
error[E0609]: no field `elem` on type `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>`
--> src/fourth.rs:64:22
|
64 | old_head.elem
| ^^^^ unknown field
确认 RefCells
。 我猜要再来一次borrow_mut
…
pub fn pop_front(&mut self) -> Option<T> {
self.head.take().map(|old_head|{
match old_head.borrow_mut().next.take() {
Some(new_head) => {
new_head.borrow_mut().prev.take();
self.head = Some(new_head);
}
None => {
self.tail.take();
}
}
old_head.borrow_mut().elem
})
}
cargo build
error[E0507]: cannot move out of borrowed content
--> src/fourth.rs:64:13
|
64 | old_head.borrow_mut().elem
|
Hrm… 借用mut
只能得到一个&mut Node<T>
,但我们不能提出这个节点!
我们需要一些能把RefCell<T>
转换成T
的东西。让我们看看文档中有没有类似的东西。
fn into_inner(self) -> T
Consumes the RefCell, returning the wrapped value.
这看起来很有希望!
old_head.into_inner().elem
> cargo build
error[E0507]: cannot move out of an `Rc`
--> src/fourth.rs:64:13
|
64 | old_head.into_inner().elem
| ^^^^^^^^ cannot move out of an `Rc`
啊,见鬼。into_inner
想要将RefCell
移出,但我们不能,因为它在Rc
中。正如我们在前一章中看到的,Rc<T>
只允许我们获得对其内部的共享引用。这是有道理的,因为这就是引用计数指针的全部意义:它们是共享的!
当我们想要为引用计数列表实现Drop
时,这是一个问题,解决方案是相同的:Rc::try_unwrap
,它将一个Rc
的内容移出,如果它的refcount
是1。
Rc::try_unwrap(old_head).unwrap().into_inner().elem
Rc::unwrap
返回一个Result<T, Rc<T>>
。Result
基本上是一个通用Option
,其中None
情况下有相关的数据。在本例中,您试图展开的Rc
。因为我们不关心它失败的情况(如果我们正确地编写了程序,它必须成功),所以我们只对它调用unwrap
。
无论如何,让我们看看接下来我们会遇到什么编译错误(让我们面对它,肯定会有一个)。
> cargo build
error[E0599]: no method named `unwrap` found for type `std::result::Result<std::cell::RefCell<fourth::Node<T>>, std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>>` in the current scope
--> src/fourth.rs:64:38
|
64 | Rc::try_unwrap(old_head).unwrap().into_inner().elem
| ^^^^^^
|
= note: the method `unwrap` exists but the following trait bounds were not satisfied:
`std::rc::Rc<std::cell::RefCell<fourth::Node<T>>> : std::fmt::Debug`
啊。为Result
进行unwrap
解包要求可以调试打印错误情况。RefCell<T>
仅在T
实现Debug
时才实现。Node
没有实现调试。
我们不这样做,而是通过ok
将Result
转换为Option
来解决这个问题:
Rc::try_unwrap(old_head).ok().unwrap().into_inner().elem
cargo build
是的。我们成功了。
我们实现了push
和pop
。
-
list.head = None, list.tail = None
list +-------+ | head <----+--+-------+ +-------| | + None | | tail <----+| +-------+ +-------+
-
list
有一个链表list +-------+ new_head | head <----+--+--------+ +-------+ +-------| | | prev <----+-+ None | | tail <----+ +--------| | +-------+ +-------+ | next <----+ +--------+ | elem | +--------+
-
list
有多个链表
+-------------------+
list | old_head | new_head
+-------+ | +--------+ +---+--------+ +--+-------+
| &head<----+ | prev | | | prev | | | None |
+-------| +--------+ | +--------+ | +-------+
| &tail<----+ | next | | | next <----+
+-------+ | +--------+ | +--------+
| | elem | | | elem |
| +--------+ | +--------+
+-------------------+
让我们通过旧的stack basic
来进行测试(因为这是我们到目前为止所实现的所有内容)
#[cfg(test)]
mod test {
use super::List;
#[test]
fn baiscs() {
let mut list = List::new();
// Check empty list behaves right
assert_eq!(list.pop_front(), None);
// Populate list
list.push_front(1);
list.push_front(2);
list.push_front(3);
// Check normal removal
assert_eq!(list.pop_front(), Some(3));
assert_eq!(list.pop_front(), Some(2));
// Push some more just to make sure nothing's corrupted
list.push_front(4);
list.push_front(5);
// Check normal removal
assert_eq!(list.pop_front(), Some(5));
assert_eq!(list.pop_front(), Some(4));
// Check exhaustion
assert_eq!(list.pop_front(), Some(1));
assert_eq!(list.pop_front(), None);
}
}
现在我们可以正确地从列表中删除东西,我们可以实现Drop
。这一次Drop
在概念上更有趣一些。以前我们费心为栈实现Drop
只是为了避免无限递归,现在我们需要实现Drop
来让任何事情发生。
Rc
不能处理循环。如果有一个循环,所有的东西都会让其他的东西保活。事实证明,一个双链表只是一个由小循环组成的大链!因此,当我们删除我们的列表,两个末端节点的refcounts
会被减为1.…然后什么也不会发生。好吧,如果我们的列表只包含一个节点,我们就可以了。但理想情况下,如果一个列表包含多个元素,它也应该正常工作。也许这只是我的想法。
正如我们所看到的,删除元素有点痛苦。所以最简单的方法就是一直弹出直到没有:
impl<T> Drop for List<T> {
fn drop(&mut self) {
while self.pop_front().is_some() {}
}
}
(我们其实可以使用可变堆栈来实现这一点,但捷径是为那些理解事物的人准备的!)
我们可以看看push
和pop
的反向版本的实现,但它们只是复制-粘贴作业,我们将在本章后面讨论。现在让我们看看更有趣的东西
5.4. Peek
好了,我们通过了push
和pop
。不瞒你说,我当时有点激动。编译时的正确性是一种致命的毒药。
让我们做一些简单的事情来冷静一下:让我们先实现peek_front
。
list new_head old_head
+-------+ +---+--------+--+ +------------+ +--+-------+
| &head<----+ | prev | +--------> prev | | | None |
+-------| +--------+ | +--------+ | +-------+
| &tail<----+ | next <-------+ | next <----+
+-------+ | +--------+ | +--------+
| | elem | | | elem |
| +--------+ | +--------+
+-------------------+
这在以前总是很容易的。还是很简单,对吧
事实上,我想我可以直接复制粘贴
pub fn peek_front(&self) -> Option<&T> {
self.head.as_ref().map(|node| &node.elem)
}
等一下。 这次不是
pub fn peek_front(&self) -> Option<&T> {
self.head.as_ref().map(|node| {
// borrow!!!
&node.borrow().elem
})
}
> cargo build
error[E0515]: 不能返回引用临时值的值
--> src/fourth.rs:66:13
|
66 | &node.borrow().elem
| ^ ----------^^^^^
| | |
| | 这里创建的临时值
| |
| 返回一个引用当前函数所拥有的数据的值
这与我们的单链表完全相同。为什么事情会不同。为什么。
答案就是这一章的全部寓意:RefCell
让一切都悲伤。到目前为止,RefCell
一直是个讨厌的东西。现在他们将成为一场噩梦。
那么到底发生了什么呢?要理解这一点,我们需要回到borrow
的定义
fn borrow<'a>(&'a self) -> Ref<'a, T>
fn borrow_mut<'a>(&'a self) -> RefMut<'a, T>
在layout
节我们说:
RefCell
并不是静态地强制它们,而是在运行时强制它们。如果你违反了规则,RefCell
就会panic
,让程序崩溃。为什么它返回这些Ref
和RefMut
的东西?它们的行为和Rc
很像,只是借用而已。而且他们会一直借用RefCell
直到他们超出了范围。我们稍后会讲到
现在就是稍后
Ref
和RefMut
分别实现了Deref
和DerefMut
,所以对于大多数意图和目的来说,它们的行为与&T
和&mut T
完全相同。然而,由于这些特性的工作方式,返回的引用与Ref
的生命期有关,而不是实际的RefCell
。这就意味着,只要我们把引用留在身边,Ref
就必须一直存在。
事实上,这对于正确性来说是必要的。当一个Ref
被丢弃时,它会告诉RefCell
它不再被借用了。因此,如果我们确实设法保持我们的引用比 Ref
存在的时间更长,我们可以在引用还在运行的时候得到一个 RefMut
,并完全将Rust的类型系统破坏了一半。
那么我们现在的情况是什么呢?我们只想返回一个引用,但我们需要把Ref
这个东西留在身边。但只要我们从peek
中返回引用,函数就结束了,而Ref
就超出了作用域。
😖
据我所知,我们在这里完全是死水一潭。您不能像那样完全封装RefCells
的使用。但是…如果我们放弃完全隐藏实现细节呢?如果我们返回Ref
?
pub fn peek_front(&self) -> Option<Ref<T>> {
self.head.as_ref().map(|node| node.borrow())
}
> cargo build
error[E0412]: cannot find type `Ref` in this scope
--> src/fourth.rs:63:40
|
63 | pub fn peek_front(&self) -> Option<Ref<T>> {
| ^^^ not found in this scope
help: possible candidates are found in other modules, you can import them into scope
|
1 | use core::cell::Ref;
|
1 | use std::cell::Ref;
|
必须导入一些东西
use std::cell::{Ref, RefCell};
> cargo build
error[E0308]: mismatched types
--> src/fourth.rs:64:9
|
64 | / self.head.as_ref().map(|node| {
65 | | node.borrow()
66 | | })
| |__________^ expected type parameter, found struct `fourth::Node`
|
= note: expected type `std::option::Option<std::cell::Ref<'_, T>>`
found type `std::option::Option<std::cell::Ref<'_, fourth::Node<T>>>`
嗯…这是正确的。我们有一个Ref<Node<T>>
,但是我们想要一个Ref<T>
。我们可以放弃所有封装的希望,直接返回这个。我们还可以让事情变得更加复杂,将Ref<Node<T>>
包装为新的类型,只公开对&T
的访问。
这两种选择都有点蹩脚。
相反,我们要深入下去。让我们找点乐子。我们的乐趣来源就是这个野兽
map<U, F>(orig: Ref<'b, T>, f: F) -> Ref<'b, U>
where F: FnOnce(&T) -> &U,
U: ?Sized
为借来的数据的一个组件创建一个新的Ref
。
是的:就像你可以在一个Option
上进行map
映射一样,你可以也映射一个Ref
。
我肯定有人在某处真的很兴奋,因为单子或任何东西,但我不关心任何这些。我也不认为这是一个适当的单子,因为没有类似的情况,但我离题了。
这很酷,这对我来说才是最重要的。我需要这个:
pub fn peek_front(&self) -> Option<Ref<T>> {
self.head.as_ref().map(|node|{
Ref::map(node.borrow(), |node| &node.elem)
})
}
> cargo build
让我们通过从堆栈中添加测试来确保这是有效的。我们需要做些调整来处理Ref
并未实现比较这一事实。
#[test]
fn peek() {
let mut list = List::new();
assert!(list.peek_front().is_none());
list.push_front(1);
list.push_front(2);
list.push_front(3);
assert_eq!(&*list.peek_front().unwrap(), &3);
}
5.5. Symmetric Cases
好了,让我们把组合对称现实
list
+-------+ +-------+
| &head<-----+------| None |
+-------| | +-------+
| &tail<-----+
+-------+
list
+-------+ +---+--------+--+ +------------+ +--+-------+
| &head<----+ | prev | +--------> prev | | | None |
+-------| +--------+ | +--------+ | +-------+
| &tail<----+ | next <-------+ | next <----+
+-------+ | +--------+ | +--------+
| | elem | | | elem |
| +--------+ | +--------+
+-------------------+
我们只需要做一些基本的文本替换
tail <-> head
next <-> prev
front -> back
哦,我们还需要添加_mut
变体以进行peek
查询
pub fn push_back(&mut self, elem: T) {
let new_tail = Node::new(elem);
match self.tail.take() {
Some(old_tail) => {
old_tail.borrow_mut().next = Some(new_tail.clone());
new_tail.borrow_mut().prev = Some(old_tail);
self.tail = Some(new_tail);
}
None => {
self.head = Some(new_tail.clone());
self.tail = Some(new_tail);
}
}
}
pub fn pop_back(&mut self) -> Option<T> {
self.tail.take().map(|old_tail| {
match old_tail.borrow_mut().prev.take() {
Some(new_tail) => {
new_tail.borrow_mut().next.take();
self.tail = Some(new_tail);
}
None => {
self.head.take();
}
}
Rc::try_unwrap(old_tail).ok().unwrap().into_inner().elem
})
}
pub fn peek_back(&self) -> Option<Ref<T>> {
self.tail.as_ref().map(|node| {
Ref::map(node.borrow(), |node| &node.elem)
})
}
pub fn peek_back_mut(&mut self) -> Option<RefMut<T>> {
self.tail.as_ref().map(|node|{
RefMut::map(node.borrow_mut(), |node| &mut node.elem)
})
}
pub fn peek_front_mut(&mut self) -> Option<RefMut<T>> {
self.head.as_ref().map(|node|{
RefMut::map(node.borrow_mut(), |node| &mut node.elem)
})
}
大量充实我们的测试
#[cfg(test)]
mod test {
use super::List;
#[test]
fn basics() {
let mut list = List::new();
assert_eq!(list.pop_front(), None);
list.push_front(1);
list.push_front(2);
list.push_front(3);
assert_eq!(list.pop_front(), Some(3));
assert_eq!(list.pop_front(), Some(2));
list.push_front(4);
list.push_front(5);
assert_eq!(list.pop_front(), Some(5));
assert_eq!(list.pop_front(), Some(4));
assert_eq!(list.pop_front(), Some(1));
assert_eq!(list.pop_front(), None);
// ----- back ------
assert_eq!(list.pop_back(), None);
list.push_back(1);
list.push_back(2);
list.push_back(3);
assert_eq!(list.pop_back(), Some(3));
assert_eq!(list.pop_back(), Some(2));
list.push_back(4);
list.push_back(5);
assert_eq!(list.pop_back(), Some(5));
assert_eq!(list.pop_back(), Some(4));
assert_eq!(list.pop_back(), Some(1));
assert_eq!(list.pop_back(), None);
}
#[test]
fn peek() {
let mut list = List::new();
assert!(list.peek_front().is_none());
assert!(list.peek_back().is_none());
assert!(list.peek_front_mut().is_none());
assert!(list.peek_back_mut().is_none());
list.push_front(1);
list.push_front(2);
list.push_front(3);
assert_eq!(&*list.peek_front().unwrap(), &3);
assert_eq!(&mut *list.peek_front_mut().unwrap(), &mut 3);
assert_eq!(&*list.peek_back().unwrap(), &1);
assert_eq!(&mut *list.peek_back_mut().unwrap(), &mut 1);
}
}
还有没有一些情况下我们没有测试? 大概有。
组合空间确实在这里爆炸了。
我们的代码至少没有明显的错误。
> cargo test
好了。复制粘贴是最好的编程方式。
5.6. Iteration
像往常一样,IntoIter
将是最简单的。只需要包装栈并调用pop
pub struct IntoIter<T>(List<T>);
impl<T> List<T> {
pub fn into_iter(self) -> IntoIter<T> {
IntoIter(self)
}
}
impl<T> Iterator for IntoIter<T> {
type Item = T;
fn next(&mut self) -> Option<T> {
self.0.pop_front()
}
}
但我们有了一个有趣的新发展。在此之前,我们的列表只有一个“自然”迭代顺序,而Deque
本质上是双向的。从前到后有什么特别之处?如果有人想要在另一个方向迭代该怎么办?
对于这个问题,Rust
实际上有一个答案:DoubleEndedIterator
。DoubleEndedIterator
继承自Iterator
(意味着所有DoubleEndedIterator
都是迭代器),并且需要一个新方法:next_back
。它与next
具有完全相同的签名,但它应该从另一端产生元素。DoubleEndedIterator
的语义对我们来说非常方便:迭代器变成了deque
容器。您可以从前面和后面使用元素,直到两端收敛,此时迭代器为空。
就像Iterator
和next
一样,事实证明next_back
并不是DoubleEndedIterator
的用户真正关心的东西。相反,这个接口最好的地方在于它公开了rev
方法,它将迭代器包装起来,生成一个新迭代器,以相反的顺序生成元素。它的语义相当直接:在反向迭代器上调用next
就是调用next_back
。
因为我们已经是deque
了,提供这个API很容易:
impl<T> DoubleEndedIterator for IntoIter<T> {
fn next_back(&mut self) -> Option<T> {
self.0.pop_back()
}
}
我们来测试一下:
#[test]
fn into_iter() {
let mut list = List::new();
list.push_front(1); list.push_front(2); list.push_front(3);
let mut iter = list.into_iter();
assert_eq!(iter.next(), Some(3));
assert_eq!(iter.next_back(), Some(1));
assert_eq!(iter.next(), Some(2));
assert_eq!(iter.next_back(), None);
assert_eq!(iter.next(), None);
}
> cargo test
好极了!
Iter
Iter
就不那么宽容了。我们又得应付那些可怕的Ref
了!由于引用Refs
,我们不能像以前那样存储&Node
。相反,让我们尝试存储Ref<Node>s
:
pub struct Iter<'a T>(Option<Ref<'a, Node<T>>>);
impl<T> List<T> {
pub fn iter(&self) -> Iter<T> {
Iter(self.head.as_deref().map(|node| node.borrow()))
}
}
到目前为止,一切都好。实现next
会有点麻烦,但我认为它与旧堆栈IterMut
的基本逻辑相同,但有额外的RefCell
疯狂:
impl<'a, T> Iterator for Iter<'a, T> {
type Item = Ref<'a, T>;
fn next(&mut self) -> Option<Self::Item> {
self.0.take().map(|node_ref: Ref<Node<T>> |{
self.0 = node_ref.next: Option<Rc<RefCell<Node<T>>>>
.as_ref(): Option<&Rc<RefCell<Node<T>>>>
.map(|head: &Rc<RefCell<Node<T>>>| head: &Rc<RefCell<Node<T>>>
.borrow(): Ref<Node<T>>);
Ref::map(node_ref, |node| &node.elem)
})
}
}
cargo build
error[E0521]: 借用的数据逃逸到闭包之外
--> src/fourth.rs:155:13
|
153 | fn next(&mut self) -> Option<Self::Item> {
| --------- `self` 是在这里声明的,在闭包体之外
154 | self.0.take().map(|node_ref| {
155 | self.0 = node_ref.next.as_ref().map(|head| head.borrow());
| ^^^^^^ -------- 借用仅在闭包体中有效
| |
| 对' node ref '的引用在这里逃逸出了闭包体
error[E0505]: 无法移出' node_ref ',因为它是借来的
--> src/fourth.rs:156:22
|
153 | fn next(&mut self) -> Option<Self::Item> {
| --------- 生命期参数 “'1” 出现在 “self” 的类型中
154 | self.0.take().map(|node_ref| {
155 | self.0 = node_ref.next.as_ref().map(|head| head.borrow());
| ------ -------- 这里出现`node_ref`的借用
| |
| 赋值要求 "node_ref "为"’1"借用
156 | Ref::map(node_ref, |node| &node.elem)
| ^^^^^^^^ 移出`node_ref`发生在这里
该死
node_ref
的寿命不够长。不像一般的引用,Rust不允许我们像那样把引用Refs
分开。我们从head.borrow()
中得到的Ref
只允许存在与node_ref
相同的时间,但是我们最终在Ref::map
调用中丢弃了它。
巧合的是,在我写这个的时候,我们想要的函数实际上两天前就稳定下来了。这意味着它还需要几个月的时间才能发布稳定版。因此,让我们继续使用最新的夜间构建:
pub fn map_split<U, V, F>(orig: Ref<'b, T>, f: F) -> (Ref<'b, U>, Ref<'b, V>) where
F: FnOnce(&T) -> (&U, &V),
U: ?Sized,
V: ?Sized,
Woof
,让我们试一试……
fn next(&mut self) -> Option<Self::Item> {
self.0.take().map(|node_ref: Ref<Node<T>>| {
let (next: Ref<Option<Rc<Ref<Node<T>>>>>, elem: Ref<T>)
= Ref::map_split(node_ref, |node: &Node<T>| {
(&node.next, &node.elem)
});
self.0 = next.as_ref(): Option<&Rc<Ref<Node<T>>>>
.map(|head: &Rc<Ref<Node<T>>>| head.borrow());
elem
})
}
cargo build
Compiling lists v0.1.0 (/Users/ABeingessner/dev/temp/lists)
error[E0521]: borrowed data escapes outside of closure
--> src/fourth.rs:159:13
|
153 | fn next(&mut self) -> Option<Self::Item> {
| --------- `self` is declared here, outside of the closure body
...
159 | self.0 = next.as_ref().map(|head| head.borrow());
| ^^^^^^ ---- borrow is only valid in the closure body
| |
| reference to `next` escapes the closure body here
恩。我们需要再次使用Ref::Map
才能使生命期正确。 但是 Ref::Map
返回一个Ref
,我们需要一个Option<Ref>
,但是我们需要遍历Ref
才能映射到我们的Option
上…
长时间凝视远方
??????
fn next(&mut self) -> Option<Self::Item> {
self.0.take().map(|node_ref: Ref<Node<T>>| {
let (next, elem) = Ref::map_split(node_ref, |node| {
(&node.next, &node.elem)
});
self.0 = if next.is_some() {
Some(Ref::map(next: Ref<Option<Rc<RefCell<Node<T>>>>>,
|next: &Option<Rc<RefCell<Node<T>>>>|
&**next
.as_ref(): Option<&Rc<RefCell<Node<T>>>>
.unwrap(): &Rc<RefCell<Node<T>>>
// &RefCell<Node<T>>
))} else {
None
};
elem
})
}
error[E0308]: mismatched types
--> src/fourth.rs:162:22
|
162 | Some(Ref::map(next, |next| &**next.as_ref().unwrap()))
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `fourth::Node`, found struct `std::cell::RefCell`
|
= note: expected type `std::cell::Ref<'_, fourth::Node<_>>`
found type `std::cell::Ref<'_, std::cell::RefCell<fourth::Node<_>>>`
哦。对的。有多个重叠的RefCells
。我们在列表中走得越深,每个RefCell
下的嵌套就越深。例如,我们需要维护一个Refs
栈来代表我们所持有的所有未偿还的借用,因为如果我们停止查看某个元素,则需要减少它之前的每个RefCell
上的借位计数……
我认为我们在这里无能为力。 这是一个死胡同。 让我们尝试摆脱RefCell
。
那我们的Rc
s呢? 谁说我们需要存储引用? 为什么我们不能仅仅克隆整个Rc
来在list
中间找到一个很好的拥有者句柄?
pub struct Iter<T>(Option<Rc<Node<T>>>);
impl<T> List<T> {
pub fn iter(&self) -> Iter<T> {
Iter(self.head.as_ref().map(|head| head.clone()))
}
}
impl<T> Iterator for Iter<T> {
type Item =
嗯…等等,我们现在返回什么? &T
? Ref<T>
?
不,这些都没用……我们的Iter
再也没有生命周期了!&T
和Ref<T>
都要求我们在进入next
之前预先声明一些生命周期。但是我们从Rc
中得到的任何东西都会借用Iterator……头……痛……aaaaaahhhhhh
也许我们可以…map
……Rc
……得到一个Rc<T>
?这是答案吗?Rc
的文档中似乎没有这样的内容。实际上有人做了个crate
让你可以这么做。
但是,等等,即使我们这样做,也遇到了一个更大的问题:迭代器失效的可怕幽灵。 以前,我们完全不受迭代器失效的影响,因为Iter
借用了列表list
,使其完全不可变。 但是,如果我们的Iter
产生的是Rcs
,那么他们根本不会借用该列表! 这意味着人们可以在持有列表中的指针的同时在列表上调用push
和pop
!
哦,上帝,那会有什么后果?
好吧,pushing
其实是可以的。 我们的视野已经进入了该列表的某些子范围,并且该列表将增长到超出我们的视线。 没什么大不了的。
然而pop
是另一回事。 如果他们在我们的范围外弹出元素,那应该还是可以的。 我们看不到那些节点,所以什么也不会发生。 但是,但是如果他们试图弹出我们指向的节点……一切都会崩溃! 特别是当他们去unwrap
解包try_unwrap
的结果时,它实际上将失败,并且整个程序将崩溃。
这其实是非常酷的。我们可以将大量内部自有指针添加到列表中,同时对其进行修改,直到他们试图删除我们指向的节点为止。即使我们没有得到悬空指针或其他东西,程序也肯定会崩溃。
但是在映射Rcs
的基础上还要处理迭代器无效的问题,这似乎……很糟糕。 Rc<RefCell>
真的让我们失望了。 有趣的是,我们经历了持久栈情况的反转。 在持久性堆栈努力获取数据所有权但每天都可以获取引用的地方,我们的列表在获得所有权方面没有问题,但却很难借出我们的引用。
虽然公平地说,但我们的大多数努力都围绕着希望隐藏实现细节并拥有一个优雅的API来进行。 如果我们只是想到处传递Nodes,我们可以做到一切都很好。
哎呀,我们可以创建多个并发的IterMuts
,这些IterMuts
在运行时进行了检查,以确保不可变地访问同一元素!
实际上,这种设计更适合于内部数据结构,因为这些数据结构永远不会被API的用户看到。内部可变性对于编写安全的应用程序非常有用。没有比这安全的库了。
总之,我放弃了Iter
和IterMut
。我们可以做,但是……唉…….
5.7. Final Code
好了,这就是在Rust
中实现一个100%
安全的双链表。它的实现是个噩梦,泄露了实现细节,而且不支持几个基本操作。
但是,它是存在的。
哦,我猜它也被Rc
和RefCell
之间大量的“不必要的”运行时检查所困扰。我把不必要的放在引号里,因为它们实际上是必要的,以确保整个是安全的。我们遇到了一些地方,这些检查实际上是必要的。双向链表有一个可怕的混乱的别名和所有权故事。
尽管如此,这也是我们可以做的事情。尤其是当我们不在乎将内部数据结构暴露给用户的时候。
从现在开始,我们将专注于硬币的另一面:通过让我们的实现变得不安全来夺回所有的控制权
#![allow(unused_variables)]
fn main() {
use std::rc::Rc;
use std::cell::{Ref, RefMut, RefCell};
pub struct List<T> {
head: Link<T>,
tail: Link<T>,
}
type Link<T> = Option<Rc<RefCell<Node<T>>>>;
struct Node<T> {
elem: T,
next: Link<T>,
prev: Link<T>,
}
impl<T> Node<T> {
fn new(elem: T) -> Rc<RefCell<Self>> {
Rc::new(RefCell::new(Node {
elem: elem,
prev: None,
next: None,
}))
}
}
impl<T> List<T> {
pub fn new() -> Self {
List { head: None, tail: None }
}
pub fn push_front(&mut self, elem: T) {
let new_head = Node::new(elem);
match self.head.take() {
Some(old_head) => {
old_head.borrow_mut().prev = Some(new_head.clone());
new_head.borrow_mut().next = Some(old_head);
self.head = Some(new_head);
}
None => {
self.tail = Some(new_head.clone());
self.head = Some(new_head);
}
}
}
pub fn push_back(&mut self, elem: T) {
let new_tail = Node::new(elem);
match self.tail.take() {
Some(old_tail) => {
old_tail.borrow_mut().next = Some(new_tail.clone());
new_tail.borrow_mut().prev = Some(old_tail);
self.tail = Some(new_tail);
}
None => {
self.head = Some(new_tail.clone());
self.tail = Some(new_tail);
}
}
}
pub fn pop_back(&mut self) -> Option<T> {
self.tail.take().map(|old_tail| {
match old_tail.borrow_mut().prev.take() {
Some(new_tail) => {
new_tail.borrow_mut().next.take();
self.tail = Some(new_tail);
}
None => {
self.head.take();
}
}
Rc::try_unwrap(old_tail).ok().unwrap().into_inner().elem
})
}
pub fn pop_front(&mut self) -> Option<T> {
self.head.take().map(|old_head| {
match old_head.borrow_mut().next.take() {
Some(new_head) => {
new_head.borrow_mut().prev.take();
self.head = Some(new_head);
}
None => {
self.tail.take();
}
}
Rc::try_unwrap(old_head).ok().unwrap().into_inner().elem
})
}
pub fn peek_front(&self) -> Option<Ref<T>> {
self.head.as_ref().map(|node| {
Ref::map(node.borrow(), |node| &node.elem)
})
}
pub fn peek_back(&self) -> Option<Ref<T>> {
self.tail.as_ref().map(|node| {
Ref::map(node.borrow(), |node| &node.elem)
})
}
pub fn peek_back_mut(&mut self) -> Option<RefMut<T>> {
self.tail.as_ref().map(|node| {
RefMut::map(node.borrow_mut(), |node| &mut node.elem)
})
}
pub fn peek_front_mut(&mut self) -> Option<RefMut<T>> {
self.head.as_ref().map(|node| {
RefMut::map(node.borrow_mut(), |node| &mut node.elem)
})
}
pub fn into_iter(self) -> IntoIter<T> {
IntoIter(self)
}
}
impl<T> Drop for List<T> {
fn drop(&mut self) {
while self.pop_front().is_some() {}
}
}
pub struct IntoIter<T>(List<T>);
impl<T> Iterator for IntoIter<T> {
type Item = T;
fn next(&mut self) -> Option<T> {
self.0.pop_front()
}
}
impl<T> DoubleEndedIterator for IntoIter<T> {
fn next_back(&mut self) -> Option<T> {
self.0.pop_back()
}
}
#[cfg(test)]
mod test {
use super::List;
#[test]
fn basics() {
let mut list = List::new();
// Check empty list behaves right
assert_eq!(list.pop_front(), None);
// Populate list
list.push_front(1);
list.push_front(2);
list.push_front(3);
// Check normal removal
assert_eq!(list.pop_front(), Some(3));
assert_eq!(list.pop_front(), Some(2));
// Push some more just to make sure nothing's corrupted
list.push_front(4);
list.push_front(5);
// Check normal removal
assert_eq!(list.pop_front(), Some(5));
assert_eq!(list.pop_front(), Some(4));
// Check exhaustion
assert_eq!(list.pop_front(), Some(1));
assert_eq!(list.pop_front(), None);
// ---- back -----
// Check empty list behaves right
assert_eq!(list.pop_back(), None);
// Populate list
list.push_back(1);
list.push_back(2);
list.push_back(3);
// Check normal removal
assert_eq!(list.pop_back(), Some(3));
assert_eq!(list.pop_back(), Some(2));
// Push some more just to make sure nothing's corrupted
list.push_back(4);
list.push_back(5);
// Check normal removal
assert_eq!(list.pop_back(), Some(5));
assert_eq!(list.pop_back(), Some(4));
// Check exhaustion
assert_eq!(list.pop_back(), Some(1));
assert_eq!(list.pop_back(), None);
}
#[test]
fn peek() {
let mut list = List::new();
assert!(list.peek_front().is_none());
assert!(list.peek_back().is_none());
assert!(list.peek_front_mut().is_none());
assert!(list.peek_back_mut().is_none());
list.push_front(1); list.push_front(2); list.push_front(3);
assert_eq!(&*list.peek_front().unwrap(), &3);
assert_eq!(&mut *list.peek_front_mut().unwrap(), &mut 3);
assert_eq!(&*list.peek_back().unwrap(), &1);
assert_eq!(&mut *list.peek_back_mut().unwrap(), &mut 1);
}
#[test]
fn into_iter() {
let mut list = List::new();
list.push_front(1); list.push_front(2); list.push_front(3);
let mut iter = list.into_iter();
assert_eq!(iter.next(), Some(3));
assert_eq!(iter.next_back(), Some(1));
assert_eq!(iter.next(), Some(2));
assert_eq!(iter.next_back(), None);
assert_eq!(iter.next(), None);
}
}
}
6. 不安全的单链队列
好吧,引用计数的内部可变性有点失控了。Rust当然不会真的希望你做这种事吧?嗯,是也不是。Rc
和Refcell
可以很好地处理简单的情况,但它们可能会变得很笨重。特别是当你想隐藏它的发生时。 一定有更好的方法!
在这一章中,我们将回到单链表,并实现一个单链路队列,以了解原始指针和Unsafe Rust
。
让我们添加一个名为 fifth.rs 的新文件
// in lib.rs
pub mod first;
pub mod second;
pub mod third;
pub mod fourth;
pub mod fifth;
我们的代码主要是由second
派生的。因为在链表的世界里,队列基本上是堆栈的扩充。不过,我们还是要从头开始,因为我们还需要解决一些关于布局之类的基本问题。
那么,单链路的队列是什么样的呢?好吧,当我们有一个单链栈时,我们推到列表的一端,然后从同一端弹出。栈和队列的唯一区别是,队列会从另一端弹出。所以从我们的栈实现来看,我们有:
input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)
stack push X:
[Some(ptr)] -> (X, Some(ptr)) -> (A, Some(ptr)) -> (B, None)
stack pop:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)
为了创建一个队列,我们只需要决定将哪个操作移动到列表的末尾:push
,还是pop
?由于我们的列表是单链的,我们实际上可以用相同的努力将任意一个操作移动到最后。
要将push
移动到末尾,只需一直走到None
,并使用新元素将其设置为Some
。
input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)
flipped push X:
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)
要将pop
移至末尾,我们只需要一直走到None
之前的节点,然后将其取走:
input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)
flipped pop:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)
我们可以在今天做完这一切,然后收手,但那会很糟糕! 这两种操作都会走过整个列表。有些人会认为,这样的队列实现确实是一个队列,因为它公开了正确的接口。然而我认为,性能保证也是接口的一部分。我并不关心精确的渐变边界,但在乎“快”与“慢”的区别。队列保证了push
和pop
是快速的,而遍历整个列表肯定不是快速的。
一个关键的观察是,我们浪费了大量的工作,重复做同样的事情。我们能记住这些工作吗? 为什么,是的!我们可以存储一个指向列表末尾的指针,然后直接跳到那里就可以了!
事实证明,只有push
和pop
的一种反转才能使用此功能。 要反转pop
,我们必须将“tail
”指针向后移动,但是由于我们的列表是单链链接,因此我们无法有效地做到这一点。 如果我们反转push
,我们只需要向前移动“head
”指针,这很容易。
list
+------+ +------+
| head <---+-+ None |
+------+ | +------+
| tail <---+
+------+
list
+------+ +--+------+ +--+------+
| head <---+ | elem | | | elem |
+------+ +------+ | +------+
| tail <---+ | next <---+ | next |
+------+ | +------+ | +------+
+-------------+
让我们试一试:
use std::mem;
pub struct List<T> {
head: Link<T>,
tail: Link<T>, // NEW!
}
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, tail: None }
}
pub fn push(&mut self, elem: T) {
let new_tail = Box::new(Node {
elem,
// 当您push到tail时,next永远是None
next: None,
});
// 换 old_tail 指向 new_tail
let old_tail = mem::replace(&mut self.tail, Some(new_tail));
match old_tail {
Some(mut old_tail) => {
// 如果 old_tail 存在,更新old_tail指向new_tail
old_tail.next = Some(new_tail);
}
None => {
// 否则,更新head指向new_tail
self.head = Some(new_tail);
}
}
}
}
我现在对 impl 的细节讲得比较快,因为我们对这种事情应该很熟悉。并不是说你一定要期望第一次就能产生这样的代码,我只是跳过了一些我们以前要处理的试错。其实我在写这段代码的时候犯了一大堆错误,我就不展示了。你只能看到我漏掉一个mut
或;
这么多次才会停止指导。别担心,我们会看到很多其他的错误信息!
> cargo build
error[E0382]: use of moved value: `new_tail`
--> src/fifth.rs:38:38
|
26 | let new_tail = Box::new(Node {
| -------- move occurs because `new_tail` has type `std::boxed::Box<fifth::Node<T>>`, which does not implement the `Copy` trait
...
33 | let old_tail = mem::replace(&mut self.tail, Some(new_tail));
| -------- value moved here
...
38 | old_tail.next = Some(new_tail);
| ^^^^^^^^ value used here after move
该死!
使用了转移后的值:new_tail
Box
并没有实现Copy
,所以我们不能随便把它分配到两个位置。更重要的是,Box
拥有它所指向的东西,当它被丢弃时,会尝试释放它。如果我们的push
实现编译后,就会把列表的尾部双倍释放! 实际上,就像我们写的那样,我们的代码会在每次push
时释放 old_tail
。呀!🙀
我们知道如何创建一个非所有者指针。这只是一个参考!
pub struct List<T> {
head: Link<T>,
tail: Option<&mut Node<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, tail: None }
}
pub fn push(&mut self, elem: T) {
let new_tail = Box::new(Node {
elem: elem,
// When you push onto the tail, your next is always None
next: None,
});
// Put the box in the right place, and then grab a reference to its Node
// 将box放在正确的位置,然后获取对其Node的引用
let new_tail = match self.tail.take() {
Some(old_tail) => {
// If the old tail existed, update it to point to the new tail
old_tail.next = Some(new_tail);
old_tail.next.as_deref_mut()
}
None => {
// Otherwise, update the head to point to it
self.head = Some(new_tail);
self.head.as_deref_mut()
}
};
self.tail = new_tail;
}
}
这没什么难的。和前面的代码基本思路一样,只是我们使用了一些隐式返回的好处,从我们塞入实际Box的地方提取尾部引用。
> cargo build
error[E0106]: missing lifetime specifier
--> src/fifth.rs:3:18
|
3 | tail: Option<&mut Node<T>>, // NEW!
| ^ expected lifetime parameter
对了,我们需要在类型生命周期中提供引用。嗯…这个引用的生命周期是多少?这看起来像IterMut
,对吧?让我们尝试一下我们对IterMut
所做的,只是添加一个泛型的'a'
:
pub struct List<'a, T> {
head: Link<T>,
tail: Option<&'a mut Node<T>>, // NEW!
}
impl<'a, T> List<'a, T> {
...
}
cargo build
error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting
error[E0495]: 由于需求冲突,无法推断出自动引用的适当生命周期
requirements
--> src/fifth.rs:35:27
|
35 | self.head.as_deref_mut()
| ^^^^^^^^^^^^
|
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 18:5...
注意:首先,生命周期不能超过18:5在方法体上定义的匿名生命周期#1…
--> src/fifth.rs:18:5
|
18 | / pub fn push(&mut self, elem: T) {
19 | | let new_tail = Box::new(Node {
20 | | elem: elem,
21 | | // When you push onto the tail, your next is always None
... |
39 | | self.tail = new_tail;
40 | | }
| |_____^
note: ...so that reference does not outlive borrowed content
注意:……所以引用不会比借来的内容更长久
--> src/fifth.rs:35:17
|
35 | self.head.as_deref_mut()
| ^^^^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the impl at 13:6...
注意:但是,生命周期必须在13:6 impl上定义的生命周期 'a 内有效。
--> src/fifth.rs:13:6
|
13 | impl<'a, T> List<'a, T> {
| ^^
= note: ...so that the expression is assignable:
= 注意:……这样表达式就可以赋值了
expected std::option::Option<&'a mut fifth::Node<T>>
found std::option::Option<&mut fifth::Node<T>>
哇,那是一条非常详细的错误消息。 这有点令人担忧,因为这表明我们正在做的事情确实搞砸了。 这是一个有趣的部分:
生命周期必须在impl上定义的生命周期a内有效
我们是从self
借来的,但是编译器希望我们的生命期和'a
一样长,如果我们告诉它self
可以持续那么长时间呢?
pub fn push(&'a mut self, elem: T) {
...
}
cargo build
warning: field is never used: `elem`
--> src/fifth.rs:9:5
|
9 | elem: T,
| ^^^^^^^
|
= note: #[warn(dead_code)] on by default
哦,嘿,成功了!太棒了!
我们也来完成 pop
吧
pub fn pop(&'a mut self) -> Option<T> {
// 获取list的当前head
self.head.take().map(|head| {
let head = *head;
self.head = head.next;
// 如果我们的“head”没有,请确保将“tail”设置为“None”
if self.head.is_none() {
self.tail = None;
}
head.elem
})
}
并为此编写一个快速测试:
mod test {
use super::List;
#[test]
fn basics() {
let mut list = List::new();
assert_eq!(list.pop(), None);
list.push(1); list.push(2); list.push(3);
assert_eq!(list.pop(), Some(1));
assert_eq!(list.pop(), Some(2));
list.push(4); list.push(5);
assert_eq!(list.pop(), Some(3));
assert_eq!(list.pop(), Some(4));
// check exhaustion
assert_eq!(list.pop(), Some(5));
assert_eq!(list.pop(), None);
}
}
cargo test
error[E0499]: cannot borrow `list` as mutable more than once at a time
--> src/fifth.rs:68:9
|
65 | assert_eq!(list.pop(), None);
| ---- first mutable borrow occurs here
...
68 | list.push(1);
| ^^^^
| |
| second mutable borrow occurs here
| first borrow later used here
error[E0499]: cannot borrow `list` as mutable more than once at a time
--> src/fifth.rs:69:9
|
65 | assert_eq!(list.pop(), None);
| ---- first mutable borrow occurs here
...
69 | list.push(2);
| ^^^^
| |
| second mutable borrow occurs here
| first borrow later used here
error[E0499]: cannot borrow `list` as mutable more than once at a time
--> src/fifth.rs:70:9
|
65 | assert_eq!(list.pop(), None);
| ---- first mutable borrow occurs here
...
70 | list.push(3);
| ^^^^
| |
| second mutable borrow occurs here
| first borrow later used here
....
** WAY MORE LINES OF ERRORS **
....
error: aborting due to 11 previous errors
🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀
哦~ 我的天哪。
编译者对我们的吐槽并没有错。我们只是犯了一个Rust
的大罪:我们在自己的内部存储了一个对自己的引用。不知何故,我们设法说服Rust
,这在我们的push
和pop
实现中完全是有意义的(我对此感到非常震惊)。我相信原因是Rust
还不能从单纯的push
和pop
中判断出引用是属于我们自己的——或者更确切地说,Rust
根本就没有这个概念。引用到自己身上失效只是一种紧急的行为。
当我们尝试使用我们的列表时,一切很快就崩溃了。当我们调用push
或pop
时,我们会立即将对自己的引用存储在我们自己中并陷入困境。我们实际上是在借用自己。
我们的pop
实现暗示了为什么这可能真的很危险
// ...
if self.head.is_none() {
self.tail = None;
}
如果我们忘了这样做呢?那我们的tail
就会指向某个被从列表中删除的节点。这样的节点会被立即释放,我们会有一个悬空的指针,而Rust
本来应该保护我们的。
而事实上,Rust
正在保护我们免受这种危险。只是以一种非常… 迂回的方式。
所以,我们能做些什么? 回到Rc <RefCell>>
地狱?
行行好,不行
不,相反,我们将偏离常规,使用原始指针。我们的布局是这样的:
pub struct List<T> {
head: Link<T>,
tail: *mut Node<T>, // 危险 Danger
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
就是这样。真的别跟我说这些没用的引用计数、动态借用检查的废话
硬核、没有检查的指针才是王道~
让我们成为C语言的人吧,让我们回到C语言一整天。
我准备好了。
你好,unsafe
6.2. Unsafe
这是一个严肃,重大,复杂和危险的话题。 这是如此严重,以至于我写了另一本书。
简而言之,只要你允许调用其他语言,每一种语言实际上都是不安全的,因为你可以让C做任意错误的事情。是的:Java, Python, Ruby, Haskell…
在外部函数接口(FFI)面前,每个人都非常不安全。
Rust
通过将自己分成两种语言来接受这个事实。安全Rust
和不安全Rust
。到目前为止,我们只使用了安全Rust
。它是完全100%
安全的……除了它可以FFI
成不安全的Rust
。
不安全Rust
是安全Rust
的超级集。它的语义和规则与安全Rust
完全相同,只是允许你做一些额外的事情,这些事情非常不安全,可能会导致可怕的未定义行为,困扰着C。
这是一个非常大的话题有很多有趣的特例。我真的不想太深入(好吧,我是想的。我读过那本书)。这没关系,因为使用链表,我们实际上可以忽略几乎所有这些。
我们将使用的主要不安全工具是原始指针。原始指针基本上是C的指针。它们没有固有的别名规则。他们没有生命期。它们可以是null
。它们可以悬挂着。它们可以指向未初始化的内存。它们可以转换为整数,也可以从整数转换为指针。它们可以被强制转换指向另一种类型。可变性吗?转换它。几乎所有的东西都可以,这意味着几乎所有的东西都可以出错。
这是一些不好的东西,说实话,你永远不用去碰这些东西,你会活得更开心。不幸的是,我们想写链表,而链表是可怕的。这意味着我们将不得不使用不安全的指针。
原始指针有两种:*const T
和*mut T
。它们的意思是来自C的const T *
和T *
,但我们实际上并不关心C认为它们的含义是什么。 您只能将* const T
解引用到&T
,但是就像变量的可变性一样,这只是防止不正确使用的纱布。 最多只是意味着您必须先将* const
强制转换为* mut
。但是如果你没有修改指针的引用的权限,你就会有麻烦了。
无论如何,当我们编写一些代码时,我们会对此有更好的感觉。 目前,
*mut T = &unchecked mut T
6.3. Basics
好了,回到最基本的bascis
。我们如何构造我们的列表
之前,我们是这样写的:
impl<T> List<T> {
pub fn new() -> Self {
List { head: None, tail: None }
}
}
但我们不再对尾部使用Option了
> cargo build
error[E0308]: mismatched types
--> src/fifth.rs:15:34
|
15 | List { head: None, tail: None }
| ^^^^ expected *-ptr, found enum `std::option::Option`
|
= note: expected type `*mut fifth::Node<T>`
found type `std::option::Option<_>`
我们可以使用Option
,但是与Box
不同,* mut
是可为空的。 这意味着它不能从空指针优化中受益。 相反,我们将使用null
来表示None
。
那么我们如何获得一个空指针呢? 有几种方法,但是我更喜欢使用std::ptr::nul_mut()
。 如果需要,您也可以使用 0 as *mut _
,但这似乎太混乱了。
use std::ptr;
// 定义 ...
impl<T> List<T> {
pub fn new() -> Self {
List { head: None, tail: ptr::null_mut() }
}
}
> cargo build
** 一堆字段未使用的警告 **
嘘~ ,编译器,我们很快就会使用它们。
好了,我们继续写push
。这一次,我们不是在插入后抓取一个Option<&mut Node<T>>
,而是马上抓取一个*mut Node<T>
到Box
的内部。我们知道我们可以这样做,因为Box
的内容有一个稳定的地址,即使我们移动Box
。当然,这样做是不安全的,因为如果我们直接丢掉这个Box
,就会有一个指向已释放内存的指针。
我们如何从普通指针制作原始指针? 威逼! 如果将变量声明为原始指针,则普通引用将强制进入该变量:
let raw_tail: *mut _ = &mut *new_tail;
我们需要的信息都有了。我们可以将我们的代码近似地翻译成以前的参考版本
pub fn push(&mut self, elem: T) {
let mut new_tail = Box::new(Node {
elem,
next: None,
});
let raw_tail: *mut _ = &mut *new_tail;
// .is_null 检查null,等同于检查None
if !self.tail.is_null() {
self.tail.next = Some(new_tail);
} else {
self.head = Some(new_tail);
}
self.tail = raw_tail;
}
> cargo build
error[E0609]: no field `next` on type `*mut fifth::Node<T>`
--> src/fifth.rs:31:23
|
31 | self.tail.next = Some(new_tail);
| ----------^^^^
| |
| help: `self.tail` is a raw pointer; try dereferencing it: `(*self.tail).next`
嗯?我们有一个指向Node
的指针,为什么我们不能得到next
字段?
当你用原始指针的时候,Rust
有点混蛋。为了访问原始指针的内容,它坚持要手动对其进行解引用,因为这是一个非常不安全的操作。我们来做一下:
*self.tail.next = Some(new_tail);
> cargo build
error[E0609]: no field `next` on type `*mut fifth::Node<T>`
--> src/fifth.rs:31:23
|
31 | *self.tail.next = Some(new_tail);
| -----------^^^^
| |
| help: `self.tail` is a raw pointer; try dereferencing it: `(*self.tail).next`
呃~~ 运算优先级~~
(*self.tail).next = Some(new_tail);
> cargo build
error[E0133]: dereference of raw pointer is unsafe and requires unsafe function or block
--> src/fifth.rs:31:13
|
31 | (*self.tail).next = Some(new_tail);
| ^^^^^^^^^^^^^^^^^ dereference of raw pointer
|
= note: raw pointers may be NULL, dangling or unaligned; they can violate aliasing rules and cause data races: all of these are undefined behavior
就不应该这么难!!!
还记得我说不安全的Rust
就像一个FFI语言的安全Rust
吗?编译器想让我们显式地界定我们在哪放置这个FFI
。我们有两个选择。首先,我们可以将整个函数标记为不安全的,在这种情况下,它成为不安全的Rust
函数,只能在不安全的上下文中调用。这并不好,因为我们希望我们的列表是安全使用的。其次,我们可以在函数内部编写一个不安全的块,来划定FFI
边界。这声明了整个函数是安全的。我们来做这个:
pub fn push(&mut self, elem: T) {
let mut new_tail = Box::new(Node {
elem,
next: None,
});
let raw_tail: *mut _ = &mut *new_tail;
if !self.tail.is_null() {
unsafe{
(*self.tail).next = Some(new_tail);
}
} else {
self.head = Some(new_tail);
}
}
> cargo build
编译通过
耶!
有趣的是,到目前为止,这是我们唯一写不安全块的地方。但我们到处都是原始指针,这是怎么回事?
事实证明,在不安全的问题上,Rust是一个庞大的规则学究。我们很合理地想要最大化安全Rust程序集,因为这些程序我们可以更有信心。为了达到这个目的,Rust小心翼翼地为不安全划出了最小的表面积。请注意,我们使用原始指针的所有其他地方都是对它们进行赋值,或者只是观察它们是否为空。
如果你从来没有解引用过原始指针那是完全安全的事情。您只是读写一个整数!使用原始指针唯一可能遇到麻烦的情况是对它进行解引用。所以Rust
说只有这个操作是不安全的,其他一切都是完全安全的。
超级学究。但技术上正确的。
然而,这引发了一个有趣的问题:尽管我们应该用不安全块来界定不安全块的范围,但它实际上取决于在块之外建立的状态。甚至是在函数之外!这就是我所说的不安全污染。
一旦你在一个模块中使用了unsafe
,整个模块就会被unsafe
污染。为了确保不安全代码的不变性得到维护,必须正确地编写所有内容。
由于隐私的关系,这种污染是可以处理的。在我们的模块之外,所有的struct
字段都是完全私有的,所以其他人不能以任意的方式干扰我们的状态。只要我们公开的api
组合没有导致糟糕的事情发生,就外部观察者而言,我们所有的代码都是安全的!实际上,这和FFI的情况没有什么不同。只要暴露出一个安全的接口,没有人需要关心某个python
数学库是否会外壳到C语言。
不管怎样,我们来看看pop
,它和参考版本几乎一字不差
pub fn pop(&mut self) -> Option<T> {
self.head.take().map(|head| {
let head = *head;
self.head = head.next;
if self.head.is_none() {
self.tail = ptr::null_mut();
}
head.elem
})
}
再一次,我们看到了另一种情况,即安全是有状态的。 如果我们无法在该函数中使尾指针为零,那么我们将看不到任何问题。 但是,随后的push
调用将开始写入悬空的tail
!
让我们来测试一下
#[cfg(test)]
mod test {
use super::List;
#[test]
fn basics() {
let mut list = List::new();
assert_eq!(list.pop(), None);
list.push(1); list.push(2); list.push(3);
assert_eq!(list.pop(), Some(1));
assert_eq!(list.pop(), Some(2));
list.push(4);
list.push(5);
assert_eq!(list.pop(), Some(3));
assert_eq!(list.pop(), Some(4));
assert_eq!(list.pop(), Some(5));
assert_eq!(list.pop(), None);
list.push(6);
list.push(7);
assert_eq!(list.pop(), Some(6));
assert_eq!(list.pop(), Some(7));
assert_eq!(list.pop(), None);
}
}
这只是堆栈测试,但是把预期的pop
结果翻转过来了。我还在最后增加了一些额外的步骤,以确保pop
中的尾指针损坏情况不会发生。
> cargo test
God Star!
6.4. Extras
现在已经编写了push
和pop
,其他所有内容与堆栈情况完全相同。 只有更改列表长度的操作才需要真正担心尾指针。
因此,让我们从第二个列表中窃取所有内容(请确保反转预期的测试输出):
// ...
pub struct IntoIter<T>(List<T>);
pub struct Iter<'a, T> {
next: Option<&'a Node<T>>,
}
pub struct IterMut<'a, T> {
next: Option<&'a mut Node<T>>,
}
impl<T> List<T> {
// ...
pub fn peek(&self) -> Option<&T> {
self.head.as_ref().map(|node| &node.elem)
}
pub fn peek_mut(&mut self) -> Option<&mut T> {
self.head.as_ref().map(|node| &mut node.elem)
}
pub fn into_iter(self) -> IntoIter<T> {
IntoIter(self)
}
pub fn iter(&self) -> Iter<'_, T> {
Iter { next: self.head.as_deref() }
}
pub fn iter_mut(&mut self) -> IterMut<'_, T> {
IterMut { next: self.head.as_deref_mut() }
}
}
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();
}
}
}
impl<T> Iterator for IntoIter<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
self.0.pop()
}
}
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
self.next.map(|node| {
self.next = node.next.as_deref();
&node.elem
})
}
}
impl<'a, T> Iterator for IterMut<'a, T> {
type Item = &'a mut T;
fn next(&mut self) -> Option<Self::Item> {
self.next.take().map(|node| {
self.next = node.next.as_deref_mut();
&mut node.elem
})
}
}
#[cfg(test)]
mod test {
// ...
#[test]
fn into_iter() {
let mut list = List::new();
list.push(1); list.push(2); list.push(3);
let mut iter = list.into_iter();
assert_eq!(iter.next(), Some(1));
assert_eq!(iter.next(), Some(2));
assert_eq!(iter.next(), Some(3));
assert_eq!(iter.next(), None);
}
#[test]
fn iter() {
let mut list = List::new();
list.push(1); list.push(2); list.push(3);
let mut iter = list.iter();
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), None);
}
#[test]
fn iter_mut() {
let mut list = List::new();
list.push(1); list.push(2); list.push(3);
let mut iter = list.iter_mut();
assert_eq!(iter.next(), Some(&mut 1));
assert_eq!(iter.next(), Some(&mut 2));
assert_eq!(iter.next(), Some(&mut 3));
assert_eq!(iter.next(), None);
}
}
> cargo test
大声疾呼的复制粘贴编程。
起初我以为用IntoIter
会弄乱,但我们还是很方便地按迭代顺序弹出结果了!
6.5. Final Code
好了,通过一点点的不安全性,我们成功地在简单的安全队列上得到了线性时间上的改进,并且我们成功地重用了来自安全堆栈的几乎所有逻辑!我们也不需要编写任何疯狂的Rc
或RefCell
内容。
pub struct List<T> {
head: Link<T>,
tail: *mut Node<T>,
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
impl<T> Node<T> {
pub fn new(elem: T) -> Box<Node<T>> {
Box::new(Node { elem, next: None })
}
}
impl<T> List<T> {
pub fn new() -> Self {
List {
head: None,
tail: std::ptr::null_mut(),
}
}
pub fn push(&mut self, elem: T) {
let mut new_tail = Node::new(elem);
let raw_tail: *mut _ = &mut *new_tail;
if !self.tail.is_null() {
unsafe {
(*self.tail).next = Some(new_tail);
}
} else {
self.head = Some(new_tail);
}
self.tail = raw_tail;
}
pub fn pop(&mut self) -> Option<T> {
self.head.take().map(|old_head| {
self.head = old_head.next;
if self.head.is_none() {
self.tail = std::ptr::null_mut();
}
old_head.elem
})
}
pub fn into_iter(self) -> IntoIter<T> {
IntoIter(self)
}
pub fn iter(&self) -> Iter<T> {
Iter {
next: self.head.as_deref(),
}
}
pub fn iter_mut(&mut self) -> IterMut<T> {
IterMut {
next: self.head.as_deref_mut(),
}
}
pub fn peek(&self) -> Option<&T> {
self.head.as_ref().map(|old_head| &old_head.elem)
}
pub fn peek_mut(&mut self) -> Option<&mut T> {
self.head.as_mut().map(|old_head| &mut old_head.elem)
}
}
pub struct IntoIter<T>(List<T>);
impl<T> Iterator for IntoIter<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
self.0.head.take().map(|old_head| {
self.0.head = old_head.next;
old_head.elem
})
}
}
pub struct Iter<'a, T> {
next: Option<&'a Node<T>>,
}
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
self.next.map(|old_head| {
self.next = old_head.next.as_deref();
&old_head.elem
})
}
}
pub struct IterMut<'a, T> {
next: Option<&'a mut Node<T>>,
}
impl<'a, T> Iterator for IterMut<'a, T> {
type Item = &'a mut T;
fn next(&mut self) -> Option<Self::Item> {
self.next.take().map(|old_head| {
self.next = old_head.next.as_deref_mut();
&mut old_head.elem
})
}
}
#[cfg(test)]
mod test {
use super::List;
#[test]
fn basics() {
let mut list = List::new();
// Check empty list behaves right
assert_eq!(list.pop(), None);
// Populate list
list.push(1);
list.push(2);
list.push(3);
// Check normal removal
assert_eq!(list.pop(), Some(1));
assert_eq!(list.pop(), Some(2));
// Push some more just to make sure nothing's corrupted
list.push(4);
list.push(5);
// Check normal removal
assert_eq!(list.pop(), Some(3));
assert_eq!(list.pop(), Some(4));
// Check exhaustion
assert_eq!(list.pop(), Some(5));
assert_eq!(list.pop(), None);
// Check the exhaustion case fixed the pointer right
list.push(6);
list.push(7);
// Check normal removal
assert_eq!(list.pop(), Some(6));
assert_eq!(list.pop(), Some(7));
assert_eq!(list.pop(), None);
}
#[test]
fn into_iter() {
let mut list = List::new();
list.push(1);
list.push(2);
list.push(3);
let mut iter = list.into_iter();
assert_eq!(iter.next(), Some(1));
assert_eq!(iter.next(), Some(2));
assert_eq!(iter.next(), Some(3));
assert_eq!(iter.next(), None);
}
#[test]
fn iter() {
let mut list = List::new();
list.push(1);
list.push(2);
list.push(3);
let mut iter = list.iter();
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), None);
}
#[test]
fn iter_mut() {
let mut list = List::new();
list.push(1);
list.push(2);
list.push(3);
let mut iter = list.iter_mut();
assert_eq!(iter.next(), Some(&mut 1));
assert_eq!(iter.next(), Some(&mut 2));
assert_eq!(iter.next(), Some(&mut 3));
assert_eq!(iter.next(), None);
}
}
7. 一个Ok但不安全的双链双端队列
不,我还没写完这本书!这并没有什么意义。 如果你真的想要更多的话,请阅读The Rustonomicon和std::collections::LinkedList的源代码
8. 一堆愚蠢的清单
好吧。就是这样。我们列了所有的清单。
哈哈,
不,
总是会有更多的清单
这一章是一个活生生的文档,讲述了更荒谬的链表,以及它们如何与Rust
互动
- The Double Single
- TODO: BList?
- TODO: SkipList?
- TODO: std::channel? – That’s like another whole chapter. Or 3.
8.1. 双单链表
我们在处理双重链接列表时很费劲,因为它们的所有权语义很纠结:没有一个节点严格地拥有任何其他节点。然而我们之所以在这个问题上挣扎,是因为我们带来了我们对链接列表是什么的先入为主的概念。也就是说,我们假设所有的链接都是朝同一个方向走的。
相反,我们可以把列表分成两半:一个向左,一个向右:
// lib.rs
// ...
pub mod silly;
// silly1.rs
use second::List as Stack;
struct List<T> {
left: Stack<T>,
right: Stack<T>,
}
现在,我们有了一个通用列表,而不仅仅是一个安全堆栈。我们可以通过推入任意一个堆栈来向左或向右增长列表。我们还可以通过将值从一端弹出到另一端来“遍历”列表。为了避免不必要的分配,我们将复制安全堆栈的源码,以访问其私有详细信息
pub struct Stack<T> {
head: Link<T>,
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>
}
impl<T> Stack<T> {
pub fn new() -> Self {
Stack { head: None }
}
pub fn push(&mut self, elem: T) {
let new_node = Box::new(Node {
elem,
next: self.head.take(),
});
self.head = Some(new_node);
}
pub fn pop(&mut self) -> Option<T> {
self.head.take().map(|node| {
let node = *node;
self.head = node.next;
node.elem
})
}
pub fn peek(&self) -> Option<&T> {
self.head.as_ref().map(|node| &node.elem)
}
pub fn peek_mut(&mut self) -> Option<&mut T> {
self.head.as_mut().map(|node| &mut node.elem)
}
}
impl<T> Drop for Stack<T> {
fn drop(&mut self) {
let mut cur_link = self.head.take();
while let Some(mut boxed_node) = cur_link {
cur_link = boxed_noded.next.take();
}
}
}
然后再重写push
和pop
pub fn push(&mut self, elem: T) {
let new_node = Box::new(Node{
elem,
next: None,
});
self.push_node(new_node);
}
fn push_node(&mut self, mut node: Box<Node<T>>) {
node.next = self.head.take();
self.head = Some(node);
}
pub fn pop(&mut self) -> Option<T> {
self.pop_node().map(|node| node.elem)
}
fn pop_node(&mut self) -> Option<Box<Node<T>>> {
self.head = node.next.take();
node
}
现在我们可以做出我们的链表了:
pub struct List<T> {
left: Stack<T>,
right: Stack<T>,
}
impl<T> List<T> {
fn new() -> Self {
List { left: Stack::new(), right: Stack::new() }
}
}
而且我们可以做一些常用的接口:
pub fn push_left(&mut self, elem: T) { self.left.push(elem) }
pub fn push_right(&mut self, elem: T) { self.right.push(elem) }
pub fn pop_left(&mut self) -> Option<T> { self.left.pop() }
pub fn pop_right(&mut self) -> Option<T> { self.right.pop() }
pub fn peek_left(&self) -> Option<&T> { self.left.peek() }
pub fn peek_right(&self) -> Option<&T> { self.right.peek() }
pub fn peek_left_mut(&mut self) -> Option<&mut T> { self.left.peek_mut() }
pub fn peek_right_mut(&mut self) -> Option<&mut T> { self.right.peek_mut() }
但最有趣的是,我们可以遍历:
pub fn go_left(&mut self) -> bool {
self.left.pop_node().map(|node| {
self.right.push_node(node);
}).is_some()
}
pub fn go_right(&mut self) -> bool {
self.right.pop_node().map(|node| {
self.left.push_node(node);
}).is_some()
}
我们在这里返回booleans
只是为了方便表示我们是否真的成功移动。现在我们来测试一下这个宝贝:
#[cfg(test)]
mod test {
use super::List;
#[test]
fn walk_aboot() {
let mut list = List::new(); // [_]
list.push_left(0); // [0,_]
list.push_right(1); // [0, _, 1]
assert_eq!(list.peek_left(), Some(&0));
assert_eq!(list.peek_right(), Some(&1));
list.push_left(2); // [0, 2, _, 1]
list.push_left(3); // [0, 2, 3, _, 1]
list.push_right(4); // [0, 2, 3, _, 4, 1]
while list.go_left() {} // [_, 0, 2, 3, 4, 1]
assert_eq!(list.pop_left(), None);
assert_eq!(list.pop_right(), Some(0)); // [_, 2, 3, 4, 1]
assert_eq!(list.pop_right(), Some(2)); // [_, 3, 4, 1]
list.push_left(5); // [5, _, 3, 4, 1]
assert_eq!(list.pop_right(), Some(3)); // [5, _, 4, 1]
assert_eq!(list.pop_left(), Some(5)); // [_, 4, 1]
assert_eq!(list.pop_right(), Some(4)); // [_, 1]
assert_eq!(list.pop_right(), Some(1)); // [_]
assert_eq!(list.pop_right(), None);
assert_eq!(list.pop_left(), None);
}
}
> cargo test
这是手指数据结构的一个极端例子,我们在结构中保持了某种手指,因此可以支持在时间上对与手指距离成正比的位置进行操作。
我们可以对手指周围的列表进行非常快速的更改,但是如果我们要在离手指很远的地方进行更改,我们就必须一直走到那边去。我们可以通过将元素从一个堆栈转移到另一个堆栈来永久地走过去,或者我们可以用&mut
暂时沿着链接走过去来进行更改。然而,&mut
永远不能回到列表中去,而我们的手指可以。
附录
转换 | 函数 |
---|---|
Option<T> -> Option<&T> |
Option::as_ref(&self) -> Option<&T> |
Option<T> -> Option<&mut T> |
Option::as_mut(&self) -> Option<&mut T> |
Option<T> -> Option<&<T as Deref>::Target> |
Option::as_deref(&self) |
Option<T> -> Option<&mut <TasDeref>::Target> |
Option::as_deref_mut(&self) |
Option<T> -> Option<U> |
Option::map(|node| node) Option::and_then(|node| Some(node)) |
Option<T> -> None |
x = y.take() x = mem::replace(&mut y, None) |
Option<T> -> T |
Option::unwrap(self) -> T |
Rc<T> -> Result<T, Rc<T>> / Ok<T> |
Rc::try_unwrap(x: Rc<T>) |
Rc<RefCell<Node<T>>> -> &RefCell<Node<T>> |
x.as_deref() |
RefCell<T> -> T |
RefCell::into_inner(self) -> T |
Result<T> -> Option<T> |
Result::ok(self) -> Option<T> |
Ref<T> -> Ref<U>/ Ref<Node<T>> -> Ref<U> |
Ref::map(Ref<T>, F) -> Ref<'_, U> where F: FnOnce<&T> -> &U |
Ref<T> -> &T |
Ref::map(Ref<T>, |x: &T| &x.elem) -> Ref<U> |
match 表达式
match
表达式在模式上产生分支。匹配的具体形式取决于模式。匹配表达式有一个检查表达式,它是要与模式进行比较的值。被审查者的表达和模式必须具有相同的类型。
匹配的行为不同,取决于检查对象表达式是位置表达式还是值表达式。如果检查对象表达式是一个值表达式,那么它首先会被计算,并放进一个临时位置,然后将结果值按顺序与arms中的模式进行比较,直到找到匹配的为止。带有匹配模式的第一个arm被选择为匹配的分支目标,模式所绑定的任何变量都被分配给arm块中的局部变量,控制流进入匹配块中。
当检审查达式是位置表达式时,匹配不分配临时位置;但是,按值绑定可以从内存位置复制或移动。如果可能的话,更可取的方法是匹配位置表达式,因为这些匹配的生存期继承place表达式的生存期,而不是被限制在匹配的内部。
let x = 1;
match x {
1 => println!("one"),
2 => println!("two"),
_ => println!("something else"),
}
模式中变量绑定的作用域是匹配守护match guard
和arm
表达式。绑定方式(移动、复制或引用)取决于模式。可以用|
操作符连接多个匹配模式。每个模式将按照从左到右的顺序进行测试,直到找到一个成功的匹配。