用太多链表写法学习Rust
有任何问题或想一次性查看所有最终代码吗？ 所有代码都在Github上！
说明: 本书当前版本是针对Rust 2018编写的，第一次发布是rustc 1.31 (2018-12-08) 如果你的rust工具链足够新，
cargo new创造的Cargo.toml文件应该包含一行edition = "2018"（如果你在很久以后读到这篇文章，可能看到更大的数字！）。你可以 用旧版工具链，但是会解锁一个隐藏的困难模式，你会得到书里没有提到的额外的编译器 报错。哇哦，有意思！
我经常被问到如何在Rust中实现链表。老实说，答案取决于你的需求是什么，要当场回答这个问 题显然不是超级容易。因此，我决定写这本书来一劳永逸地全面回答这个问题。
在这个系列中，我将通过让你实现6个链表来教你基本和高级的Rust编程。在这样做的过程中，你 应该学会：
- 下列指针类型：
&,&mut,Box,Rc,Arc,*const,*mut - 所有权、借用、继承可变性、内部可变性、Copy复制性
- 所有的关键词： struct, enum, fn, pub, impl, use, ...
- 模式匹配、泛型、析构器
- 测试
- 基本不安全Rust
是的，链表真是如此的可怕，以至于你在制作它们时要处理所有这些概念。
一切都在侧边栏中（在移动端可能会被折叠），但为了快速参考，这里是我们要做的：
为了使我们的得到的结果一致，我将写出所有输入终端的命令。我还将使用Rust的标准 包管理器Cargo来开发这个项目。Cargo并不是写Rust程序所必需的，但它比直接使用 rustc要好得多。如果你只是想玩玩，你也可以通过play.rust-lang.org 在浏览器中运行一些简单的程序。
让我们开始做我们的项目吧：
> cargo new --lib lists
> cd lists
我们会把每个列表放在一个单独的文件中，这样我们就不会失去任何工作。
需要注意的是，真实的Rust学习经历包括写代码，让编译器对你咆哮，并试图弄清楚 这些咆哮到底是什么意思。我将仔细确保这种情况尽可能频繁地发生。学会阅读和理解 Rust普遍优秀的编译器错误和文档，这对于成为一个高效的Rust程序员来说非常重要。
虽然实际上这是一个谎言。在写这本书的过程中，我遇到的编译器错误远远多于我展示 的。特别是，在后面的章节中，我不会展示很多随机的"打错字（复制粘贴）"的错误，就 是你会在每一种语言中都能遇到的错误。这是一次让编译器向我们尖叫的导游之旅。
我们的进度会很慢，而且老实说，整个过程中我不会很认真。我认为编程应该是有趣的， 哇哈哈! 如果你是那种想要最大化信息密集、严肃、正式内容的人，这本书不适合你。我 所做的一切都不适合你。你错了。
义务公益广告
我们会完全100％清楚一件事：我就是讨厌链表。恨之入骨。链表是可怕的数据结构。 当然，链表有几个很好的使用案例。
- 你想做很多大列表的拆分或合并。很多。
- 你正在做一些很棒的无锁并发的事情。
- 你在写一个内核/嵌入式的东西，想使用一个侵入式列表。
- 你正在使用纯函数式语言，有限的语义和不能修改东西使得链表比较好用。
- ......还有更多!
但所有这些情况对于任何编写Rust程序的人来说都是超级罕见的。99%的时间你应该只 使用Vec（数组栈），另外1%的时间你应该使用VecDeque（数组双端队列）。由于较少的 内存分配频率、较低的内存开销、真正的随机访问和缓存定位，这些对于大多数工作负载 来说都是公然优越的数据结构。
链表和Trie一样是小众而模糊的数据结构。很少有人会反驳我说Trie是一种小众结 构，你们平均水平程序员在整个生产生涯中很可能永远也不用学会--然而链表却有一些奇 怪的名人地位。我们教每个本科生如何写一个链表。这是唯一的小众集合 I couldn't kill from std::collections。它是 the list in C++!
作为一个社区，我们都应该对链表作为"标准"数据结构说不。它是一个很好的数据结构， 有几个很好的用例，但这些用例是特殊的，而不是常见的。
有几个人显然读了这个PSA的第一段，然后就不读了。比如，他们会试图通过列举我的伟大用 例列表中的一件事来反驳我的论点。就在第一段之后的那件事!
为了让我可以直接链接到详细的论点，下面是我看到的几种反驳的尝试，以及我对它们的回应。 如果你只是想学习一些Rust，欢迎跳到第一章!
性能并不总是重要的
是的! 也许你的应用程序是I/O瓶颈的，或者相关代码是在一些不重要的冷门的情况下。但这 甚至不是一个使用链表的论点。这是一个使用任何东西的论点。为什么要使用链表呢？使用 链接的哈希图吧!
如果性能不重要，那么应用数组的自然默认值肯定是可以的。
如果你有一个指针，那么他们会有O(1)的分割-追加-插入-删除
没错! 不过正如Bjarne Stroustrup所指出的，如果获取指针所花费的时间与复制 一个数组中所有元素所花费的时间完全相差无几的话，这实际上并不重要（这确实相当快）。
除非你的工作负载是以拆分和合并成本为主要开销，否则其他每个操作由于缓存效应和代码复杂 度所需要的惩罚会消除任何理论上的收益。
但是是的，如果你剖析发现你的应用要花大量的时间在拆分和合并上，你可能从链表中获益。
我负担不起摊销
你已经进入了一个相当小众的领域--大多数人都能承受摊销。不过，数组在最坏的情况下也是
要摊销的。仅仅因为你使用的是一个数组，并不意味着你有摊销的成本。如果你能预测你要存储
多少元素（甚至有一个上限），你就可以预留所有你需要的空间。根据我的经验，能够预测你需
要多少元素是很常见的。特别是在Rust中，所有的迭代器都会提供一个size_hint，正是针对
这种情况。
那么push和pop将是真正的O(1)操作。而且它们会比链表上的push和pop快得多。你做
一个指针偏移，写入字节，然后递增一个整数。不需要使用任何类型的分配器。
这对低延迟来说如何？
但是，是的，如果你不能预测你的负载，那么可以节省在最坏的情况下的延迟!
链表浪费的空间更少
嗯，这很复杂。一个“标准”的数组大小调整策略是增长或缩小，使最多一半的数组为空。这确实 浪费了很多空间。特别是在Rust中，我们不会自动收缩集合（如果你只是要把它重新填满，那就 太浪费了），所以浪费的空间可能会接近无穷大!
但这是最坏的情况。在最好的情况下，一个数组栈对整个数组只有三个指针的开销。基本上没有 开销。
而链表则是无条件的浪费每个元素的空间。一个单链列表浪费一个指针，而一个双链列表则浪费 两个指针。与数组不同，相对的浪费与元素的大小成正比。如果你有巨大的元素，这接近于0浪费 。如果你有微小的元素（比如说，字节），那么这可能是高达16倍的内存开销（32位上是8倍）!
实际上，这更像是23倍（32位上是11倍），因为会在字节上添加填充，将整个节点的大小对齐到 指针上。
这也是假设你的分配器的最佳情况：分配和取消分配节点是在密集地进行的，你不会因为碎片化 而损失内存。
但是是的，如果你有巨大的元素，不能预测你的负载，并且有一个像样的分配器，就可以节省内 存。
我在<函数式语言>中一直使用链表。
很好! 在函数式语言中使用链表是超级优雅的，因为你可以在没有任何改变的情况下对它们进行 操作，可以递归地描述它们，而且由于惰性的魔力，还可以使用无限列表。
具体来说，链表是不错的，因为它们代表了一个迭代，而不需要任何可变的状态。下一步只是访 问下一个子列表。
然而需要注意的是，Rust可以在数组上进行模式匹配，并且用slices来谈论子数组 ! 实际上，它在某些方面甚至比函数式链表更有表现力，因为你可以谈论最后一个元素，甚至“ 没有第一和最后两个元素的数组”或其他任何你想要的疯狂的东西。
的确，你不能用分片来构建一个列表。你只能把它们拆开。
为了偷懒，我们改用iterators。这些可以是无限的，你可以像函数式列表一样对它们进行 映射、过滤、反转和连接，而且这一切都会同样惰性地完成。这里不奇怪：切片也可以被转换成 迭代器。
但是是的，如果你限于不可变的语义，链表可以非常好。
请注意，我并不是说函数式编程一定很弱或不好。然而它从根本上讲是有语义限制的：你基本 上只允许谈论事情是怎样的，而不允许谈论它们应该怎样做。这实际上是一个特点，因为 它使编译器能够进行大量的怪异变换，并有可能找出最好的方法来做事情，而不用你 担心。然而这是以能够担心为代价的。通常有逃生舱口，但在某些限制下，你又只是在写过程 式代码。
即使是在函数式语言中，当你真正需要数据结构时，你也应该努力为任务使用合适的数据结构。 是的，单链表是你控制数据流的主要工具，但它们对于实际存储一堆数据和查询数据来说是一种 非常糟糕的方式。
链表是构建并发数据结构的好方法!
是的! 虽然编写一个并发数据结构真的是一个完全不同的野兽，而且不是一件值得轻视的事情。 当然也不是很多人都会考虑去做的事情。一旦写好了一个，你也不是真的选择使用链表。你是选 择使用MPSC队列什么的。在这种情况下，实现策略是相当遥远的!
但没错，链表是无锁并发的黑暗世界中的不折不扣的英雄。
咕哝咕哝的内核嵌入了一些干扰性的东西。
这很小众。你说的是一种情况，你甚至没有使用你的语言的运行时。这难道不是一个危险的 信号，你在做一些奇怪的事情吗？
这也是非常不安全的。
但是肯定的。要在栈上构建你那令人敬畏的零分配列表。
迭代器不会因为无关的插入/删除而失效。
你这舞跳得可真微妙。特别是当你没有垃圾回收器的时候。我可能会说，你的控制流和所有 权模式可能有点太纠结了，这取决于细节。
但是是的，你可以用光标做一些非常酷的疯狂的事情。
它们很简单，而且很适合教学
嗯，是的。你正在读一本专门针对这个前提的书。好吧，单链表是非常简单的。双链表可能会 变得有点粗糙，我们会看到。
深呼吸
好吧，那就不说了。让我们写一个亿万个链表。
现在开始第一章！
一个不好的单链栈
这章将是至今最长的一章，因为我们需要介绍所有Rust的基础知识，而且将以“艰难的方式”构建一些东西来 更好地理解这门语言。
我们将把我们的第一个链表放在src/first.rs。我们需要告诉Rustfirst.rs是我们的库用的东西。需
要做的事是我们把它放在src/lib.rs（Cargo已经给我们创建了）最上面：
// in lib.rs
pub mod first;
基本数据布局
好吧，那么什么是链表呢？基本上，它是一堆在堆上的数据片(嘘，内核的人!)，它们依次 指向对方。链表是程序员不应该碰的东西，而函数式程序员却用它来做所有事情。那么，我 们应该向函数式程序员询问链表的定义，这似乎很公平。他们可能会给你类似下面的定义：
List a = Empty | Elem a (List a)
其内容大致为“一个链表要么是空的，要么是一个元素，后面是一个链表”。这是一个递归
定义，表示为和类型，这是“一个可以有不同值的类型，这些值可能是不同的类型”的花
哨名字。Rust称和类型为枚举! 如果你来自于类C语言，这正是你所熟悉和喜爱的枚举，
但是是超速的。所以让我们把这个函数定义转录到Rust中吧!
现在，我们将避免使用泛型，保持简单。我们将只支持存储有符号的32位整数:
// in first.rs
// pub says we want people outside this module to be able to use List
pub enum List {
Empty,
Elem(i32, List),
}
呼，我被淹没了。我们还是继续编译吧：
> cargo build
error[E0072]: recursive type `first::List` has infinite size
--> src/first.rs:4:1
|
4 | pub enum List {
| ^^^^^^^^^^^^^ recursive type has infinite size
5 | Empty,
6 | Elem(i32, List),
| ---- recursive without indirection
|
= help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `first::List` representable
好吧，我不知道你是怎么想的，但我确实觉得被函数式编程社区背叛了。
如果我们真正检查一下错误信息（在我们克服了整个背叛的事情之后），我们可 以看到rustc实际上是在告诉我们如何解决这个问题：
insert indirection (e.g., a
Box,Rc, or&) at some point to makefirst::Listrepresentable
好吧，box。那是什么？让我们谷歌一下rust box...
贴在这里...
pub struct Box<T>(_);一个在堆上分配的指针类型。 更多信息参见module-level documentation。
点击链接
Box<T>被随意的称为"盒子"，提供了Rust中最简单的堆分配形式。盒子为这种分配提供所有权，并在它们离开范围时放弃它们的内容。举例
创建盒子：
let x = Box::new(5);创建一个递归数据结构：
#![allow(unused)] fn main() { #[derive(Debug)] enum List<T> { Cons(T, Box<List<T>>), Nil, } }
fn main() { let list: List<i32> = List::Cons(1, Box::new(List::Cons(2, Box::new(List::Nil)))); println!("{:?}", list); }
这会打印
Cons(1, Box(Cons(2, Box(Nil))))。递归数据类型一定要是盒子，因为如果他们的Cons的定义向这样：
Cons(T, List<T>),它不会运行。这因为链表的大小取决于链表里有几个元素，如果我们不知道Cons要分配多少内存。通过引入有已知大小的盒子，我们知道Cons会有多大。
哇，呃。这可能是我看过的最相关最有帮助的文档。字面上文档的最重要的事情是确切地 说明我们正在尝试写什么，为什么它不能正常运行，如何修复它。
铛，文档说了算。
好吧，让我们这么做：
pub enum List {
Empty,
Elem(i32, Box<List>),
}
> cargo build
Finished dev [unoptimized + debuginfo] target(s) in 0.22s
哈，他构建了！
...但由于某些原因，实际上这是一个愚蠢的链表定义。
考虑有两个元素的链表：
[] = Stack
() = Heap
[Elem A, ptr] -> (Elem B, ptr) -> (Empty, *junk*)
有两个关键问题：
- 我们正分配一个只是说“我不是节点”的节点
- 我们的一个节点不是在堆上分配的。
表面上，这两个似乎是相互矛盾的。我们分配一个额外的节点，但是我们其中一个 节点不需要被分配。然而，考虑我们链表可能的以下布局：
[ptr] -> (Elem A, ptr) -> (Elem B, *null*)
在这个布局我们现在不可避免地在堆上分配我们的节点。关键区别是不存在我们第一个 布局的junk。这个垃圾是什么？为了理解，我们将需要查看一个枚举在内存里是如何 布局的。
总的来说，如果我们有一个枚举如下：
enum Foo {
D1(T1),
D2(T2),
...
Dn(Tn),
}
一个Foo会存储一些数字来表示枚举中的哪个变量代表了(D1, D2, .. Dn)。这是枚
举的标签。它也会需要足够的空间存储最大的T1, T2, .. Tn（加上一些额外的
空间来满足对齐的需要）。
这里最大的启示是，尽管Empty是一个单一的信息位，但它必然要消耗足够的空间来放置一个
指针和一个元素，因为它要随时准备成为一个Elem。因此第一个布局的堆里多分配了一个元
素，就是满满的垃圾，比第二个布局多消耗了一点空间。
我们的一个节点完全不被分配，也许令人惊讶的是，也比总是分配它更糟糕。这是因为它给我 们提供了一个非统一的节点布局。这对推入和弹出节点没有什么明显的影响，但对拆分和合并 链表有影响。
考虑在两种布局中拆分一个链表：
布局1：
[Elem A, ptr] -> (Elem B, ptr) -> (Elem C, ptr) -> (Empty *junk*)
在C处分割：
[Elem A, ptr] -> (Elem B, ptr) -> (Empty *junk*)
[Elem C, ptr] -> (Empty *junk*)
布局2：
[ptr] -> (Elem A, ptr) -> (Elem B, ptr) -> (Elem C, *null*)
在C处分割：
[ptr] -> (Elem A, ptr) -> (Elem B, *null*)
[ptr] -> (Elem C, *null*)
布局2的拆分只需要将B的指针复制到堆栈，并将旧的值清空。布局1最终也做同样的事情， 但也要把C从堆中复制到栈中。合并则是反过来的相同过程。
链表的几个好处之一是，你可以在节点本身中构造元素，然后在链表中自由打乱，而无需 移动它。你只需要摆弄一下指针，东西就会被“移动”。布局1破坏了这个属性。
好吧，我有理由相信布局1是坏的。我们如何重写我们的链表？好吧，我们可以做这样的事 情：
pub enum List {
Empty,
ElemThenEmpty(i32),
ElemThenNotEmpty(i32, Box<List>),
}
希望这在你看来是一个更糟糕的想法。最值得注意的是，这真的让我们的逻辑复杂化了，因为
现在有一个完全无效的状态：ElemThenNotEmpty(0, Box(Empty))。它也仍然受到非
统一分配我们元素的影响。
然而它有一个有趣的特性：它完全避免了分配为空的情况，使堆分配的总数减少了1，不幸 的是，在这样做的时候，它设法浪费了更多的空间！这是因为之前的布局利用了空指针优 化。
我们之前看到，每个枚举都必须存储一个标签，以指定其位代表枚举的哪个变体。然而，如果 我们有一种特殊的枚举：
enum Foo {
A,
B(ContainsANonNullPtr),
}
空指针优化来了，从而消除了标签所需的空间。如果变体是A，则整个枚举都设置为全0，否则 就是B。这样做的原因是B永远不会是所有的0，因为它包含一个非零指针。聪明!
你能想到其他的枚举和类型可以做到这样的优化吗？其实有很多! 这就是为什么Rust对枚举布局
完全不作规定。有一些更复杂的枚举布局优化，Rust会为我们做，但空指针这个绝对是最重要的!
这意味着&、&mut、Box、Rc、Arc、Vec以及Rust中其他几个重要的类型在放入
Option时没有任何开销! (我们会在适当的时候讲到其中的大部分)。
那么，我们如何避免额外的垃圾，统一分配，并获得甜蜜的空指针优化呢？我们需要更好地将拥 有一个元素的想法与分配另一个列表分开。要做到这一点，我们必须想得更像C语言：结构体!
枚举让我们声明一个可以包含多个值中的一个类型，而结构体让我们声明一个同时包含许多值 的类型。让我们把链表分成两种类型。一个链表和一个节点。
和之前一样，一个链表要么是空的，要么是有一个元素跟在另一个链表后面。通过用一个完全独立 的类型来表示“有一个被另一个链表跟随的元素”的情况，我们可以将盒子提升到一个更理想的位置：
struct Node {
elem: i32,
next: List,
}
pub enum List {
Empty,
More(Box<Node>),
}
我们来确认优先级：
- 列表尾部永远不会分配额外的垃圾：检查!
enum是美味的空指针优化形式：检查!- 所有元素都是统一分配的：检查!
好吧！实际上，我们刚刚构建的布局正是我们用来证明我们的第一个布局（正如官方 Rust文档所建议的那样）是有问题的。
> cargo build
warning: private type `first::Node` in public interface (error E0446)
--> src/first.rs:8:10
|
8 | More(Box<Node>),
| ^^^^^^^^^
|
= note: #[warn(private_in_public)] on by default
= warning: this was previously accepted by the compiler but
is being phased out; it will become a hard error in a future release!
:(
Rust又对我们发火了。我们把List标记为公共的（因为我们希望人们能够使用它），但Node
没有。问题是枚举的内部是完全公开的，我们不允许公开谈论私有类型。我们可以将Node的所
有内容完全公开，但一般来说，在Rust中，我们倾向于保持实现细节的私有性。让我们把List
做成一个结构体，这样我们就可以隐藏实现细节：
pub struct List {
head: Link,
}
enum Link {
Empty,
More(Box<Node>),
}
struct Node {
elem: i32,
next: Link,
}
因为List是一个只有一个字段的结构体，所以它的大小与该字段相同。耶，零成本抽象!
> cargo build
warning: field is never used: `head`
--> src/first.rs:2:5
|
2 | head: Link,
| ^^^^^^^^^^
|
= note: #[warn(dead_code)] on by default
warning: variant is never constructed: `Empty`
--> src/first.rs:6:5
|
6 | Empty,
| ^^^^^
warning: variant is never constructed: `More`
--> src/first.rs:7:5
|
7 | More(Box<Node>),
| ^^^^^^^^^^^^^^^
warning: field is never used: `elem`
--> src/first.rs:11:5
|
11 | elem: i32,
| ^^^^^^^^^
warning: field is never used: `next`
--> src/first.rs:12:5
|
12 | next: Link,
| ^^^^^^^^^^
好了，这下编译好了！Rust很生气，因为据它所知，我们写的所有东西都是完全无用的：我们从
来没有用过head，使用我们库的人也不能用，因为它是私有的。反过来说，这意味着Link和
Node也是无用的。所以我们来解决这个问题吧! 让我们为我们的List实现一些代码吧!
新建
我们使用了impl块，将实际的代码与类型联系起来：
impl List {
// TODO, make code happen
}
现在我们只需要弄清楚如何实际编写代码。在Rust中，我们这么声明一个函数：
fn foo(arg1: Type1, arg2: Type2) -> ReturnType {
// body
}
我们首先需要的是一种构造列表的方式。由于我们隐藏了实现细节，我们需要以函数的形
式来提供。在Rust中，通常的方法是提供一个静态方法，也就是在impl中提供一个普通的
函数：
impl List {
pub fn new() -> Self {
List { head: Link::Empty }
}
}
有几点说明：
- Self是“我写在最上面的那个在
impl旁边的类型”的别名。很好的避免了自己的重复。 - 我们创建一个结构体的实例的方式与我们声明它的方式很相似，只是我们没有提供它的字 段类型，而是用值来初始化它们
- 我们使用
::来引用一个枚举的变体，这是命名间隔操作符。 - 一个函数的最后一个表达式是隐式返回的。这使得简单的函数变得更加整洁。你仍然可以 像其他类C语言一样，使用return来提前返回。
所有权101
现在我们可以构造一个列表，如果能用它做一些事情就更好了。我们用“普通”(非静态)方
法来做这些事情。在Rust中，方法是函数的一种特殊情况，因为self参数没有声明类型：
fn foo(self, arg2: Type2) -> ReturnType {
// body
}
self可以有3种主要形式：self、&mut self和&self。这3种形式代表了Rust中所有权
的三种主要形式：
self- 值&mut self- 可变引用&self- 共享引用
一个值代表了真正的所有权。你可以对一个值做任何你想做的事情：移动它，销毁它，改变
它，或者通过引用把它借出去。当你用值传递某物时，它就会被移动到新的位置。新的位置
现在拥有这个值，而旧的位置不能再访问它。出于这个原因，大多数方法都不想要self--如
果试图与一个链表一起工作，让它消失，那将是非常蹩脚的!
一个可变引用代表了对一个你不拥有的值的临时独占访问。你可以对一个有可变引用的值做
任何你想做的事情，只要你做完后让它处于有效状态（否则会对所有者不礼貌！）。这意味着
你实际上可以完全覆盖这个值。一个非常有用的特殊情况是将一个值交换另一个值，我们会
经常使用。你唯一不能用&mut做的事情就是把值移出，而不进行替换。对于想要改变self
的方法来说，&mut self是很好的选择。
共享引用代表了对一个你不拥有的值的临时共享访问。因为你有共享访问权，所以一般不允许
你改变任何东西。把&想象成把值放在博物馆里展示。&对于那些只想观察self的方法来
说，是非常好的。
后面我们会看到，在某些情况下，关于改变的规则是可以绕过的。这就是为什么共享引用不叫 不可变引用的原因。真的，可改变的引用可以被称为唯一引用，但我们发现，将所有权与 可改变性联系起来，99%的时候都能给出正确的直觉。
推入
push会使链表发生改变，所以我们需要使用&mut self。我们还需要取一个i32
来推入：
impl List {
pub fn push(&mut self, elem: i32) {
// TODO
}
}
首先，我们需要做一个节点来存储我们的元素：
pub fn push(&mut self, elem: i32) {
let new_node = Node {
elem: elem,
next: ?????
};
}
next是什么？嗯，整个旧链表！我们能不能... ... 就这么做？
impl List {
pub fn push(&mut self, elem: i32) {
let new_node = Node {
elem: elem,
next: self.head,
};
}
}
> cargo build
error[E0507]: cannot move out of borrowed content
--> src/first.rs:19:19
|
19 | next: self.head,
| ^^^^^^^^^ cannot move out of borrowed content
不——。Rust正告诉我们正确的事情，但它到底是什么意思，或者对它该怎么做，肯定不太显然：
不能移出借用的上下文
我们想把self.head字段移到next，但Rust不希望我们这么做。这将使self在我们结束
借用并将其“还给”它的合法所有者时，只被部分初始化。正如我们之前说过的，这是你不能用
&mut做的一件事：这将是超级无礼的，而Rust是非常有礼貌的（这也将是难以置信的危险
，但这肯定不是它关心的原因）。
如果我们把东西放回去呢？也就是我们正在创建的节点：
pub fn push(&mut self, elem: i32) {
let new_node = Box::new(Node {
elem: elem,
next: self.head,
});
self.head = Link::More(new_node);
}
> cargo build
error[E0507]: cannot move out of borrowed content
--> src/first.rs:19:19
|
19 | next: self.head,
| ^^^^^^^^^ cannot move out of borrowed content
没办法。原则上，这是Rust可以接受的，但它不会接受（出于各种原因--最严重的是例外安全） 。我们需要一些方法在Rust没有注意到它消失的情况下得到头。为了寻求建议，我们求助于臭名昭著 的Rust黑客Indiana Jones：
啊，对了，Indy建议使用mem::replace手法。这个非常有用的函数可以让我们通过用另一个值替
换来从一个借用中偷取出来一个值。我们在文件的顶部拉入std::mem，让mem在本地作用域内：
use std::mem;
并适当地使用它：
pub fn push(&mut self, elem: i32) {
let new_node = Box::new(Node {
elem: elem,
next: mem::replace(&mut self.head, Link::Empty),
});
self.head = Link::More(new_node);
}
在这里，我们用Link::Empty暂时replace到self.head，然后再把self.head换成列表的新头。
我不会撒谎：这是一件非常不幸的事情。很遗憾，我们必须这么做（目前）。
但是，嘿，push全部完成! 可能吧。我们也许应该测试一下，说实话。现在，最简单的方法
可能是写pop，并确保它产生正确的结果。
弹出
和push一样，pop想要改变列表。与push不同的是，我们实际上想返回一些东西。
但pop还需要处理一个棘手的角落情况：如果链表是空的怎么办？为了表示这种情况，
我们使用可靠的Option类型：
pub fn pop(&mut self) -> Option<i32> {
// TODO
}
Option<T>是一个枚举，表示一个可能存在的值。它可以是Some(T)，也可以是None。
我们可以像对待Link一样，自己做一个枚举，但是我们希望我们的用户能够理解我们的返回类
型到底是什么，Option是如此的无处不在，以至于每个人都知道它。事实上，它是如此的基
本，以至于在每个文件中都会隐式地导入到scope中，还有它的变体Some和None（所以我
们不必说Option::None）。
Option<T>上的尖头表示Option实际上是在T上通用的，这意味着你可以为任何类型制
作一个Option!
那么，呃，我们有这个Link的东西，我们怎么知道它是空的还是有More的？模式匹配与
match!
pub fn pop(&mut self) -> Option<i32> {
match self.head {
Link::Empty => {
// TODO
}
Link::More(node) => {
// TODO
}
};
}
> cargo build
error[E0308]: mismatched types
--> src/first.rs:27:30
|
27 | pub fn pop(&mut self) -> Option<i32> {
| --- ^^^^^^^^^^^ expected enum `std::option::Option`, found ()
| |
| this function's body doesn't return
|
= note: expected type `std::option::Option<i32>`
found type `()`
糟糕，pop必须返回一个值，而我们还没有这样做。我们其实可以返回None，但在这种
情况下，返回unimplemented!()可能是一个更好的主意，以表明我们还没有完成函数的实
现。unimplemented!()是一个宏(!表示一个宏)，当我们到达它时，它会使程序惊慌失
措(~以一种可控的方式使它崩溃)。
pub fn pop(&mut self) -> Option<i32> {
match self.head {
Link::Empty => {
// TODO
}
Link::More(node) => {
// TODO
}
};
unimplemented!()
}
无条件恐慌是发散函数的一个例子。发散函数永远不会返回给调用者，所以它
们可以用在期待任何类型的值的地方。这里，unimplemented!()被用来代替一个
Option<T>类型的值。
还要注意，我们的程序中不需要写return。一个函数中的最后一个表达式（基本上是行）隐
含了它的返回值。这让我们可以更简洁地表达真正简单的东西。你总是可以像其他类C语言一
样，显式地用return提前返回。
> cargo build
error[E0507]: cannot move out of borrowed content
--> src/first.rs:28:15
|
28 | match self.head {
| ^^^^^^^^^
| |
| cannot move out of borrowed content
| help: consider borrowing here: `&self.head`
...
32 | Link::More(node) => {
| ---- data moved here
|
note: move occurs because `node` has type `std::boxed::Box<first::Node>`, which does not implement the `Copy` trait
--> src/first.rs:32:24
|
32 | Link::More(node) => {
| ^^^^
来吧Rust，别烦我们了。一如既往，Rust对我们很生气。值得庆幸的是，这次它也给了我们完 整的信息! 默认情况下，模式匹配会尝试将其内容移动到新的分支中，但我们不能这样做，因 为我们在这里没有拥有self的值。
help: consider borrowing here: `&self.head`
Rust说我们应该在match中添加一个引用来解决这个问题。🤷♀️让我们试试吧：
pub fn pop(&mut self) -> Option<i32> {
match &self.head {
Link::Empty => {
// TODO
}
Link::More(ref node) => {
// TODO
}
};
unimplemented!()
}
> cargo build
warning: unused variable: `node`
--> src/first.rs:32:24
|
32 | Link::More(node) => {
| ^^^^ help: consider prefixing with an underscore: `_node`
|
= note: #[warn(unused_variables)] on by default
warning: field is never used: `elem`
--> src/first.rs:13:5
|
13 | elem: i32,
| ^^^^^^^^^
|
= note: #[warn(dead_code)] on by default
warning: field is never used: `next`
--> src/first.rs:14:5
|
14 | next: Link,
| ^^^^^^^^^^
万岁，又能编译了! 现在让我们弄清楚这个逻辑。我们想做一个Option，所以让我们为它做一
个变量。如果是Empty，我们需要返回None。如果是More，我们需要返回Some(i32)，并改
变列表的头。那么，让我们试着简单做到这一点？
pub fn pop(&mut self) -> Option<i32> {
let result;
match &self.head {
Link::Empty => {
result = None;
}
Link::More(ref node) => {
result = Some(node.elem);
self.head = node.next;
}
};
result
}
> cargo build
Compiling lists v0.1.0 (/Users/ABeingessner/dev/temp/lists)
error[E0507]: cannot move out of borrowed content
--> src/first.rs:35:29
|
35 | self.head = node.next;
| ^^^^^^^^^ cannot move out of borrowed content
脑袋
办公桌
我们正试图把东西移出node，但我们只有它的共享引用。
我们也许应该退一步，想想我们现在到底想做什么。我们想做的是：
- 检查列表是否为空。
- 如果是空的，就返回None
- 如果它不是空的
- 移除链表的头
- 移除它的
elem - 用它的
next代替列表的头 - 返回
Some(elem)
我们主要的想法是要删除事物，这意味着我们要通过值来获得列表的头部。我们当然不能通过我们通过
&self.head得到的共享引用来做到这一点。我们也"只"有一个对self的可变引用，所以我们移动东西
的唯一方法就是替换它。看来我们又在跳Empty舞了！
让我们试试吧：
pub fn pop(&mut self) -> Option<i32> {
let result;
match mem::replace(&mut self.head, Link::Empty) {
Link::Empty => {
result = None;
}
Link::More(node) => {
result = Some(node.elem);
self.head = node.next;
}
};
result
}
cargo build
Finished dev [unoptimized + debuginfo] target(s) in 0.22s
O M G
它在编译时没有任何警告!!!!!
其实我在这里要套用一下我个人的套路：我们返回了这里的result，但其实我们根本不
需要这么做！就像一个函数运算结果是它的最后一个表达式一样，每个块的运算结果也是它
的最后一个表达式。通常我们会用分号阻止这种行为，这样反而会使代码块运算为空元组，
()。这实际上是不声明返回值的函数--比如push--返回的值。
因此，我们可以将pop写成：
pub fn pop(&mut self) -> Option<i32> {
match mem::replace(&mut self.head, Link::Empty) {
Link::Empty => None,
Link::More(node) => {
self.head = node.next;
Some(node.elem)
}
}
}
这更简洁、更惯用。请注意，Link::Empty分支完全失去了括号，因为我们只有一个表达式 需要运算。只是一个很好的简写，用于简单的情况。
cargo build
Finished dev [unoptimized + debuginfo] target(s) in 0.22s
好，仍能运行！
测试
好了，我们已经写好了push和pop，现在我们可以真正测试我们的堆栈了!Rust和cargo支
持测试作为一级功能，所以这将是超级简单的。我们要做的就是写一个函数，然后用#[test]
来对它注解。
一般来说，在Rust社区中，我们尽量把测试放在它测试的代码旁边。然而我们通常会为测试做
一个新的命名空间，以避免与"真正的"代码冲突。就像我们使用mod来指定first.rs应该
包含在lib.rs中一样，我们可以使用mod来简单地创建一个全新的内联文件：
// in first.rs
mod test {
#[test]
fn basics() {
// TODO
}
}
我们用cargo test调用它。
> cargo test
Compiling lists v0.1.0 (/Users/ABeingessner/dev/temp/lists)
Finished dev [unoptimized + debuginfo] target(s) in 1.00s
Running /Users/ABeingessner/dev/lists/target/debug/deps/lists-86544f1d97438f1f
running 1 test
test first::test::basics ... ok
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
; 0 filtered out
耶，我们的什么都没做的测试通过了! 让我们把它变得做一些事情。我们将通过assert_eq!
宏来实现。这不是什么特殊的测试魔法。它所做的就是比较你给它的两个东西，如果它们不匹配
，程序就会惊慌失措。是的，你通过惊慌失措向测试套装表示失败!
mod test {
#[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(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);
}
}
> cargo test
error[E0433]: failed to resolve: use of undeclared type or module `List`
--> src/first.rs:43:24
|
43 | let mut list = List::new();
| ^^^^ use of undeclared type or module `List`
糟糕！因为我们做了一个新的模块，所以我们需要明确地拉入List来使用。
mod test {
use super::List;
// everything else the same
}
> cargo test
warning: unused import: `super::List`
--> src/first.rs:45:9
|
45 | use super::List;
| ^^^^^^^^^^^
|
= note: #[warn(unused_imports)] on by default
Finished dev [unoptimized + debuginfo] target(s) in 0.43s
Running /Users/ABeingessner/dev/lists/target/debug/deps/lists-86544f1d97438f1f
running 1 test
test first::test::basics ... ok
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
; 0 filtered out
耶！
不过那个警告是怎么回事...? 我们在测试中明明用的是List!
...但只在测试时使用! 为了安抚编译器(并对我们的消费者友好)，我们应该说明整个测试模块只有 在运行测试时才应该被编译。
#[cfg(test)]
mod test {
use super::List;
// everything else the same
}
这就是测试的一切!
丢弃
我们可以做一个堆栈，对它推入，弹出，我们甚至已经测试过，这一切都正确！
我们需要担心清理我们的列表吗？从技术上讲，不，完全不需要！Rust和C++一样，使用 destructors来自动清理列表。像C++一样，Rust使用析构器来自动清理资源。如果一个 类型实现了一个叫做Drop的特质，它就有一个析构器。特质是Rust对接口的花哨称呼。 Drop特质有以下接口：
pub trait Drop {
fn drop(&mut self);
}
基本上就是，“当你离开作用域时，我会给你一点时间来清理你的事务”。
如果你包含了实现Drop的类型，你其实并不需要实现Drop，你要做的只是调用它们的析构函
数。在List的情况下，它所要做的就是丢弃它的头部，而头部又可能会尝试丢弃一个
Box<Node>。所有这些都会自动为我们处理......但有一个问题。
自动处理的效果会很差。
让我们考虑一个简单的列表：
list -> A -> B -> C
当list被丢弃时，它会尝试丢弃A，会尝试丢弃B，会尝试丢弃C，你们中的一些人可能会正确
地开始紧张。这是递归代码，而递归代码会炸掉堆栈!
你们中的一些人可能会想："这显然是尾部递归，任何体面的语言都会确保这种代码不会炸堆"。 事实上，这是不正确的! 为了了解原因，让我们试着写出编译器要做的事情，为我们的List手动 实现Drop，就像编译器一样：
impl Drop for List {
fn drop(&mut self) {
// NOTE: you can't actually explicitly call `drop` in real Rust code;
// we're pretending to be the compiler!
self.head.drop(); // tail recursive - good!
}
}
impl Drop for Link {
fn drop(&mut self) {
match *self {
Link::Empty => {} // Done!
Link::More(ref mut boxed_node) => {
boxed_node.drop(); // tail recursive - good!
}
}
}
}
impl Drop for Box<Node> {
fn drop(&mut self) {
self.ptr.drop(); // uh oh, not tail recursive!
deallocate(self.ptr);
}
}
impl Drop for Node {
fn drop(&mut self) {
self.next.drop();
}
}
我们不能在回收内存之后丢弃Box的内容，所以没有办法以尾部递归的方式丢弃！而我们要
手动为List写一个迭代丢弃，将节点从它们的盒子里吊出来。
impl Drop for List {
fn drop(&mut self) {
let mut cur_link = mem::replace(&mut self.head, Link::Empty);
// `while let` == "do this thing until this pattern doesn't match"
while let Link::More(mut boxed_node) = cur_link {
cur_link = mem::replace(&mut boxed_node.next, Link::Empty);
// boxed_node goes out of scope and gets dropped here;
// but its Node's `next` field has been set to Link::Empty
// so no unbounded recursion occurs.
}
}
}
> cargo test
Running target/debug/lists-5c71138492ad4b4a
running 1 test
test first::test::basics ... ok
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured
棒！
提前优化的奖励部分！
我们对drop的实现其实和while let Some(_) = self.pop() { }很相似，当然更简单。
它有什么不同，一旦我们开始泛化我们的列表来存储整数以外的东西，会导致什么性能问题？
Click to expand for answer
Pop返回Option<i32>，而我们的实现只操作Links（Box<Node>）。所以我们的实现只移动节点的指针，而基于pop的实现将移动我们存储在节点中的值。如果我们通用我们的列表，有人用它来存储很大的有丢弃实现的东西(VBTWADI)的实例，这可能会非常昂贵。Box能够在原地运行其内容的drop实现，所以它不会受到这个问题的影响。由于VBTWADI正是实际上使用链表比使用数组更可取，所以在这种情况下表现不佳会让人有点失望。
如果你希望同时拥有两种实现的优点，你可以添加一个新的方法，fn pop_node(&mut self) -> Link，pop和drop都可以干净利落地从它派生出来。
The Final Code
好吧，6000字后，这里是我们写下的所有代码：
#![allow(unused)] fn main() { use std::mem; 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) { let new_node = Box::new(Node { elem: elem, next: mem::replace(&mut self.head, Link::Empty), }); self.head = Link::More(new_node); } pub fn pop(&mut self) -> Option<i32> { match mem::replace(&mut self.head, Link::Empty) { Link::Empty => None, Link::More(node) => { self.head = node.next; Some(node.elem) } } } } 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); } } } #[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(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); } } }
天啊，80行，一半是测试！80行，其中一半是测试! 好吧，我说过这第一篇要花点时间的!
一个好的单链栈
在上一章中，我们写了一个最小可行的单链栈。然而，有几个设计决定使它变得有点糟 糕。让我们把它变得不那么糟糕。在这样做的时候，我们将：
- 取消发明轮子
- 使我们的链表能够处理任何元素类型
- 增加选择功能
- 使我们的链表可迭代
在这个过程中，我们将了解到
- 高级选项的使用
- 泛型
- 生命期
- 迭代器
让我们添加一个名为second.rs的新文件：
// in lib.rs
pub mod first;
pub mod second;
并将first.rs中的所有内容复制到其中。
使用Option
细心的读者可能已经注意到，我们实际上重新发明了一个非常糟糕的Option版本：
enum Link {
Empty,
More(Box<Node>),
}
Link只是Option<Box<Node>>。现在，可以不用到处写Option<Box<Node>>了，
真不错。而且与pop不同的是，我们并没有把它暴露给外部世界，所以也许这很好。
然而Option有一些非常好的方法，我们一直在手动实现。我们不要这样做，而是用
Options代替一切。首先，我们简单地使用Some和None重命名所有的东西：
use std::mem;
pub struct List {
head: Link,
}
// 耶，类型别名！
type Link = Option<Box<Node>>;
struct Node {
elem: i32,
next: Link,
}
impl List {
pub fn new() -> Self {
List { head: None }
}
pub fn push(&mut self, elem: i32) {
let new_node = Box::new(Node {
elem: elem,
next: mem::replace(&mut self.head, None),
});
self.head = Some(new_node);
}
pub fn pop(&mut self) -> Option<i32> {
match mem::replace(&mut self.head, None) {
None => None,
Some(node) => {
self.head = node.next;
Some(node.elem)
}
}
}
}
impl Drop for List {
fn drop(&mut self) {
let mut cur_link = mem::replace(&mut self.head, None);
while let Some(mut boxed_node) = cur_link {
cur_link = mem::replace(&mut boxed_node.next, None);
}
}
}
这稍微好一点，但最大的胜利来自于Option的方法。
首先，mem::replace(&mut option, None)是一个非常常见的习语，Option实际上只是把它
作为一个方法：take。
pub struct List {
head: Link,
}
type Link = Option<Box<Node>>;
struct Node {
elem: i32,
next: Link,
}
impl List {
pub fn new() -> Self {
List { head: None }
}
pub fn push(&mut self, elem: i32) {
let new_node = Box::new(Node {
elem: elem,
next: self.head.take(),
});
self.head = Some(new_node);
}
pub fn pop(&mut self) -> Option<i32> {
match self.head.take() {
None => None,
Some(node) => {
self.head = node.next;
Some(node.elem)
}
}
}
}
impl Drop for List {
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();
}
}
}
第二，match option { None => None, Some(x) => Some(y) }是一个非常惯用的写法，
以至于它被称为map。map需要一个函数来对Some(x)中的x执行，以产生Some(y)
中的y。我们可以写一个适当的fn并把它传递给map，但我们更愿意写出内联要做什
么。
做到这一点的方法是使用一个闭包。闭包是匿名函数，有一个额外的超级能力：它们可以
引用闭包之外的局部变量。这使得它们在做各种条件逻辑时超级有用。我们唯一进行
match的地方是在pop中，所以让我们重写一下：
pub fn pop(&mut self) -> Option<i32> {
self.head.take().map(|node| {
self.head = node.next;
node.elem
})
}
啊，好多了。让我们确保我们没有破坏任何东西：
> cargo test
Running target/debug/lists-5c71138492ad4b4a
running 2 tests
test first::test::basics ... ok
test second::test::basics ... ok
test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured
很好! 让我们继续实际改进代码的行为。
让他全变成泛型
我们已经用 Option 和 Box 触及了一些泛型。然而到目前为止，我们一直设法避免声明任 何新的类型，这些类型实际上是对任意元素的泛型。
事实证明，这其实很容易。让我们现在就把我们所有的类型都变成泛型：
pub struct List<T> {
head: Link<T>,
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
你只要把所有的东西都加上两个尖角，你的代码就会突然间变得很通用。当然，我们不能 仅仅这样做，否则编译器就会变得超级疯狂。
> cargo test
error[E0107]: wrong number of type arguments: expected 1, found 0
--> src/second.rs:14:6
|
14 | impl List {
| ^^^^ expected 1 type argument
error[E0107]: wrong number of type arguments: expected 1, found 0
--> src/second.rs:36:15
|
36 | impl Drop for List {
| ^^^^ expected 1 type argument
问题很明显：我们一直在谈论这个List的事情，但那已经不是真的了。像 Option 和 Box
一样，我们现在必须要谈论 List<Something>。
但是我们在所有这些impl中使用的Something是什么？就像List一样，我们希望我们的实现能与
所有的T一起工作。所以，就像List一样，让我们的impl变得尖尖的：
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();
}
}
}
......就这样了!
> cargo test
Running target/debug/lists-5c71138492ad4b4a
running 2 tests
test first::test::basics ... ok
test second::test::basics ... ok
test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured
我们所有的代码现在在任意的T值上都是完全通用的，铛，Rust很容易。我想对甚至没有改
变的new做一个特别的叫喊：
pub fn new() -> Self {
List { head: None }
}
沐浴在Self的光辉中，它是重构和复制粘贴编码的守护者。同样有趣的是，当我们构造一个
链表的实例时，我们并没有写 List<T>。这一部分是根据我们从一个期望有 List<T>
的函数中返回的事实来推断的。
好了，让我们继续讨论全新的行为吧！
选择
有一件事我们上次甚至懒得实施，就是选择。让我们继续做这个。我们所要做的就是返回一 个对列表头部元素的引用，如果它存在的话。听起来很简单，让我们试试吧：
pub fn peek(&self) -> Option<&T> {
self.head.map(|node| {
&node.elem
})
}
> cargo build
error[E0515]: cannot return reference to local data `node.elem`
--> src/second.rs:37:13
|
37 | &node.elem
| ^^^^^^^^^^ returns a reference to data owned by the current function
error[E0507]: cannot move out of borrowed content
--> src/second.rs:36:9
|
36 | self.head.map(|node| {
| ^^^^^^^^^ cannot move out of borrowed content
叹息。现在怎么办，Rust？
map通过值来获取self，这将会把Option移出它所在的地方。以前这很好，因为我们只是把它
取出来，但是现在我们实际上想把它留在原处。处理这个问题的正确方法是使用Option的
as_ref方法，它的定义如下：
impl<T> Option<T> {
pub fn as_ref(&self) -> Option<&T>;
}
它将 Option.操作符
为我们处理了这个问题。
pub fn peek(&self) -> Option<&T> {
self.head.as_ref().map(|node| {
&node.elem
})
}
cargo build
Finished dev [unoptimized + debuginfo] target(s) in 0.32s
钉住了。
我们也可以用as_mut制作这个方法的可变版本：
pub fn peek_mut(&mut self) -> Option<&mut T> {
self.head.as_mut().map(|node| {
&mut node.elem
})
}
lists::cargo build
EZ
别忘了测试一下：
#[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));
}
cargo test
Running target/debug/lists-5c71138492ad4b4a
running 3 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::peek ... ok
test result: ok. 3 passed; 0 failed; 0 ignored; 0 measured
这很好，但我们并没有真正测试是否可以改变那个peek_mut的返回值，不是吗？如果一个引
用是可变的，但是没有人改变它，我们真的测试了可变性吗？让我们试试在这个
Option<&mut T>上使用map，放一个奥妙的值：
#[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));
list.peek_mut().map(|&mut value| {
value = 42
});
assert_eq!(list.peek(), Some(&42));
assert_eq!(list.pop(), Some(42));
}
> cargo test
error[E0384]: cannot assign twice to immutable variable `value`
--> src/second.rs:100:13
|
99 | list.peek_mut().map(|&mut value| {
| -----
| |
| first assignment to `value`
| help: make this binding mutable: `mut value`
100 | value = 42
| ^^^^^^^^^^ cannot assign twice to immutable variable ^~~~~
编译器抱怨说value是不可变的，但我们很清楚地写了&mut value；这又是怎么回事呢？事
实证明，这样写闭包的参数并没有说明value是一个可变的引用。相反，它创建了一个将与闭
包的参数相匹配的模式；|&mut value|意味着 "参数是一个可变的引用，但是请将它指向的值
复制到value中"。如果我们只使用|value|，value的类型将是&mut i32，我们就可以
真正地对头部进行改变：
#[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));
list.peek_mut().map(|value| {
*value = 42
});
assert_eq!(list.peek(), Some(&42));
assert_eq!(list.pop(), Some(42));
}
cargo test
Running target/debug/lists-5c71138492ad4b4a
running 3 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::peek ... ok
test result: ok. 3 passed; 0 failed; 0 ignored; 0 measured
好多了！
进入遍历
在Rust中使用Iterator特性对集合进行迭代。这比Drop要复杂一点：
pub trait Iterator {
type Item;
fn next(&mut self) -> Option<Self::Item>;
}
块里的新东西是type Item。这声明了每个迭代器的实现都有一个关联类型，叫做Item。在
这种情况下，当你调用next时，它可以吐出这个类型。
Iterator产生Option<Self::Item>的原因是该接口集成了has_next和get_next的概念。
当你有下一个值时，你产生Some(value)，而当你没有时，你产生None。这使得API在使用
和实现上更加符合人体工程学和安全，同时避免了has_next和get_next之间多余的检查和
逻辑。很好!
遗憾的是，Rust（现在还）没有类似yield语句的东西，所以我们必须自己实现这个逻辑。另
外，每个集合应该努力实现3种不同的迭代器：
- IntoIter -
T - IterMut -
&mut T - Iter -
&T
实际上，我们已经有了使用List接口实现IntoIter的所有工具：只需不断地调用pop。因此，
我们只需将IntoIter作为List的一个新类型包装器来实现：
// Tuple structs are an alternative form of struct,
// useful for trivial wrappers around other types.
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<Self::Item> {
// access fields of a tuple struct numerically
self.0.pop()
}
}
然后让我们写一个测试：
#[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);
}
> cargo test
Running target/debug/lists-5c71138492ad4b4a
running 4 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::into_iter ... ok
test second::test::peek ... ok
test result: ok. 4 passed; 0 failed; 0 ignored; 0 measured
棒！
遍历
好吧，让我们试着实现Iter。这一次，我们将不能依靠List提供我们想要的所有功能。我 们需要靠我们自己。我们想要的基本逻辑是持有一个指向当前节点的指针，我们想要产生 下一个节点。因为这个节点可能不存在（列表是空的或者我们已经完成了迭代），我们希 望这个引用是一个 Option。当我们产出一个元素时，我们希望继续到当前节点的下一个 节点。
好吧，我们来试试：
pub struct Iter<T> {
next: Option<&Node<T>>,
}
impl<T> List<T> {
pub fn iter(&self) -> Iter<T> {
Iter { next: self.head.map(|node| &node) }
}
}
impl<T> Iterator for Iter<T> {
type Item = &T;
fn next(&mut self) -> Option<Self::Item> {
self.next.map(|node| {
self.next = node.next.map(|node| &node);
&node.elem
})
}
}
> cargo build
error[E0106]: missing lifetime specifier
--> src/second.rs:72:18
|
72 | next: Option<&Node<T>>,
| ^ expected lifetime parameter
error[E0106]: missing lifetime specifier
--> src/second.rs:82:17
|
82 | type Item = &T;
| ^ expected lifetime parameter
哦，上帝。生命周期。我听说过这些事情。我听说它们是一场恶梦。
让我们试试新的东西：看到那个error[E0106]的东西吗？那是一个编译器错误代码。我们可
以让rustc用--explain来解释这些：
> rustc --explain E0106
This error indicates that a lifetime is missing from a type. If it is an error
inside a function signature, the problem may be with failing to adhere to the
lifetime elision rules (see below).
Here are some simple examples of where you'll run into this error:
struct Foo { x: &bool } // error
struct Foo<'a> { x: &'a bool } // correct
enum Bar { A(u8), B(&bool), } // error
enum Bar<'a> { A(u8), B(&'a bool), } // correct
type MyStr = &str; // error
type MyStr<'a> = &'a str; //correct
...
这......这并没有真正说明什么（这些文档假设我们比现在更了解Rust）。但看起来我们应该把
这些'a添加到我们的结构中去？让我们试试吧。
pub struct Iter<'a, T> {
next: Option<&'a Node<T>>,
}
> cargo build
error[E0106]: missing lifetime specifier
--> src/second.rs:83:22
|
83 | impl<T> Iterator for Iter<T> {
| ^^^^^^^ expected lifetime parameter
error[E0106]: missing lifetime specifier
--> src/second.rs:84:17
|
84 | type Item = &T;
| ^ expected lifetime parameter
error: aborting due to 2 previous errors
好吧，我开始看到一个模式......让我们把这些小家伙添加到我们能做的所有事情中：
pub struct Iter<'a, T> {
next: Option<&'a Node<T>>,
}
impl<'a, T> List<T> {
pub fn iter(&'a self) -> Iter<'a, T> {
Iter { next: self.head.map(|node| &'a node) }
}
}
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&'a mut self) -> Option<Self::Item> {
self.next.map(|node| {
self.next = node.next.map(|node| &'a node);
&'a node.elem
})
}
}
> cargo build
error: expected `:`, found `node`
--> src/second.rs:77:47
|
77 | Iter { next: self.head.map(|node| &'a node) }
| ---- while parsing this struct ^^^^ expected `:`
error: expected `:`, found `node`
--> src/second.rs:85:50
|
85 | self.next = node.next.map(|node| &'a node);
| ^^^^ expected `:`
error[E0063]: missing field `next` in initializer of `second::Iter<'_, _>`
--> src/second.rs:77:9
|
77 | Iter { next: self.head.map(|node| &'a node) }
| ^^^^ missing `next`
哦，上帝。我们搞坏了Rust。
也许我们应该搞清楚这个'a生命周期到底是什么意思。
生命期会吓跑很多人，因为它是对我们从编程之初就知道并喜爱的东西的改变。到目前为止， 我们实际上已经成功地避开了生命期，尽管它们一直在我们的程序中纠缠不清。
生命期在垃圾收集语言中是不必要的，因为垃圾收集器会确保所有的东西都能神奇地活到它需 要的时间。Rust中的大多数数据都是人工管理的，所以这些数据需要另一种解决方案。C和 C++给了我们一个清晰的例子，如果你只是让人们在堆栈上拿指针去随机数据会发生什么：普 遍的不可管理的不安全。这可以粗略地分为两类错误：
- 持有一个超出范围的东西的指针
- 持有一个指向被改变的东西的指针
生命期可以解决这两个问题，而且99%的情况下，它们是以一种完全透明的方式进行的。
那么什么是生命期呢？
很简单，生命期是程序中某个区域（~块/范围）代码的名称。就是这样。当一个引用被标记为生 命期时，我们是说它必须对整个区域有效。不同的东西对一个引用必须和可以在多长时间内有 效提出了要求。整个生命期系统又只是一个约束解决系统，它试图最小化每个引用的区域。如果 它成功地找到了一组满足所有约束条件的生命期，你的程序就可以编译了！否则你就会得到一个 错误反馈，说什么东西的生命期不够长。
在一个函数体中，你一般不能谈论生命期，而且也不想谈论。编译器有完整的信息，可以推断出 所有的限制条件来找到最小的生命期。然而在类型和API层面，编译器并没有所有的信息。它需 要你告诉它不同生命期之间的关系，这样它才能弄清楚你在做什么。
原则上说，这些生命期也可以不写，但这样一来，检查所有的借用将是一个巨大的全程序分析 ，会产生令人难以置信的非本地错误。Rust的系统意味着所有的借用检查都可以在每个函数体中 独立完成，你的所有错误都应该是相当局部的（或者你的类型有错误的签名）。
但是我们以前也在函数签名中写过引用，而且很好！为什么？这是因为有一些情况非常普遍， Rust会自动为你挑选生命期。这就是寿命消除。
特别地：
// Only one reference in input, so the output must be derived from that input
fn foo(&A) -> &B; // sugar for:
fn foo<'a>(&'a A) -> &'a B;
// Many inputs, assume they're all independent
fn foo(&A, &B, &C); // sugar for:
fn foo<'a, 'b, 'c>(&'a A, &'b B, &'c C);
// Methods, assume all output lifetimes are derived from `self`
fn foo(&self, &B, &C) -> &D; // sugar for:
fn foo<'a, 'b, 'c>(&'a self, &'b B, &'c C) -> &'a D;
那么，fn foo<'a>(&'a A)->&'a B是什么意思？在实践中，它的意思是，输入必须至少活得
与输出一样长。因此，如果你把输出保留很长一段时间，这将扩大输入必须有效的区域。一旦你
停止使用输出，编译器就会知道输入也可以变得无效了。
由于这个系统的设置，Rust可以确保没有东西会在释放之后被使用，而且在未完成的引用存在时 没有任何东西被改变。它只是确保这些约束条件都能得到解决。
好的。那么。Iter。
让我们回到没有生命期的状态：
pub struct Iter<T> {
next: Option<&Node<T>>,
}
impl<T> List<T> {
pub fn iter(&self) -> Iter<T> {
Iter { next: self.head.map(|node| &node) }
}
}
impl<T> Iterator for Iter<T> {
type Item = &T;
fn next(&mut self) -> Option<Self::Item> {
self.next.map(|node| {
self.next = node.next.map(|node| &node);
&node.elem
})
}
}
我们只需要在函数和类型的签名中添加生命期：
// Iter is generic over *some* lifetime, it doesn't care
pub struct Iter<'a, T> {
next: Option<&'a Node<T>>,
}
// No lifetime here, List doesn't have any associated lifetimes
impl<T> List<T> {
// We declare a fresh lifetime here for the *exact* borrow that
// creates the iter. Now &self needs to be valid as long as the
// Iter is around.
pub fn iter<'a>(&'a self) -> Iter<'a, T> {
Iter { next: self.head.map(|node| &node) }
}
}
// We *do* have a lifetime here, because Iter has one that we need to define
impl<'a, T> Iterator for Iter<'a, T> {
// Need it here too, this is a type declaration
type Item = &'a T;
// None of this needs to change, handled by the above.
// Self continues to be incredibly hype and amazing
fn next(&mut self) -> Option<Self::Item> {
self.next.map(|node| {
self.next = node.next.map(|node| &node);
&node.elem
})
}
}
好吧，我想这次我们得到了它，你们都。
cargo build
error[E0308]: mismatched types
--> src/second.rs:77:22
|
77 | Iter { next: self.head.map(|node| &node) }
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box`
|
= note: expected type `std::option::Option<&second::Node<T>>`
found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`
error[E0308]: mismatched types
--> src/second.rs:85:25
|
85 | self.next = node.next.map(|node| &node);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box`
|
= note: expected type `std::option::Option<&'a second::Node<T>>`
found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`
(╯°□°)╯︵ ┻━┻
好的。所以。我们修复了我们的生命期错误，但现在我们得到了一些新的类型错误。
我们想存储&Node的，但我们得到的是&Box<Node>的。好吧，这很容易，我们只需
要在引用之前取消对Box的引用：
impl<T> List<T> {
pub fn iter<'a>(&'a self) -> Iter<'a, T> {
Iter { next: self.head.map(|node| &*node) }
}
}
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.map(|node| &*node);
&node.elem
})
}
}
cargo build
Compiling lists v0.1.0 (/Users/ABeingessner/dev/temp/lists)
error[E0515]: cannot return reference to local data `*node`
--> src/second.rs:77:43
|
77 | Iter { next: self.head.map(|node| &*node) }
| ^^^^^^ returns a reference to data owned by the current function
error[E0507]: cannot move out of borrowed content
--> src/second.rs:77:22
|
77 | Iter { next: self.head.map(|node| &*node) }
| ^^^^^^^^^ cannot move out of borrowed content
error[E0515]: cannot return reference to local data `*node`
--> src/second.rs:85:46
|
85 | self.next = node.next.map(|node| &*node);
| ^^^^^^ returns a reference to data owned by the current function
error[E0507]: cannot move out of borrowed content
--> src/second.rs:85:25
|
85 | self.next = node.next.map(|node| &*node);
| ^^^^^^^^^ cannot move out of borrowed content
(ﾉಥ益ಥ）ﾉ ┻━┻
我们忘记了要as_ref，所以我们要把盒子移到map里，这意味着它将被丢弃，这意味着
我们的引用将被悬空：
pub struct Iter<'a, T> {
next: Option<&'a Node<T>>,
}
impl<T> List<T> {
pub fn iter<'a>(&'a self) -> Iter<'a, T> {
Iter { next: self.head.as_ref().map(|node| &*node) }
}
}
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_ref().map(|node| &*node);
&node.elem
})
}
}
cargo build
Compiling lists v0.1.0 (/Users/ABeingessner/dev/temp/lists)
error[E0308]: mismatched types
--> src/second.rs:77:22
|
77 | Iter { next: self.head.as_ref().map(|node| &*node) }
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box`
|
= note: expected type `std::option::Option<&second::Node<T>>`
found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`
error[E0308]: mismatched types
--> src/second.rs:85:25
|
85 | self.next = node.next.as_ref().map(|node| &*node);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box`
|
= note: expected type `std::option::Option<&'a second::Node<T>>`
found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`
😭
as_ref又增加了一层我们需要去除的间接性：
pub struct Iter<'a, T> {
next: Option<&'a Node<T>>,
}
impl<T> List<T> {
pub fn iter<'a>(&'a self) -> Iter<'a, 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
})
}
}
cargo build
🎉 🎉 🎉
as_deref和as_deref_mut函数在Rust 1.40中已经稳定。在此之前，你需要做map(|node| &**node)
和map(|node| &mut**node)。你可能会想"哇，那个&**的东西真的很古怪"，你没有错，但就像美
酒一样，Rust会随着时间的推移变得更好，我们不再需要这样做。通常情况下，Rust非常善于隐式地进
行这种转换，通过一个叫做解引用强制转换的过程，基本上它可以在你的代码中插入*，使其进行类
型检查。它可以做到这一点，因为我们有借用检查器来确保我们不会弄乱指针！
但是闭包同时结合了我们有一个Option<&T>而不是&T的情况，对它来说有点太复杂了，所以我们需
要通过显式的方式来帮助它。值得庆幸的是，根据我的经验，这种情况相当少见。
为了完整起见，我们可以用涡轮鱼给它一个不同的提示：
self.next = node.next.as_ref().map::<&Node<T>, _>(|node| &node);
看，map是一个泛型函数：
pub fn map<U, F>(self, f: F) -> Option<U>
涡轮鱼，:<>，让我们告诉编译器我们认为这些泛型的类型应该是什么。在这个例子中
::<&Node<T>, _>说 "它应该返回一个&Node<T>，而我不知道/不关心其他类型"。
这反过来又让编译器知道&node应该被应用于解引用强制转换，所以我们不需要手动应用所有这
些*!
但在这种情况下，我不认为这真的是一种改进，这只是一个薄薄的借口，来展示解引用强制转换和 有时有用的涡轮鱼。😅
让我们写一个测试，以确定我们没有拒绝它或任何东西：
#[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(&3));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&1));
}
> cargo test
Running target/debug/lists-5c71138492ad4b4a
running 5 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::peek ... ok
test result: ok. 4 passed; 0 failed; 0 ignored; 0 measured
全对。
最后，应该指出的是，我们实际上可以在这里应用生命期消除：
impl<T> List<T> {
pub fn iter<'a>(&'a self) -> Iter<'a, T> {
Iter { next: self.head.as_deref() }
}
}
等同于：
impl<T> List<T> {
pub fn iter(&self) -> Iter<T> {
Iter { next: self.head.as_deref() }
}
}
更少的生命期!
或者，如果你不愿意"隐藏"一个结构包含一个生命期，你可以使用Rust 2018的“
显式省略生命期”语法，'_：
impl<T> List<T> {
pub fn iter(&self) -> Iter<'_, T> {
Iter { next: self.head.as_deref() }
}
}
可变遍历
老实说，可变遍历是很疯狂的。这本身就像是一个疯狂的说法；它肯定与Iter相同！
从语义上讲，是的，但是当IterMut是合法的巫师魔法时，共享和可变引用的本质意 味着Iter是"微不足道的"。
关键的洞察力来自于我们对Iter的Iterator的实现：
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> { /* stuff */ }
}
这可以被解开语法糖为：
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next<'b>(&'b mut self) -> Option<&'a T> { /* stuff */ }
}
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(&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类型从一个引用中移出而不需要替换
rust中所有的数字基元（i32, u64, bool, f32, char, etc...）都是Copy。你也可以声明任 何用户定义的类型是Copy，只要它的所有组件都是Copy。
最关键的是，共享引用也是Copy! 因为&是Copy，Option<&>也是Copy。所以当我们做
self.next.map的时候就很好，因为Option只是被复制了。现在我们不能这样做了，因为
&mut不是Copy（如果你复制了一个&mut，你就会有两个&mut到内存的同一个位置，这是禁止
的）。相反，我们应该正确地take Option来获得它。
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
是的。它是有效的。
真他妈的。
什么。
好吧，我的意思是它实际上是应该工作的，但通常会有一些愚蠢的东西挡住了它的去路! 让 我们在这里说清楚：
我们刚刚实现了一段代码，它接收了一个单链表，并且返回链表中每个元素的可变引用各最多一 次。而且它是经过静态验证的，可以做到这一点。它是完全安全的。我们不需要做任何疯狂的事 情。
如果你问我，这是件大事。有几个原因可以说明这一点：
- 我们
takeOption<&mut>，所以我们可以独占地访问可变的引用。不需要担心有人会再看 它。 - Rust知道把一个可变引用分散到指向的结构的子字段中是可以的，因为没有办法"回到上面"， 而且它们肯定是不相干的。
事实证明，你也可以应用这个基本逻辑来为数组或树获得一个安全的IterMut！你甚至可以把迭代 器变成一个安全的迭代器。你甚至可以让迭代器变成DoubleEnded，这样你就可以同时从前面和 后面消耗迭代器了。呜呼!
Final Code
好了，第二份清单就到此为止；这是最后的代码！
#![allow(unused)] fn main() { 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 }) } 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 }) } 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(); } } } pub struct IntoIter<T>(List<T>); impl<T> Iterator for IntoIter<T> { type Item = T; fn next(&mut self) -> Option<Self::Item> { // access fields of a tuple struct numerically self.0.pop() } } 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(|node| { self.next = node.next.as_deref(); &node.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(|node| { self.next = node.next.as_deref_mut(); &mut node.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(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); } #[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)); list.peek_mut().map(|value| { *value = 42 }); assert_eq!(list.peek(), Some(&42)); assert_eq!(list.pop(), Some(42)); } #[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); } #[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(&3)); assert_eq!(iter.next(), Some(&2)); assert_eq!(iter.next(), Some(&1)); } #[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)); } } }
越来越强壮了!
一个持久化的单链栈
好了，我们已经掌握了可变单链堆栈的艺术。
让我们通过编写一个持久化的不可变的单链表，从单一所有权转向共享所有权。这 将是函数式程序员所熟悉和喜爱的列表。你可以得到头或尾，把别人的头放在别人的尾 上......而且......基本上就是这样了。不变性是一种地狱般的毒药。
在这个过程中，我们很大程度上只是熟悉了Rc和Arc，但这将为我们下一个改变游戏的链 表做准备。
让我们添加一个名为third.rs的新文件：
// in lib.rs
pub mod first;
pub mod second;
pub mod third;
这次没有复制--粘帖。这是一个净室操作。
布局
好了，回到布局的画板上。
持久列表最重要的一点是，你可以完全没有成本地操作列表的尾部：
例如，在持久列表中，这并不是一个不常见的工作情况：
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吗？对于盒子，我们当然希望如此。
函数式语言--事实上几乎所有其他语言--都通过使用垃圾回收来解决这个问题。有了垃圾收集 的魔力，只有在每个人都不再看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 third.rs
pub struct List<T> {
head: Link<T>,
}
type Link<T> = Option<Rc<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
cargo build
error[E0412]: cannot find type `Rc` in this scope
--> src/third.rs:5:23
|
5 | type Link<T> = Option<Rc<Node<T>>>;
| ^^ not found in this scope
help: possible candidate is found in another module, you can import it into scope
|
1 | use std::rc::Rc;
|
哦，该死，坏起来了。与我们用于可变列表的一切不同，Rc是如此蹩脚，以至于它甚至没有被 隐式地导入到每一个Rust程序中。真是个失败者。
use std::rc::Rc;
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，然后就可以了。
...
不，不，我们不能。
基本
我们现在已经知道了很多Rust的基础知识，所以我们可以再次做很多简单的事情。
对于构造函数，我们又可以直接复制粘贴：
impl<T> List<T> {
pub fn new() -> Self {
List { head: None }
}
}
push和pop已经不太能表达含义了。我们可以提供append和tail来代替它们，它们提
供的东西大致相同。
让我们从append开始。它接受一个列表和一个元素，并返回一个列表。就像可变列表的情况一样，
我们要做一个新的节点，它的next值是旧列表。唯一新奇的是如何获得下一个值，因为我们不
允许改变任何东西。
我们祈祷的答案就是Clone特性。几乎所有的类型都实现了克隆，它提供了一种通用的方法来获得 "像这样的另一个"，而这个逻辑上是不相干的，只给了一个共享的引用。它就像C++中的复制构造 函数，但它不会被隐式调用。
特别地，Rc使用Clone作为增加引用计数的方法。因此，与其移动一个Box到子列表中，不如直接 克隆旧列表的头部。我们甚至不需要在头部进行匹配，因为Option暴露了一个Clone的实现，它所 做的正是我们想要的事情。
好了，让我们试一试吧：
pub fn append(&self, elem: T) -> List<T> {
List { head: Some(Rc::new(Node {
elem: 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<_>>>`
嗯，我们搞砸了。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 )
}
> cargo build
很好。
这已经有足够的功能，我们可以测试它：
#[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);
// Make sure empty tail works
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。我们只有对元素的共享访问。
丢弃
像可变列表一样，我们有一个递归的析构器问题。诚然，对于不可变的列表来说，这并不是一 个糟糕的问题：如果我们遇到某处另一个节点是另一个列表的头，我们就不会递归地放弃它。 然而，这仍然是一个我们应该关心的问题，而且如何处理并不那么明确。下面是我们之前解决这 个问题的方法：
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();
}
}
}
问题在于循环的主体：
cur_link = boxed_node.next.take();
这是在盒子里改变节点，但我们不能用Rc做这个；它只给我们共享访问权，因为任何数量的其他 Rc都可能指向它。
但是如果我们知道我们是最后一个知道这个节点的列表，那么将节点移出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
好! 棒。
Arc
使用不可变链表的一个原因是跨线程共享数据。毕竟，共享可变的状态是所有邪恶的根源， 解决这个问题的一个方法是永远杀死可变的部分。
只是我们的列表根本就不是线程安全的。为了实现线程安全，我们需要原子化地处理引用 计数。否则，两个线程可以尝试增加引用计数，但只有一个会发生。那么，列表就会过早 地被释放！
为了获得线程安全，我们必须使用Arc。Arc与Rc完全相同，只是引用计数被原子化地修改。
如果你不需要的话，这有一点开销，所以Rust将两者都暴露出来。我们需要做的就是用
std::sync::Arc替换所有对Rc的引用，来制作我们的列表。就这样了。我们是线程安全
的。完成了!
但这提出了一个有趣的问题：我们如何知道一个类型是否是线程安全的？我们会不会不小心 搞砸了？
不会！在Rust中，你不可能搞乱线程安全。
之所以如此，是因为Rust通过两个特性以第一类的方式建立了线程安全模型。Send和
Sync。
如果一个类型可以安全地移动到另一个线程，那么它就是Send。如果一个类型在多个线程之
间共享是安全的，那么它就是Sync。也就是说，如果T是Sync，&T就是Send。在这种
情况下，安全意味着不可能引起数据竞争，（不要误解为更普遍的竞赛条件问题）。
这些是标记特性，这是一种华丽的说法，即它们是完全不提供接口的特性。你要么是Send， 要么不是。这只是一个其他API可以要求的属性。如果你不是合适的Send，那么就不可能被发 送到不同的线程中。很好!
Send和Sync也是基于你是否完全由Send和Sync类型组成的自动派生特性。这类似于如果你只由 Copy类型组成，你只能实现Copy，但如果你是Copy类型，我们就自动去实现它。
几乎每个类型都是Send和Sync。大多数类型都是Send，因为它们完全拥有自己的数据。大多数 类型是Sync，因为跨线程共享数据的唯一方法是把它们放在一个共享引用后面，这使得它们是 不可改变的
然而，有一些特殊的类型违反了这些属性：那些具有内部可变性的类型。到目前为止，我们只 与继承的可变性（又称外部可变性）进行了真正的互动：一个值的可变性是从其容器的可变性 中继承的。也就是说，你不能因为你喜欢而随机地改变一个不可变的值的某个字段。
内部可变性类型违反了这一点：它们让你通过一个共享的引用进行改变。内部可变性有两大类： 单元格，它只在单线程环境下工作；锁，它在多线程环境下工作。由于显而易见的原因，当你可 以使用单元格时，单元格开销更小。还有atomics，它是类似于锁的基元。
那么这一切与Rc和Arc有什么关系呢？好吧，它们都使用内部可变性来表示它们的引用计数。 更糟的是，这个引用计数在每个实例之间都是共享的！Rc只是使用一个单元，这意味着它不是线程 安全的。Arc使用了一个原子，这意味着它是线程安全的。当然，你不可能通过把一个类型放在 Arc中而神奇地使它成为线程安全的。Arc只能像其他类型一样派生出线程安全。
我真的真的不想讨论原子内存模型或非派生Send实现的更多细节。不用说，当你深入了解Rust的线 程安全故事时，事情会变得更加复杂。作为一个高级消费者，这一切都只是在工作，你真的不需 要考虑它。
Final Code
That's all I really have to say on the immutable stack. We're getting pretty good at implementing lists now!
#![allow(unused)] fn main() { 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>, } impl<T> List<T> { pub fn new() -> Self { List { head: None } } pub fn append(&self, elem: T) -> List<T> { List { head: Some(Rc::new(Node { elem: elem, next: self.head.clone(), }))} } pub fn tail(&self) -> List<T> { List { head: self.head.as_ref().and_then(|node| node.next.clone()) } } pub fn head(&self) -> Option<&T> { self.head.as_ref().map(|node| &node.elem) } pub fn iter(&self) -> Iter<'_, T> { Iter { next: self.head.as_deref() } } } 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; } } } } 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(|node| { self.next = node.next.as_deref(); &node.elem }) } } #[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); // Make sure empty tail works let list = list.tail(); assert_eq!(list.head(), None); } #[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)); } } }
一个不好但是安全的双链双向队列
现在我们已经看到了Rc，并听说了内部可变性，这给我们一个有趣的想法......。也许我 们可以通过Rc进行改变。如果是这样，也许我们可以完全安全地实现一个双链表！
在这个过程中，我们将熟悉内部可变性，并可能了解到，安全并不意味着正确。双链表很 难，我总是在某个地方犯错。
让我们添加一个新的文件，叫做fourth.rs：
// in lib.rs
pub mod first;
pub mod second;
pub mod third;
pub mod fourth;
这将是另一个净室操作，尽管像往常一样，我们可能会发现一些逻辑再次逐字适用。
免责声明：这一章基本上是一个示范，说明这是一个非常糟糕的主意。
布局
我们设计的关键是RefCell类型。RefCell的核心是一对方法：
fn borrow(&self) -> Ref<'_, T>;
fn borrow_mut(&self) -> RefMut<'_, T>;
borrow和borrow_mut的规则正是&和&mut的规则：你可以随意调用borrow，但
borrow_mut需要独占性。
RefCell不是静态地执行这些规则，而是在运行时执行这些规则。如果你违反了这些规则，
RefCell就会惊慌失措，使程序崩溃。为什么它会返回这些Ref和RefMut的东西？好吧，它们的
行为基本上和Rcs一样，只是用于借用。它们也保持RefCell的借用，直到它们超出范围。我
们稍后会讨论这个问题。
现在有了Rc和RefCell，我们可以成为......一种令人难以置信的冗长的普遍可变异的垃圾收集 语言，它不能收集循环 呀呀呀...
好了，我们要做双向链接的。这意味着每个节点都有一个指向上一个和下一个节点的指针。同 时，列表本身也有一个指向第一个和最后一个节点的指针。这样我们就可以在列表的两端快速插 入和删除。
所以我们可能需要这样的东西：
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>,
}
> cargo build
warning: field is never used: `head`
--> src/fourth.rs:5:5
|
5 | head: Link<T>,
| ^^^^^^^^^^^^^
|
= note: #[warn(dead_code)] on by default
warning: field is never used: `tail`
--> src/fourth.rs:6:5
|
6 | tail: Link<T>,
| ^^^^^^^^^^^^^
warning: field is never used: `elem`
--> src/fourth.rs:12:5
|
12 | elem: T,
| ^^^^^^^
warning: field is never used: `next`
--> src/fourth.rs:13:5
|
13 | next: Link<T>,
| ^^^^^^^^^^^^^
warning: field is never used: `prev`
--> src/fourth.rs:14:5
|
14 | prev: Link<T>,
| ^^^^^^^^^^^^^
嘿，它建好了! 很多死代码的警告，但它构建了！让我们试着使用它。
构建
好吧，我们先从建立链表开始。在这个新的系统中，这是很直接的事情。new仍然简单，
所有的字段都是None。另外，因为它变得有点不方便，我们也来做一个Node构造函数：
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 }
}
}
> cargo build
**A BUNCH OF DEAD CODE WARNINGS BUT IT BUILT**
耶!
现在让我们试着把推入写到链表的前面。因为双链表明显更复杂，我们需要做更多的工作。 单链表的操作可以简化为一个简单的单行代码，而双链表的操作则相当复杂。
特别是我们现在需要特别处理一些围绕空列表的边界情况。大多数操作只涉及head或
tail的指针。然而当过渡到空列表或从空列表过渡时，我们需要同时编辑两个列表。
如果我们保持以下的不变性，我们验证我们的方法是否有意义的一个简单方法是：每个节 点应该正好有两个指向它的指针。列表中间的每个节点都被其前任和后任所指向，而两端 的节点则被列表本身所指向。
让我们来试一试：
pub fn push_front(&mut self, elem: T) {
// new node needs +2 links, everything else should be +0
let new_head = Node::new(elem);
match self.head.take() {
Some(old_head) => {
// non-empty list, need to connect the 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
// total: +2 new_head, +0 old_head -- OK!
}
None => {
// empty list, need to set the tail
self.tail = Some(new_head.clone()); // +1 new_head
self.head = Some(new_head); // +1 new_head
// total: +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妨碍了它。
我们也许应该检查一下文档。
谷歌一下"rust refcell"
一个具有动态检查的借用规则的可变的内存位置
参见模块级文档以了解更多。
点击链接
可共享的可变异容器。
Cell<T>和RefCell<T>类型的值可以通过共享引用（即常见的&T类型）进行改变 ，而大多数Rust类型只能通过唯一的（&mut T）引用进行变异。我们说Cell<T>和RefCell提供了 "内部可变性"，而典型的Rust类型则表现为 "继承的可变性"。 细胞类型有两种风格：
Cell<T>和RefCell<T>。Cell<T>提供了get和set方 法，只需调用一个方法就可以改变内部值。不过Cell<T>只与实现Copy的类型兼容。对 于其他类型，必须使用RefCell<T>类型，在改变之前获得一个写锁。
RefCell使用Rust的生命周期来实现 "动态借用"，在这个过程中，我们可以要求对 内部值进行临时的、独占的、可改变的访问。 RefCell<T>的借用是在"运行时"跟踪的， 而不像Rust的本地引用类型那样完全是在编译时静态跟踪的。因为RefCell<T>的借用是 动态的，所以有可能试图借用一个已经被变异借用的值；当这种情况发生时，会导致线程恐 慌。何时选择内部可变性
更常见的继承可变性，即必须有唯一的访问权才能改变一个值，这是一个关键的语言元素， 使Rust能够强有力地推理指针别名，静态地防止崩溃的错误。正因为如此，继承的可变性是 首选，而内部可变性是最后的手段。由于单元格类型能够在原本不允许的地方进行改变，所 以在某些情况下，内部变异可能是合适的，甚至是必须使用的，比如说
- 为共享类型引入继承的可变性根源。
- 逻辑上不可变的方法的实现细节。
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
嘿，它构建了！文档又赢了。
崩溃
pop_front应该是与push_front相同的基本逻辑，但要倒过来。我们来试试：
pub fn pop_front(&mut self) -> Option<T> {
// need to take the old head, ensuring it's -2
self.head.take().map(|old_head| { // -1 old
match old_head.borrow_mut().next.take() {
Some(new_head) => { // -1 new
// not emptying list
new_head.borrow_mut().prev.take(); // -1 old
self.head = Some(new_head); // +1 new
// total: -2 old, +0 new
}
None => {
// emptying list
self.tail.take(); // -1 old
// total: -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
| ^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot move out of borrowed content
叹息
不能移出借用的内容
嗯... 看来盒子真的是宠坏了我们。borrow_mut只能得到一个&mut Node<T>，但我
们不能从那里移出！
我们需要一个能接收RefCell<T>并给我们一个T的东西，让我们看看文档
中是否有这样的东西：
fn into_inner(self) -> T消费RefCell，返回被包装的值。
这看起来很有希望！
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::try_unwrap返回一个Result<T, Rc<T>>。结果基本上是一个广义的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`
UGH.Result上的unwrap要求你能调试打印出错的情况。RefCell<T>只有在T实现时才实现
Debug。Node并没有实现Debug。
与其这样做，不如通过将Result转换为一个带有ok的Option来解决这个问题：
Rc::try_unwrap(old_head).ok().unwrap().into_inner().elem
请。
cargo build
对了。
呼
我们做到了。
我们应用了push和pop。
让我们通过窃取旧的stack基本测试来进行测试（因为这就是我们到目前为止所实现的全
部）：
#[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);
}
}
cargo test
Running target/debug/lists-5c71138492ad4b4a
running 9 tests
test first::test::basics ... ok
test fourth::test::basics ... ok
test second::test::iter_mut ... ok
test second::test::basics ... ok
test fifth::test::iter_mut ... ok
test third::test::basics ... ok
test second::test::iter ... ok
test third::test::iter ... ok
test second::test::into_iter ... ok
test result: ok. 9 passed; 0 failed; 0 ignored; 0 measured
钉住了。
现在我们可以正确地从列表中删除东西，我们可以实现Drop。这次的Drop在概念上更加有趣。 以前我们费力地为我们的堆栈实现Drop只是为了避免无界递归，现在我们需要实现Drop才能 让任何事情发生。
Rc不能处理循环。如果有一个循环，所有的东西都会让其他的东西活着。事实证明，一个
双向链接的列表只是一个由微小的循环组成的大链子！因此，当我们放弃我们的列表时，两
个末端节点的refcounts将被递减到1......然后就不会再发生什么了。好吧，如果我们的列
表正好包含一个节点，我们就可以了。但理想情况下，如果一个列表包含多个元素，它就应
该正常工作。也许这只是我的问题。
正如我们所看到的，删除元素是有点痛苦的。所以对我们来说，最简单的事情就是pop，直
到我们得到None：
impl<T> Drop for List<T> {
fn drop(&mut self) {
while self.pop_front().is_some() {}
}
}
cargo build
(我们实际上可以用我们的可变堆栈做到这一点，但捷径是给那些理解事物的人的！)
我们可以考虑实现push和pop的_back版本，但这只是复制粘贴的工作，我们将在本章的
后面进行讨论。现在，让我们看看更有趣的事情吧！
选择
好了，我们用push和pop做。不瞒你说，我在那里有点情绪化了。编译时的正确性是
一种可怕的毒药。
让我们做一些简单的事情来冷静一下：让我们实现peek_front。这在以前是非常容易
的。应该还是很容易的，对吗？
对吗？
事实上，我想我可以直接复制粘贴它！"。
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]: cannot return value referencing temporary value
--> src/fourth.rs:66:13
|
66 | &node.borrow().elem
| ^ ----------^^^^^
| | |
| | temporary value created here
| |
| returns a value referencing data owned by the current function
好吧，我只是在烧我的电脑。
这与我们的单链栈的逻辑完全相同。为什么事情会不同。为什么。
答案其实就是本章的全部寓意。RefCells使一切变得悲伤。到现在为止，RefCells只是一个讨 厌的东西。现在它们将成为一场噩梦。
那么发生了什么？为了理解这一点，我们需要回到borrow的定义上：
fn borrow<'a>(&'a self) -> Ref<'a, T>
fn borrow_mut<'a>(&'a self) -> RefMut<'a, T>
在布局部分，我们说：
RefCell不是静态地执行这些规则，而是在运行时执行它们。 如果你违反了这些规则，RefCell就会惊慌失措，使程序崩溃。 为什么它会返回这些Ref和RefMut的东西？好吧，它们的行为基本上和
Rcs一样，只是用于借用。 另外，它们保持RefCell的借用，直到它们超出范围。我们稍后会讨论这个问题。
现在就是那个稍后。
Ref和RefMut分别实现了Deref和DerefMut。因此，就大多数意图和目的而言，它们
的行为与&T和&mut T完全一样。然而，由于这些特性的工作方式，被返回的引用与引用
的生命周期有关，而不是与实际的RefCell有关。这意味着，只要我们保留引用，Ref就必须一直
存在。
事实上，这对于正确性是必要的。当一个Ref被放弃时，它告诉RefCell它不再被借用。因此，如 果我们确实设法保持我们的引用比引用存在的时间长，我们就可以在引用四处游荡时得到一个 RefMut，并完全破坏Rust的类型系统的一半。
那么，这让我们怎么办呢？我们只想返回一个引用，但我们需要保持这个引用的存在。但是一旦
我们从peek中返回引用，函数就结束了，而Ref就出了范围。
😖
据我所知，我们在这里实际上已经完全陷入了困境。你不能像这样把RefCells的使用完全封装起来。
但是......如果我们放弃了完全隐藏我们的实现细节呢？如果我们返回Refs呢？
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
为借来的数据的一个组成部分做一个新的参考。
是的：就像你可以映射一个Option，你也可以映射一个Ref。
我相信某些人真的很兴奋，因为单体或其他什么，但我并不关心这些。我也不认为这是一个合 适的单体，因为没有None-like的情况，但我离题了。
它很酷，这对我来说才是最重要的。我需要这个。
pub fn peek_front(&self) -> Option<Ref<T>> {
self.head.as_ref().map(|node| {
Ref::map(node.borrow(), |node| &node.elem)
})
}
> cargo build
啊耶。
让我们通过从我们的堆栈中插入测试来确保它的工作。我们需要做一些处理，以应对Refs不实 现比较的事实。
#[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);
}
> cargo test
Running target/debug/lists-5c71138492ad4b4a
running 10 tests
test first::test::basics ... ok
test fourth::test::basics ... ok
test second::test::basics ... ok
test fourth::test::peek ... ok
test second::test::iter_mut ... ok
test second::test::into_iter ... ok
test third::test::basics ... ok
test second::test::peek ... ok
test second::test::iter ... ok
test third::test::iter ... ok
test result: ok. 10 passed; 0 failed; 0 ignored; 0 measured
棒！
对称的垃圾
好了，让我们把所有的组合对称性问题都解决了。
我们所要做的就是一些基本的文本替换：
tail <-> head
next <-> prev
front -> back
哦，我们还需要为选取增加_mut的变体。
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)
})
}
并大规模地充实我们的测试：
#[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);
}
是否有一些情况我们没有测试？可能吧。组合空间在这里真的炸开了锅。我们的代码至少 没有明显的错误。
> cargo test
Running target/debug/lists-5c71138492ad4b4a
running 10 tests
test first::test::basics ... ok
test fourth::test::basics ... ok
test second::test::basics ... ok
test fourth::test::peek ... ok
test second::test::iter ... ok
test third::test::iter ... ok
test second::test::into_iter ... ok
test second::test::iter_mut ... ok
test second::test::peek ... ok
test third::test::basics ... ok
test result: ok. 10 passed; 0 failed; 0 ignored; 0 measured
不错。复制-粘贴是最好的编程方式。
迭代
让我们来试着迭代这个坏小子。
IntoIter
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()
}
}
但我们有一个有趣的新发展。以前，我们的列表只有一种"自然"的迭代顺序，而双向队列本 身就是双向的。从前到后有什么特别之处？如果有人想从另一个方向迭代呢？
Rust实际上对此有一个答案：DoubleEndedIterator。DoubleEndedIterator继承自
Iterator（意味着所有的DoubleEndedIterator都是Iterators），并且需要一个新方法：
next_back。它的签名与next完全相同，但它应该从另一端产生元素。
DoubleEndedIterator的语义对我们来说是非常方便的：迭代器成为一个双向队列。你可以
从前面和后面消耗元素，直到两端汇合，这时迭代器是空的。
与Iterator和next一样，事实证明next_back并不是DoubleEndedIterator的消费者
真正关心的东西。相反，这个接口最好的部分是它暴露了rev方法，它将迭代器包装起来，
形成一个新的迭代器，以相反的顺序产生元素。这方面的语义是相当直接的：对反向迭代器
的next的调用只是对next_back的调用。
总之，因为我们已经是一个双向队列，所以提供这个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
Running target/debug/lists-5c71138492ad4b4a
running 11 tests
test fourth::test::basics ... ok
test fourth::test::peek ... ok
test fourth::test::into_iter ... ok
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test second::test::iter_mut ... ok
test third::test::iter ... ok
test third::test::basics ... ok
test second::test::into_iter ... ok
test second::test::peek ... ok
test result: ok. 11 passed; 0 failed; 0 ignored; 0 measured
好。
Iter
Iter的宽容度会低一些。我们将不得不再次处理那些可怕的Ref的东西 由于Refs的存在，
我们不能像以前那样存储&Nodes。相反，让我们尝试存储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_ref().map(|head| head.borrow()))
}
}
> cargo build
到目前为止还不错。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| {
self.0 = node_ref.next.as_ref().map(|head| head.borrow());
Ref::map(node_ref, |node| &node.elem)
})
}
}
cargo build
error[E0521]: borrowed data escapes outside of closure
--> src/fourth.rs:155:13
|
153 | fn next(&mut self) -> Option<Self::Item> {
| --------- `self` is declared here, outside of the closure body
154 | self.0.take().map(|node_ref| {
155 | self.0 = node_ref.next.as_ref().map(|head| head.borrow());
| ^^^^^^ -------- borrow is only valid in the closure body
| |
| reference to `node_ref` escapes the closure body here
error[E0505]: cannot move out of `node_ref` because it is borrowed
--> src/fourth.rs:156:22
|
153 | fn next(&mut self) -> Option<Self::Item> {
| --------- lifetime `'1` appears in the type of `self`
154 | self.0.take().map(|node_ref| {
155 | self.0 = node_ref.next.as_ref().map(|head| head.borrow());
| ------ -------- borrow of `node_ref` occurs here
| |
| assignment requires that `node_ref` is borrowed for `'1`
156 | Ref::map(node_ref, |node| &node.elem)
| ^^^^^^^^ move out of `node_ref` occurs here
完成。
node_ref的生命周期不够长。与普通的引用不同，Rust不允许我们像这样把Ref拆开。我们从
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,
芜湖。让我们试一试...
fn next(&mut self) -> Option<Self::Item> {
self.0.take().map(|node_ref| {
let (next, elem) = Ref::map_split(node_ref, |node| {
(&node.next, &node.elem)
});
self.0 = next.as_ref().map(|head| 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
Ergh. 我们需要再次使用Ref::Map来使我们的生命周期正确。但是Ref::Map返回一个
Ref，我们需要一个Option<Ref>，但是我们需要通过Ref来映射我们的Option......
盯着远方看了很久
??????
fn next(&mut self) -> Option<Self::Item> {
self.0.take().map(|node_ref| {
let (next, elem) = Ref::map_split(node_ref, |node| {
(&node.next, &node.elem)
});
self.0 = if next.is_some() {
Some(Ref::map(next, |next| &**next.as_ref().unwrap()))
} 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<_>>>`
哦。对。这里有多个RefCell。我们在列表中走得越深，每个RefCell下的嵌套就越多。我们需要 维护，比如说，一个堆栈的Refs来代表我们持有的所有未偿借贷，因为如果我们停止查看一个元 素，我们需要递减它之前的每个RefCell的借用计数.................
我不认为我们在这里有什么可以做的。这是个死胡同。让我们试着离开RefCell。
那我们的Rcs呢？谁说我们甚至需要存储引用？为什么我们不能克隆整个Rc，以获得一个漂亮的
自己的解决方案到列表的中间？
#![allow(unused)] fn main() { 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>都要求我们在进
入下一步之前先声明一些生命周期。但是我们设法从Rc中得到的任何东西都会借用迭代
器......脑子......受伤了......啊啊啊啊啊啊
也许我们可以......映射......Rc......得到一个Rc<T>？这是个问题吗？Rc的文档似乎
没有这样的东西。事实上，有人做了一个板条箱，可以让你这样做。
但是等等，即使我们这样做了，我们也有一个更大的问题：如幽灵般可怕的迭代器失效。
以前我们对迭代器失效完全免疫，因为Iter借用了列表，使其完全不可改变。然而，如果我
们的 Iter 产生了 Rcs，他们就根本不会借用列表了！这意味着人们可以在持有指向列表的
指针时开始调用push和pop。
哦，天哪，那会怎么样？
好吧，推入其实是可以的。我们已经得到了一个进入列表的某个子范围的视图，而列表只是在 我们的视线之外增长。没什么大不了的。
然而pop是另一个故事。如果他们在我们的范围之外弹出元素，应该还是可以的。我们看
不到那些节点，所以不会发生什么。然而，如果他们试图从我们指向的节点上弹出......一切
都会被炸毁！特别是当他们去unwrap try_unwrap的结果时，实际上会失败，整个程序
会恐慌。
这实际上是非常酷的。我们可以把大量的内部拥有的指针放入列表中，并同时对其进行改变， 它就会一直工作，直到他们试图删除我们所指向的节点。即使如此，我们也不会出现悬空指 针或任何东西，程序会确定地发生恐慌！
但是在映射Rc的基础上还要处理迭代器失效的问题，这似乎......很糟糕。Rc<RefCell>
真的真的终于让我们失望了。有趣的是，我们经历了持久化堆栈案例的反转。持久堆栈努力地
收回数据的所有权，但每天都能得到引用，而我们的列表在获得所有权方面没有问题，但在借
出引用方面却非常困难。
尽管公平地说，我们的大部分挣扎都是围绕着想要隐藏实现细节和拥有一个体面的API。如果我 们想在所有地方传递节点，我们可以做得很好。
见鬼，我们可以制作多个并发的IterMuts，这些IterMuts在运行时被检查为不可改变地访问同 一个元素！这就是我们的设计。
实际上，这种设计更适合于内部数据结构，因为它永远不会让API的消费者看到。内部可变性对 于编写安全的应用程序是很好的。但对于安全的库来说就不是那么回事了。
总之，我放弃了Iter和IterMut。我们可以做它们，但是唉。
最终代码
好了，这就是在Rust中实现了一个100%安全的双链接列表。它的实现是一场噩梦，泄露了实现细 节，而且不支持几个基本操作。
但是，它存在。
哦，我猜它还充斥着大量"不必要的"Rc和RefCell之间正确性的运行时检查。我把"不必要"
加了引号，因为它们对于保证整个实际安全的事情来说是必要的。我们遇到了一些地方，这些检
查实际上是必要的。双重链接的列表有一个可怕的纠缠不清的别名和所有权的故事!
不过，这也是我们可以做的事情。特别是如果我们不关心向消费者暴露内部数据结构的话。
从这里开始，我们将专注于这个硬币的另一面：通过使我们的实现不安全来夺回所有控制权。
#![allow(unused)] 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); } } }
一个不安全的单连接队列
好吧，那个引用计算的内部可变性的东西有点失控了。当然，Rust并不希望你在一般 情况下做这样的事情？嗯，是的，也不是。Rc和Refcell可以很好地处理简单的情况， 但它们可能会变得不方便。特别是如果你想隐藏它的发生。一定会有更好的方法!
在这一章中，我们将回到单链列表，并实现一个单链队列，来尝试一下原始指针和不 安全的Rust。
让我们添加一个名为fifth.rs的新文件：
// in lib.rs
pub mod first;
pub mod second;
pub mod third;
pub mod fourth;
pub mod fifth;
我们的代码主要来自second.rs，因为队列在链表的世界里主要是对堆栈的一种增强。不过， 我们还是要从头开始，因为我们要解决一些关于布局和其他方面的基本问题。
布局
那么，单链队列是什么样的呢？好吧，当我们有一个单链接的堆栈时，我们推到列表的一端， 然后从同一端弹出。栈和队列的唯一区别是，队列会从另一端弹出。所以从我们的堆栈实现 来看，我们有：
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移到最后，我们只需一路走到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之前的节点，然后take它：
input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)
flipped pop:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)
我们今天可以做这个，然后就不干了，但那会很臭！。这两种操作都是在整个列表上行走。有 些人认为，这样的队列实现确实是一个队列，因为它暴露了正确的接口。然而我认为性能保证是 接口的一部分。我不关心精确的渐近界线，只关心“快”与“慢”。队列保证推送和弹出是快速的， 而在整个列表上行走肯定是不快的。
一个关键的观察是，我们在重复做同样的事情，浪费了大量的工作。我们能不能把这项工作记 忆化？为什么，是的？我们可以存储一个指向列表末尾的指针，然后直接跳到那里去！
事实证明，只有一种反转的push和pop方式可以使用。要反转pop，我们必须将“尾部”指针
向后移动，但由于我们的列表是单链的，我们无法有效地做到这一点。如果我们反转push，我
们只需要将“头部”指针向前移动，这很容易。
让我们试试吧：
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: elem,
// When you push onto the tail, your next is always None
next: None,
});
// swap the old tail to point to the new tail
let old_tail = mem::replace(&mut self.tail, Some(new_tail));
match old_tail {
Some(mut old_tail) => {
// If the old tail existed, update it to point to the new tail
old_tail.next = Some(new_tail);
}
None => {
// Otherwise, update the head to point to it
self.head = Some(new_tail);
}
}
}
}
由于我们对这种事情应该很熟悉，所以我现在在实现细节方面走得快一点。并不是说你应该期望
在第一次尝试时就能产生这样的代码。我只是跳过了一些我们以前不得不处理的试验和错误。实
际上，我在写这段代码时犯了很多错误，我没有显示出来。你只能看到我漏掉了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拥有它所指向
的东西，当它被丢弃时，会尝试释放它。如果我们的push实现被编译了，我们就会把列表的
尾部释放出来。实际上，按照写法，我们的代码会在每次推送时释放 old_tail。呀! 🙀
好了，我们知道如何制作一个不能拥有的指针。这只是一个引用！
pub struct List<T> {
head: Link<T>,
tail: Option<&mut Node<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: 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
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!
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
impl<'a, T> List<'a, 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
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;
}
}
cargo build
error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting 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...
--> 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...
--> 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>>
哇，这是一个非常详细的错误信息。这有点令人担忧，因为它表明我们正在做一些非常混乱的事 情。这里有一个有趣的部分：
生命期必须对内联中定义的 "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> {
// Grab the list's current head
self.head.take().map(|head| {
let head = *head;
self.head = head.next;
// If we're out of `head`, make sure to set the tail to `None`.
if self.head.is_none() {
self.tail = None;
}
head.elem
})
}
并为此写一个快速测试：
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);
}
}
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;
}
如果我们忘记这样做呢？那么我们的尾巴就会指向某个已经从列表中删除的节点。这样的节 点会立即被释放，我们就会有一个悬空的指针，而Rust应该保护我们免受其害！
事实上，Rust正在保护我们远离这种危险。只是以一种非常...迂回的方式。
那么我们能做什么呢？回到Rc<RefCell>>地狱？
拜托了。不，不。
不，我们要离开轨道，使用原始指针。我们的布局将看起来像这样：
pub struct List<T> {
head: Link<T>,
tail: *mut Node<T>, // DANGER DANGER
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
就这样了。没有这种懦弱的参考-计算-动态-借贷-检查的废话! 真实。硬的。未经检查的。 指针。
让我们都成为C语言。让我们整天都是C。
我回来了。我准备好了。
你好，unsafe。
不安全的Rust
这是一个严肃、巨大、复杂和危险的话题。它是如此严重，以至于关于它，我写了 一整本书。
长话短说，只要你允许调用其他语言，每一种语言实际上都是不安全的，因为你可以让C做任 意的坏事。是的：Java、Python、Ruby、Haskell......每个人在面对外来函数接口（FFI）的 时候都是很不安全的。
Rust通过将自己分成两种语言来接受这一事实。安全的Rust和不安全的Rust。到目前为止，我 们只使用了安全的Rust。它是完全100%安全的......除了它可以FFI到不安全的Rust。
不安全的Rust是安全Rust的一个超集。它的所有语义和规则与安全Rust完全相同，你只是被 允许做一些额外的事情，这些事情是非常不安全的，可能会导致可怕的未定义行为，困扰着C。
同样，这是一个非常巨大的话题，有很多有趣的角落案例。我真的不想深入研究它（好吧，我 其实想。我已经研究了。读那本书）。这没关系，因为有了链表，我们实际上可以忽略 几乎所有的东西。
我们要使用的主要不安全工具是原始指针。原始指针基本上是C的指针。它们没有固有的别名规 则。它们没有生命期。它们可以是空的。它们可以是悬空的。它们可以指向未初始化的内存。它 们可以被转换为整数或从整数中转换。它们可以被转换为指向不同的类型。可变性？转换它。几 乎所有的东西都可以，这意味着几乎所有的东西都可能出错。
这是一些不好的东西，老实说，要是永远不用碰这些东西，你会活得更快乐。不幸的是，我们想写 链表，而链表是很糟糕的。这意味着我们将不得不使用不安全的指针。
有两种类型的原始指针：*const T和*mut T。这些是指C语言中的const T*和T*，但
我们真的不关心 C 语言认为它们是什么意思。你只能将*const T解除引用为&T，但就像变
量的可变性一样，这只是对不正确使用的一种提示。最多只是意味着你必须先将*const转为
*mut。尽管如果你实际上没有权限去改变指针的引用，你会有一个糟糕的时间。
总之，当我们写一些代码时，我们会对此有更好的感觉。现在，
*mut T == &unchecked mut T！
基础
好了，回到基本的问题上。我们如何构建我们的链表？
之前我们只是做了：
impl<T> List<T> {
pub fn new() -> Self {
List { head: None, tail: None }
}
}
但我们不再为tail使用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来表示无。
那么，我们怎样才能得到一个空指针呢？有几种方法，但我更喜欢使用
std::ptr::null_mut()。如果你愿意，你也可以用0 as *mut _，但这似乎太乱了。
use std::ptr;
// defns...
impl<T> List<T> {
pub fn new() -> Self {
List { head: None, tail: ptr::null_mut() }
}
}
cargo build
warning: field is never used: `head`
--> src/fifth.rs:4:5
|
4 | head: Link<T>,
| ^^^^^^^^^^^^^
|
= note: #[warn(dead_code)] on by default
warning: field is never used: `tail`
--> src/fifth.rs:5:5
|
5 | tail: *mut Node<T>,
| ^^^^^^^^^^^^^^^^^^
warning: field is never used: `elem`
--> src/fifth.rs:11:5
|
11 | elem: T,
| ^^^^^^^
warning: field is never used: `head`
--> src/fifth.rs:12:5
|
12 | head: Link<T>,
| ^^^^^^^^^^^^^
噓编译器，我们很快就会用到它们。
好了，让我们继续写push。这一次，我们不是在插入后抓取一个Option<&mut Node<T>>
，而是直接抓取一个*mut Node<T>到Box的内部。我们知道我们可以稳妥地这样做，因为盒子
里的内容有一个稳定的地址，即使我们把盒子移来移去。当然，这并不安全，因为如果我们直
接丢掉盒子，我们就会有一个指向已释放内存的指针。
我们如何从一个普通的指针变成一个原始指针呢？强制的! 如果一个变量被声明为一个原始指针， 那么一个普通的引用就会被强制放到它里面：
let raw_tail: *mut _ = &mut *new_tail;
我们有我们需要的所有信息。我们可以把我们的代码翻译成，大约是以前的参考版本：
pub fn push(&mut self, elem: T) {
let mut new_tail = Box::new(Node {
elem: elem,
next: None,
});
let raw_tail: *mut _ = &mut *new_tail;
// .is_null checks for null, equivalent to checking for None
if !self.tail.is_null() {
// If the old tail existed, update it to point to the new tail
self.tail.next = Some(new_tail);
} else {
// Otherwise, update the head to point to it
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就像是安全Rust的FFI语言吗？那么，编译器希望我们明确地划分出
我们正在做的FFI-ing的地方。我们有两个选择。首先，我们可以把整个函数标记为不安全的
，在这种情况下，它就变成了一个不安全的Rust函数，只能在unsafe的上下文中调用。这不
是很好，因为我们希望我们的列表可以安全使用。其次，我们可以在我们的函数中写一个
unsafe的块，来划定FFI的边界。这就宣告了整个函数是安全的。让我们来做这件事：
pub fn push(&mut self, elem: T) {
let mut new_tail = Box::new(Node {
elem: elem,
next: None,
});
let raw_tail: *mut _ = &mut *new_tail;
// Put the box in the right place, and then grab a reference to its Node
if !self.tail.is_null() {
// If the old tail existed, update it to point to the new tail
unsafe {
(*self.tail).next = Some(new_tail);
}
} else {
// Otherwise, update the head to point to it
self.head = Some(new_tail);
}
self.tail = raw_tail;
}
> cargo build
warning: field is never used: `elem`
--> src/fifth.rs:11:5
|
11 | elem: T,
| ^^^^^^^
|
= note: #[warn(dead_code)] on by default
耶！
有意思的是，这是迄今为止我们唯一需要写不安全块的地方。我们到处都在做原始指针的事 情，这到底是怎么回事？
事实证明，当涉及到unsafe的时候，Rust是一个巨大的规则法学家的迂腐者。我们有理由
希望最大化安全的Rust程序集，因为那些程序是我们可以更有信心的。为了达到这个目的，
Rust仔细地划出了一个最小的不安全区域。请注意，我们在处理原始指针的所有其他地方都是
在分配它们，或者只是观察它们是否为空。
如果你从来没有真正解除过一个原始指针的引用，那么这些事情是完全安全的。你只是在读 写一个整数而已。唯一的一次，你可能会因为一个原始指针而陷入困境，那就是你真的解除了 对它的引用。所以Rust说只有这种操作是不安全的，而其他的都是完全安全的。
超强。迂腐。但在技术上是正确的。
然而，这引起了一个有趣的问题：尽管我们应该用unsafe块来限定不安全的范围，但它实际
上依赖于在块之外建立的状态。甚至是在函数之外！
这就是我所说的不安全污点。只要你在一个模块中使用unsafe，整个模块就会被不安全所
玷污。所有的东西都必须正确编写，以确保不安全代码的不变性得到维护。
这种污点是可以管理的，因为有隐藏性。在我们的模块之外，我们所有的结构字段都是完全私 有的，所以其他人不能以任意的方式乱用我们的状态。只要我们公开的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的调用将开始写到悬空的尾巴上！
让我们来测试一下：
#[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);
}
}
这只是堆栈测试，但预期的pop结果被翻转过来。我还在最后添加了一些额外的步骤，以确保
pop中的尾部指针损坏情况不会发生。
cargo test
Running target/debug/lists-5c71138492ad4b4a
running 12 tests
test fifth::test::basics ... ok
test first::test::basics ... ok
test fourth::test::basics ... ok
test fourth::test::peek ... ok
test second::test::basics ... ok
test fourth::test::into_iter ... 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
完美！
额外的废品
现在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_mut().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
Running target/debug/lists-5c71138492ad4b4a
running 15 tests
test fifth::test::into_iter ... ok
test fifth::test::basics ... ok
test fifth::test::iter ... ok
test fifth::test::iter_mut ... ok
test first::test::basics ... ok
test fourth::test::basics ... ok
test fourth::test::into_iter ... ok
test fourth::test::peek ... 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. 11 passed; 0 failed; 0 ignored; 0 measured
向复制-粘贴编程致敬。
起初我以为我们要用IntoIter来捣乱，但我们还是很方便地按迭代顺序弹出了！
最终代码
好了，通过一个小小的不安全因素，我们成功地在时间上比简单的安全队列有了线性的改 善，而且我们成功地重用了安全堆栈中几乎所有的逻辑！
我们也没有写任何疯狂的Rc或RefCell的东西。
#![allow(unused)] fn main() { use std::ptr; 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> List<T> { pub fn new() -> Self { List { head: None, tail: ptr::null_mut() } } pub fn push(&mut self, elem: T) { let mut new_tail = Box::new(Node { elem: 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); } self.tail = raw_tail; } 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 }) } 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 }) } 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 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> 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 { 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); } } }
一个好的不安全的双链双向队列
不，还是没有写这篇! 它真的只是没有那么多的指导意义。
如果你真的想了解更多，请阅读[Rustonomicon][]和std::collections::LinkedList的源代码！
一堆笨链表
好了。就这样吧。我们做了所有的列表。
啊哈哈哈哈
不
总会有更多的列表。
这一章是一个关于更多可笑的链接列表以及它们如何与Rust交互的鲜活的文件。
TODO: BLIST?
TODO: SkipList?
TODO: std::channel? -- 这就像另一个完整的章节。或者是3。
This chapter is a living document of the more ridiculous linked lists and how they interact with Rust.
- 双重单链表
- TODO: BList?
- TODO: SkipList?
- TODO: std::channel? -- 这就像另一个完整的章节。或者是3。
双重单链表
我们在处理双链表时很纠结，因为它们有纠结的所有权语义：没有一个节点严格地拥有任 何其他节点。然而，我们对此感到挣扎，因为我们带来了我们对什么是链表的先入为主 的概念。也就是说，我们假设所有的链接都在同一个方向。
相反，我们可以把我们的列表分成两半：一个向左走，一个向右走：
// lib.rs
// ...
pub mod silly1; // NEW!
// 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: 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_node.next.take();
}
}
}
然后只是重新设计一下push和pop：
pub fn push(&mut self, elem: T) {
let new_node = Box::new(Node {
elem: 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.take().map(|mut node| {
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()
}
我们在这里返回布尔值，只是为了方便表明我们是否真的成功移动了。现在让我们测试一下 这个宝贝：
#[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
Running target/debug/lists-5c71138492ad4b4a
running 16 tests
test fifth::test::into_iter ... ok
test fifth::test::basics ... ok
test fifth::test::iter ... ok
test fifth::test::iter_mut ... ok
test fourth::test::into_iter ... ok
test fourth::test::basics ... ok
test fourth::test::peek ... ok
test first::test::basics ... ok
test second::test::into_iter ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test second::test::iter_mut ... ok
test third::test::basics ... ok
test third::test::iter ... ok
test second::test::peek ... ok
test silly1::test::walk_aboot ... ok
test result: ok. 16 passed; 0 failed; 0 ignored; 0 measured
这是一个手指数据结构的极端例子，我们将某种手指维护到结构中，结果是可以支持对位 置的操作，时间与手指的距离成正比。
我们可以对手指周围的列表进行非常快速的修改，但是如果我们想在离手指很远的地方进行修
改，我们就必须一直走到那里。我们可以通过将元素从一个堆栈转移到另一个堆栈来永久地走
过去，或者我们可以用一个&mut临时沿着链接走过去做改变。然而，&mut永远不能回到
列表中去，而我们的手指却可以！