《通过链表学习rust》笔记

1. 创建项目

$ cargo new --lib lists
     Created library `lists` package
$ cd lists

2. 差的栈实现

第一种链表实现方式会在 src/first.rs 中编写，在 Cargo 自动生成的 src/lib.rs 开头写上一行：

pub mod first;

2.1. 内存布局

什么是链表呢？定义如下：

List a = Empty | Elem a (List a)

和类型（sum type）链表 List 要么是空表 Empty，要么持有一个元素 Elem，同时后面跟着下一个链表 List

和类型：可以具有不同类型的值的类型

用 Rust 写出这个函数式版的定义：

enum List {
  Empty,
  Elem(i32, List),
}

但是这里出现了递归定义

$ cargo build
   Compiling lists v0.1.0
error[E0072]: recursive type `first::List` has infinite size
 --> src/first.rs:2:1
  |
2 | pub enum List {
  | ^^^^^^^^^^^^^ recursive type has infinite size
3 |     Empty,
4 |     Elem(i32, List),
  |               ---- recursive without indirection
  |
  = help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `first::List` representable

rust无法计算出List类型的大小，所以要用指针来代替

enum List {
  Empty,
  Elem(i32, Box<List>),
}

但是这种定义涉及到内存在栈和堆上的分配问题，比如：

let a: List = List::Elem(100, Box::new(List::Empty));
println!("{:?}", a);
let b: List = List::Elem(10, Box::new(a));
println!("{:?}", b);

运行得到

Elem(100, Empty)
Elem(10, Elem(100, Empty))

内存布局：

[] = 栈
() = 堆

[Elem A, 指针] -> (Elem B, 指针) -> (Empty 垃圾数据)

rust的枚举体的内存分配：
- 枚举类型的变量需要用一些整数tag来指示它是该枚举类型中的哪一种变体（variant）
- 同时它需要足够的空间来存储 T1、T2、… Tn 中最大的类型（可能需要额外的空间来满足内存对齐的要求）
有两个关键问题： 1.我们给一个没有存储数据信息的结点分配了空间
- Empty 变体只含有一位的信息
- 却占用了一个元素加一个指针的空间，因为它随时可能转变为 Elem 变体
- 为了减少多分配的空间，我们可以用一个新的类型来避免
```
enum List {
  Empty,
  ElemThenEmpty(i32),
  ElemThenNotEmpty(i32, Box<List>),
}
```
  这样无需为Empty分配空间了，但它没有解决第2个问题，内存分配不一致的问题
  1. 其中一个结点却没有被分配堆空间
- 第1个结点分配在了栈上

空指针优化每个枚举变量都会有标志来标明它是哪种变体。但如果是这样的枚举类型：
enum Foo {
    A,
    B(NonNullPtr),
}
空指针优化就能起作用了。它可以节省标签占用的空间 如果是变体 A，就将储存内容全部置零反之，非零内容则代表变体 B

为了应用空指针优化，又解决内存分配不一致的问题：
- 思想
  - 对于我们声明的类型而言，如果说枚举体能让它持有若干值中的一种，那么结构体就能使它同时拥有多个值
  - 据此，我们可以将原来的 List 类型拆成两部分：List 与 Node 类型
  - 我们最好把存放元素的空间，与为下一链表所分配的空间分开考虑
  - 这样一个链表要么是空表，要么“持有一个元素，同时后面跟着下一个链表”
- 应用空指针优化，需要把枚举体写成如下形式
```
enum List {
  Empty,
  Elem(Box<_>),
}
```
- 我们通过用一个完全独立的类型来实现「持有一个元素，同时后面跟着下一个链表」
- 解决内存分配不一致问题
  - 所以有链表结点都存在堆上
  - 要保存的元素用结构体来表达
    struct Node { elem: i32, next: List, }
- 另一种可能的布局：
```
[指针] -> (Elem A, 指针) -> (Elem B, 空指针) -> (Empty)
```
```

得到新的链表：

#[derive(Debug)]
struct Node {
  elem: i32, 
  next: List,
}

#[derive(Debug)]
enum List {
  Empty,
  Elem(Box<Node>),
}

使用链表：

fn main() {
  let a = List::Elem(Box::new(Node {elem: 100, next: List::Empty}));
  println!("a: {:?}", a);
  match a {
    List::Elem(ref node) => {
      println!("a.elem: {:?}", node.elem);
      println!("a.next: {:?}", node.next);
    }    
    List::Empty => println!("a.elem: Empty"),
  }

  let b = List::Elem(Box::new(Node {elem: 10, next: a}));
  println!("b: {:?}", b);
  match b {
    List::Elem(ref node) => {
      println!("b.elem: {:?}", node.elem);
      println!("b.next: {:?}", node.next);
    }
    List::Empty => println!("b.elem: Empty"),
  }
}

得到结果：

a: Elem(Node { elem: 100, next: Empty })
a.elem: 100
a.next: Empty
b: Elem(Node { elem: 10, next: Elem(Node { elem: 100, next: Empty })
 })
b.elem: 10
b.next: Elem(Node { elem: 100, next: Empty })

为了让别人能使用 List，我们将List访问权限设置为公有 pub:

struct Node {
    elem: i32,
    next: List,
}

pub enum List {
    Empty,
    More(Box<Node>),
}

但编译出错了：

❯ cargo build
   Compiling lists v0.1.0 (/home/wilson/experiments/rust/lists) error[E0446]: private type `Node` in public interface
  --> src/main.rs:10:8
   |
2  | struct Node {
   | ----------- `Node` declared as private
...
10 |   Elem(Box<Node>),
   |        ^^^^^^^^^ can't leak private type

error: aborting due to previous error

For more information about this error, try `rustc --explain E0446`.
error: could not compile `lists`

To learn more, run the command again with --verbose.

问题在于公有枚举体的所有内部变体也都是公有的，而私有类型不能出现在公有的地方。理论上我们可以也把 Node 设为公有类型，但这不符合 Rust 编程风格，我们应该将实现细节隐藏起来。为达成这一点，我们可以将 List 设成结构体：

#[derive(Debug)]
struct Node {
  elem: i32, 
  next: Link,
}

#[derive(Debug)]
enum Link {
  Empty,
  Elem(Box<Node>),
}

#[derive(Debug)]
pub struct List {
  head: Link,
}

fn main() {
  let a = Link::Elem(Box::new(Node {elem: 100, next: Link::Empty}));
  println!("a: {:?}", a);
  match a {
    Link::Elem(ref node) => {
      println!("a.elem: {:?}", node.elem);
      println!("a.next: {:?}", node.next);
    }    
    Link::Empty => println!("a.elem: Empty"),
  }

  let b = Link::Elem(Box::new(Node {elem: 10, next: a}));
  println!("b: {:?}", b);
  match b {
    Link::Elem(ref node) => {
      println!("b.elem: {:?}", node.elem);
      println!("b.next: {:?}", node.next);
    }
    Link::Empty => println!("b.elem: Empty"),
  }
  let list = List {head: b};
  println!("list: {:?}", list);
  println!("list.head: {:?}", list.head);
}

运行后得到：

❯ cargo run
   Compiling lists v0.1.0 (/home/wilson/experiments/rust/lists)
    Finished dev [unoptimized + debuginfo] target(s) in 0.24s
     Running `target/debug/lists`

a: Elem(Node { elem: 100, next: Empty })
a.elem: 100
a.next: Empty

b: Elem(Node { elem: 10, next: Elem(Node { elem: 100, next: Empty }) })
b.elem: 10
b.next: Elem(Node { elem: 100, next: Empty })

list: List { head: Elem(Node { elem: 10, next: Elem(Node { elem: 100
, next: Empty }) }) }

list.head: Elem(Node { elem: 10, next: Elem(Node { elem: 100, next:
Empty }) })

2.2. New 方法

我们创建好了链表的数据结构，现在要加入的是它的方法。首先是 new 方法

impl List {
  fn new() -> Self {
    List {head: Link::Empty}
  }
}

可以用 Self 指代 impl 块所实现的类型

2.3. 所有权初探

在 Rust 中，方法就是一类特殊的函数。它们拥有无须指明类型的 self 参数，self 参数主要有三种形式：self、&mut self、&self。它们分别代表了 Rust 中主要的三种所有权：

self代表值（value）
- 值意味着真正的所有权
  - 你可以移动它、销毁它、改变它
  - 或者以引用的方式借出它
- 当你按值传递对象时，它会被移动到新的变量
&mut self：可变引用
- 可变引用意味着对你不拥有的对象暂时有独占的访问权利
- 只要有了可变引用，那你就可以为所欲为了
&self：共享引用
- 共享引用意味着对你不拥有的对象暂时有共享的访问权利

2.4. Push 方法

因为push会改变链表，所以我们用&mut self

impl List {
  pub fn push(&mut self, elem: i32) {
      let node = Node {
        elem,
        next: mem::replace(&mut self.head, Link::Empty),
      }
      self.head = Link::More(Box::new(node));
  }
}

2.5. Pop 方法

pop方法也会改写list，所以仍用&mut self。但pop会遇到链表为空和链表非空的情况，所以：

impl List {
  pub fn pop(&mut self) {
    match mem::replace(&mut self.head, Link::Empty) {
      Link::Empty => None,
      Link::More(pnode) => {
          self.head = pnode.next;
          Some(pnode.elem)
      }
    }
  }
}

2.6. 单元测试

一般来说，我们会尽量将我们的测试放在代码旁边
我们通常为测试创建一个新的名称空间，以避免与“真正的”代码发生冲突
我们可以使用mod来创建一个全新的内联文件
我们所要做的就是编写一个函数，并用#[test]标注它

// in first.rs

#[cfg(test)] // 只在测试时才编译这个模块，否则模块内的List导入但未使用
mod test {
  use super::List; //因为我们创建了一个新模块，所以需要显式地导入`List`来使用它

  #[test]
  fn basics() {
  // Check empty list behaves right
  assert_eq!(list.pop(), None);}
}

因为我们创建了一个新模块，所以需要显式地导入List来使用它
因为我们只有在测试时使用了List，所以我们应该指出，只有在运行测试时才应该编译整个测试模块

2.7. Drop 方法

如果一个类型实现了一个称为Drop的特征，那么它就有一个析构函数，Drop的声明如下：

pub trait Drop {
    fn drop(&mut self);
}

为List实现Drop

impl Drop for List {
  fn drop(&mut self) {
    let mut cur_link = mem::replace(&mut self.head, Link::Empty);

    while let Link::More(pnode) = cur_link {
      cur_link = mem::replace(&mut pnode.next, Link::Empty);
    }
  }
}

3 一个好的单链接堆栈

让我们添加一个名为second.rs的新文件

// in lib.rs 
pub mod first
pub mod second

3.1. 使用 Option

实际上可以改进的地方如下：

enum用Option表达

 enum Link {
     Empty,
     More(Box<Node>),
 }

相当于 Option<Box<Node>>，再用type Link = Option<Box<Node>>，于是我们得到新的List数据结构写法：

 struct List {
   head: Link,
 }

 type Link = Option<Box<Node>>;

 struct Node {
   elem: i32,
   next: Link,
 }

mem::replace可以用take表示实际上 mem::replace(&mut option, none) 是非常常见的用法，rust用take方法来实现
```
 pub fn take(&mut self) -> Option<T>
```
所以 mem::replce(&mut self.head, Link::Empty); 就相当于 self.head.take()
match option { None => None, Some(x) => Some(y)} 是一个非常常见的习惯用法，它被称为map
1. map接受一个函数，在Some(x)中的x上执行，生成Some(y)中的y
2. 我们可以编写一个合适的fn并将其传递给map，但我们更愿意编写内联操作
```
pub fn pop(&mut self) -> Option<i32> {
  self.head.take().map(|node| {
 self.head = node.next;
  Some(node.elem)
  })
}
```

3.2. Generic

把具体类型转变为泛型<T>

List数据结构

 struct List<T> {
   head: Link<T>,
 }
 type Link<T> = Option<Box<Node<T>>>;
 struct Node<T> {
   elem: T,
   next: Link,
 }

List的方法

 impl<T> List<T> {
     pub fn new() -> Self {
       List {head: None}
     }

     pub fn push(&mut self, elem: T) {
       let node = Node {
         elem,
         next: self.head.take(),
       }
       self.head = Some(node);
     }

     pub fn pop(&mut self) -> Option<T> {
       self.head.take().map(|node| {
         self.head = node.next;
         Some(node.elem)
       })
     }
 }

 impl<T> Drop for List<T> {
   let cur_link = self.head.take();
   while let Some(cur_node) = cur_link {
       cur_link = cur_node.next.take();
   }
 }

3.3. Peek

我们所需要做的就是返回对列表头元素的引用(如果它存在的话)

impl List {
  pub fn peek(&mut self) -> Option<&T> {
    self.head.as_ref().map(|node| {
      &node.elem
    })
  }
  pub fn peek_mut(&mut self) -> Option<&mut T> {
    self.head.as_mut().map(|node| {
      &mut node.elem
    })
  }
}

加入测试

mod test {
  #[test]
  fn peek() {
    let mut list = List::new();
    assert_eq!(list.peek(), None);
    assert_eq!(list.peek_mut(), None);

    list.push(1); list.push(2); list.push(3);

    assert_eq!(list.peek(), Some(&3));
    assert_eq!(list.peek_mut(), Some(&mut 3));
  }
}

但是当我们要修改值时要注意：

mod test {
  #[test]
  fn peek() {
    let mut list = List::new();
    list.push(1); list.push(2); list.push(3);
    list.peek_mut().map(|&mut elem| {
      elem = 100;
    });
  }
}

事实证明，这样写闭包的参数并不能说明value是一个可变引用。相反，它创建了一个模式，将与闭包的参数进行匹配；|&mut value|的意思是 “参数是一个可突变的引用，但请将它指向的值复制到value中即可”。如果我们只是使用|value|，那么value的类型将是&mut i32

mod test {
  #[test]
  fn peek() {
    let mut list = List::new();
    list.push(1); list.push(2); list.push(3);
    list.peek_mut().map(|elem| {
      *elem = 100;
    });
  }
}

3.4. IntoIter

rust中迭代器的声明如下：

pub trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
}

迭代器产生Option<Self::Item>的原因是接口合并了has_next和get_next概念。每个类型需要实现三种类型的迭代器：

Into迭代：T
Mut迭代：&mut T
迭代：&T

创建一个IntoIter类型
```
 pub struct IntoIter<T>(List<T>);
```

为List<T>实现into_iter方法，将List<T>类型转换为IntoIter<T>类型

 impl<T> List<T> {
   pub fn into_iter(self) -> IntoIter<T> {
       IntoIter(self)
   }
 }

为IntoIter<T>类型实现Iterator特性

 impl<T> Iterator for IntoIter<T> {
   type Item = T;
   pub fn next(&mut self) -> Option<Self::Item> {
     self.0.pop()
   }
 }

写测试代码

 mod test {
   #[test]
   fn into_iter() {
     let mut list = List::new();
     list.push(1); list.push(2); list.push(3);

     let mut iter = list.into_iter();
     assert_eq!(iter.next(), Some(3));
     assert_eq!(iter.next(), Some(2));
     assert_eq!(iter.next(), Some(1));
     assert_eq!(iter.next(), None);
   }
 }

3.5. Iter

pub struct List<T> {
    head: Link<T>,
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None }
    }

    pub fn push(&mut self, elem: T) {
        let new_node = Box::new(Node {
            elem,
            next: self.head.take(),
        });
        self.head = Some(new_node);
    }

    pub fn pop(&mut self) -> Option<T> {
        self.head.take().map(|pnode| {
            self.head = pnode.next;
            pnode.elem
        })
    }

    pub fn peek(&self) -> Option<&T> {
        self.head.as_ref().map(|node| &node.elem)
    }

    pub fn peek_mut(&mut self) -> Option<&mut T> {
        self.head.as_mut().map(|node| &mut node.elem)
    }
}

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut cur_link = self.head.take();

        while let Some(mut cur_node) = cur_link {
            cur_link = cur_node.next.take();
        }
    }
}

pub struct IntoIter<T>(List<T>);

impl<T> List<T> {
    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        self.0.head.take().map(|node| {
            self.0.head = node.next;
            node.elem
        })
    }
}

pub struct IterRef<'a, T>(Option<&'a Node<T>>);

impl<T> List<T> {
    pub fn iter_ref<'a>(&'a self) -> IterRef<'a, T> {
        IterRef(self.head.as_deref())
    }
}

impl<'a, T> Iterator for IterRef<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.map(|node| {
            self.0 = node.next.as_deref();
            &node.elem
        })
    }
}

#[cfg(test)]
mod test {
    use super::List;

    #[test]
    fn sec_list() {
        let mut list = List::new();
        list.push(1);
        list.push(2);
        list.push(3);

        assert_eq!(list.peek(), Some(&3));
        assert_eq!(list.peek_mut(), Some(&mut 3));

        if let Some(elem) = list.peek_mut() {
            *elem = 100;
        }
        assert_eq!(list.peek(), Some(&100));
        list.peek_mut().map(|elem| *elem = 3);

        // Check normal removal
        assert_eq!(list.pop(), Some(3));
        assert_eq!(list.pop(), Some(2));

        // Push some more just to make sure nothing's corrupted
        list.push(4);
        list.push(5);

        // Check normal removal
        assert_eq!(list.pop(), Some(5));
        assert_eq!(list.pop(), Some(4));

        // Check exhaustion
        assert_eq!(list.pop(), Some(1));
        assert_eq!(list.pop(), None);

        let mut list = List::new();
        list.push(1);
        list.push(2);
        list.push(3);

        let mut iter = list.into_iter();
        assert_eq!(iter.next(), Some(3));
        assert_eq!(iter.next(), Some(2));
        assert_eq!(iter.next(), Some(1));
        assert_eq!(iter.next(), None);

        let mut list = List::new();
        list.push(1);
        list.push(2);
        list.push(3);

        let mut iter_ref = list.iter_ref();
        assert_eq!(iter_ref.next(), Some(&3));
        assert_eq!(iter_ref.next(), Some(&2));
        assert_eq!(iter_ref.next(), Some(&1));
    }
}

3.6. IterMut

根据IterRef的实现：

impl<'a, T> Iterator for IterRef<'a, T> {
  type Item = &'a T;

  fn next(&mut self) -> Option<Self::Item> {...}
}

去糖后的真实代码是

impl<'a, T> Iterator for IterRef<'a, T> {
  type Item = &'a T;
  fn next<'b>(&'b mut self) -> Option<&'a T> {...}
}

next的签名在输入和输出的生命期之间没有建立任何约束! 为什么我们要关心这个问题？这意味着我们可以无条件地重复调用 next!

let mut list = List::new();
list.push(1); list.push(2); list.push(3);

let mut iter = list.iter();
let x = iter.next().unwrap();
let y = iter.next().unwrap();
let z = iter.next().unwrap();

对于共享引用来说，这绝对是好的，因为整个要点就是你可以同时拥有大量的引用。然而可变引用不能共存。关键就是它们是排他性的。

最终的结果是，使用安全代码编写IterMut明显更难了（我们还没有讨论到这意味着什么……）。令人惊奇的是，IterMut实际上可以完全安全地实现许多结构！我们将从以下几个方面入手。

我们先把Iter代码改成可变的：

pub struct IterMut<'a, T> {
  next: Option<&'a mut Node<T>>,
}

impl<T> List<T> {
  pub fn iter_mut(&mut self) -> IterMut<'_, T> {
    IterMut {next: self.head.as_deref_mut()}
  }
}

impl<'a, T> Iterator for IterMut<'a, T> {
  type Item = &'a mut T;

  fn next(&mut self) -> Option<Self::Item> {
    self.next.map(|node| {
      self.next = node.next.as_deref_mut();
      &mut node.elem
    })
  }
}

> cargo build
error[E0596]: cannot borrow `self.head` as mutable, as it is behind a `&` reference
  --> src/second.rs:95:25
   |
94 |     pub fn iter_mut(&self) -> IterMut<'_, T> {
   |                     ----- help: consider changing this to be a mutable reference: `&mut self`
95 |         IterMut { next: self.head.as_deref_mut() }
   |                         ^^^^^^^^^ `self` is a `&` reference, so the data it refers to cannot be borrowed as mutable

error[E0507]: cannot move out of borrowed content
   --> src/second.rs:103:9
    |
103 |         self.next.map(|node| {
    |         ^^^^^^^^^ cannot move out of borrowed content

好吧，看起来我们这里有两个不同的错误。第一条看起来非常清楚，甚至告诉我们如何修复它！你不能将共享引用升级到可变引用，所以iter_mut需要采用&mut self。

pub fn iter_mut(&mut self) -> IterMut<'_, T> {
    IterMut { next: self.head.as_deref_mut() }
}

那另一个呢？

哎呀! 其实我在上一节写iter impl的时候不小心出了一个错误，我们只是运气好，才成功的!

我们刚刚第一次接触到Copy的魔力。当我们介绍所有权时，我们说当你转移资源后，你将不能再使用它。对于某些类型，这是很有道理的。我们的好朋友Box为我们管理着堆上的分配，我们当然不希望两段代码都认为他们需要释放它的内存。

然而对于其他类型来说，这就是垃圾。整数没有所有权语义，它们只是无意义的数字！这就是为什么整数被标记为Copy的原因。众所周知，Copy类型是可以通过比特复制来完美拷贝的。因此，它们有一个超级能力：当移动时，旧的值仍然可以使用。因此，你甚至可以将Copy类型从一个引用中移出而不需要replace替换！

rust 中的所有数字基元 (i32, u64, bool, f32, char, 等等…) 都是 Copy。你也可以声明任何用户定义的类型也是Copy，只要它的所有组件都是Copy。

关键是为什么这段代码能用，共享引用也是Copy! 因为&是Copy，Option<&>也是Copy。所以当我们做self.next.map的时候，因为Option只是被Copy了，所以很正常。现在我们不能这样做，因为&mut不是Copy（如果你复制了一个&mut，你就会有两个&mut到内存的同一个位置，这是禁止的）。相反，我们应该正确地对Option应用take来获取它。

fn next(&mut self) -> Option<Self::Item> {
    self.next.take().map(|node| {
        self.next = node.next.as_deref_mut();
        &mut node.elem
    })
}

cargo build

卧槽，IterMut编译通过了！我们来测试一下：

#[test]
fn iter_mut() {
  let mut list = List::new();
  list.push(1); list.push(2); list.push(3);

  let mut iter = list.iter_mut();
  assert_eq!(iter.next(), Some(&mut 3));
  assert_eq!(iter.next(), Some(&mut 2));
  assert_eq!(iter.next(), Some(&mut 1));
}

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 6 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::iter_mut ... ok
test second::test::into_iter ... ok
test second::test::iter ... ok
test second::test::peek ... ok

test result: ok. 7 passed; 0 failed; 0 ignored; 0 measured

它正常工作了，卧槽，为什么？

我们刚刚实现了一段代码，它接收了一个单链的列表，并返回一个列表中的每一个元素的可变的引用（最多一次）。而且它是经过静态验证的，所以是完全安全的。

如果你问我的话，这是个大问题。这有几个原因：

我们对Option<&mut>使用了take，所以我们有专属的访问权来获取可变的引用。不需要担心有人再看它
Rust明白，把一个可变引用共享到指向结构的子字段中是可以的，因为没有办法 “往上走”，而且它们肯定是不相干的

事实证明，你也可以应用这个基本逻辑来为一个数组或一棵树获得一个安全的IterMut! 你甚至可以把迭代器做成DoubleEnded，这样你就可以从前面和后面同时消耗迭代器了! 哇!

pub struct IterMut<'a, T>(Option<&'a mut Node<T>>);

impl<'a, T> List<T> {
    pub fn iter_mut(&'a mut self) -> IterMut<'a, T> {
        IterMut(self.head.as_deref_mut().map(|node| node))
    }
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.take().map(|node| {
            self.0 = node.next.as_deref_mut();
            &mut node.elem
        })
    }
}

4 一个持久的单链栈

好了，我们已经掌握了可变单链栈的技巧。

让我们通过编写一个持久不变的单链列表，从单一所有权转向共享所有权。这将是函数式程序员所熟悉和喜爱的列表。你可以得到头或者尾巴，把一个链表的头放在另一个链表的尾巴上……基本上就是这样。

在这个过程中，我们大体上只会熟悉Rc和Arc，但这将为下一个改变游戏的列表做准备。

让我们添加一个新的文件，叫做third.rs。

pub mod frist;
pub mod second;
pub mod third;

4.1 Layout

好了，回到布局的画板上。

关于持久化列表最重要的一点是，你基本上可以无代价的操作列表的尾部。

比如说，在持久化列表中，这是一个常见的工作量：

list1 = A -> B -> C -> D
list2 = tail(list1) = B -> C -> D
list3 = push(list2, X) = X -> B -> C -> D

但在最后，我们希望内存是这样的：

list1 -> A ---+
              |
              v
list2 ------> B -> C -> D
              ^
              |
list3 -> X ---+

Boxes不能达到这个效果，因为B的所有权是共享的。谁应该释放它？如果我删除list2，会释放B吗？如果使用了Boxes的话，意味着我们希望如此。

函数式语言–实际上几乎所有其他语言–都可以通过使用垃圾回收来解决这个问题。有了垃圾收集的魔力，B只有在每个人都停止查询它之后才会被释放。万岁！

Rust没有任何类似于这些语言的垃圾收集器。他们有跟踪GC，它会在运行时挖出所有的内存，并自动找出哪些是垃圾。相反，Rust今天所拥有的是引用计数。引用计数可以被认为是一个非常简单的GC。对于许多工作应用来说，它的消耗明显低于跟踪收集器，如果你设法建立周期，消耗量可以忽略不计。但是，嘿，这就是我们的全部了! 值得庆幸的是，对于我们的案例来说，我们永远不会遇到周期问题（你可以试着自己证明这一点–我肯定不会）。

那么我们如何进行引用计数的垃圾收集呢？Rc! Rc就像Box一样，但我们可以复制它，只有当所有由它派生的Rc被析构时，它的内存才会被释放。不幸的是，这种灵活性付出了严重的代价：我们只能对它的内部进行共享引用。这意味着我们无法真正从其中任一个列表中取出数据，也无法对它们进行修改。

那么我们的布局会是什么样子呢？嗯，之前我们有：

pub struct List<T> {
  head: Link<T>,
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
  elem: T,
  next: Link<T>,
} 

我们能只把Box改为Rc吗？

// in thrid.rs 
use std::rc::Rc;

pub struct List<T> {
  head: Link<T>,
}
type Link<T> = Option<Rc<Node<T>>>;
struct Node<T> {
  elem: T,
  next: Link<T>,
}

cargo build

warning: field is never used: `head`
 --> src/third.rs:4:5
  |
4 |     head: Link<T>,
  |     ^^^^^^^^^^^^^
  |
  = note: #[warn(dead_code)] on by default

warning: field is never used: `elem`
  --> src/third.rs:10:5
   |
10 |     elem: T,
   |     ^^^^^^^

warning: field is never used: `next`
  --> src/third.rs:11:5
   |
11 |     next: Link<T>,
   |     ^^^^^^^^^^^^^

似乎是合法的。Rust继续是完全琐碎的写作。我敢打赌，我们可以用Rc找到并替换Box，然后就可以了。

4.2. Basics

我们现在已经知道了很多Rust的基础知识，所以我们可以再做很多简单的事情。

对于构造函数，我们又可以直接复制粘贴。

impl<T> List<T> {
  pub fn new() -> Self {
    List {head: None}
  }
}

push和pop已经没有意义了。相反，我们可以提供append和tail，它们提供的东西大致相同。

让我们从append开始。它接收一个list和一个元素，然后返回一个List。就像可变 list 的情况一样，我们要做一个新的节点，它的下一个值是旧的 list。唯一新奇的是如何获得下一个值，因为我们不允许改变任何东西。

我们祈祷的答案就是Clone特性。Clone 几乎被每个类型都实现了，它提供了一种通用的方法来获取 “另一个像这个一样的”，它只给定一个共享引用，在逻辑上是不相干的。它就像C++中的复制构造函数，但它从来没有被隐式调用。

特别是Rc使用Clone作为增量引用数的方式。所以，我们不是把一个Box移到子列表中，而是直接克隆旧列表的头部。我们甚至不需要在头部进行匹配，因为Option暴露了一个Clone实现，它完全可以完成我们想要的事情。

好吧，让我们试试看:

pub fn append(&self, elem: T) -> List<T> {
  List {head: Some(Rc::new(Node {
    elem,
    next: self.head.clone(),
  }))}
}

> cargo build
warning: field is never used: `elem`
  --> src/third.rs:10:5
   |
10 |     elem: T,
   |     ^^^^^^^
   |
   = note: #[warn(dead_code)] on by default

warning: field is never used: `next`
  --> src/third.rs:11:5
   |
11 |     next: Link<T>,
   |     ^^^^^^^^^^^^^

哇，Rust对实际使用字段的态度真的很精明。它告诉我们，没有消费者能够真正观察到这些字段的使用情况! 不过，我们目前看来还是不错的。

tail是这个操作的逻辑反转。它接收一个列表，然后返回整个列表，并删除第一个元素。所有这些都是克隆列表中的第二个元素（如果它存在的话）。让我们试试这个。

pub fn tail(&self) -> List<T> {
  List { head: self.head.as_ref().map(|node| node.next.clone()) }
}

> cargo build
error[E0308]: mismatched types
  --> src/third.rs:27:22
   |
27 |         List { head: self.head.as_ref().map(|node| node.next.clone()) }
   |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `std::rc::Rc`, found enum `std::option::Option`
   |
   = note: expected type `std::option::Option<std::rc::Rc<_>>`
              found type `std::option::Option<std::option::Option<std::rc::Rc<_>>>`

Hrm, 我们搞砸了。map期望我们返回一个Y，但这里我们返回的是Option<Y>。幸运的是，这是另一种常见的Option模式，我们可以使用and_then让我们返回一个Option。

pub fn tail(&self) -> List<T> {
  List {head: self.head.as_ref().and_then(|node| node.next.clone()) }
}

> cargo build

好极了！

现在我们有了tail，我们应该提供head，它返回对第一个元素的引用。这只是从可变列表中peek查看到的：

pub fn head(&self) -> Option<&T> {
  self.head.as_ref().map(|node| &node.elem)
}

漂亮！

这样的功能已经足够我们测试了：

#[cfg(test)]
mod test {
  use super::List;
  #[test]
  fn baiscs() {
    let list = List::new();
    assert_eq!(list.head(), None);
    
    let list = list.append(1).append(2).append(3);
    assert_eq!(list.head(), Some(&3));
    
    let list = list.tail();
    assert_eq!(list.head(), Some(&2));
    
    let list = list.tail();
    assert_eq!(list.head(), Some(&1));
    
    let list = list.tail();
    assert_eq!(list.head(), None);
    
    // 确认空链表tail也工作
    let list = list.tail();
    assert_eq!(list.head(), None);
  }
}

> cargo test
     Running target/debug/lists-5c71138492ad4b4a

running 5 tests
test first::test::basics ... ok
test second::test::into_iter ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test third::test::basics ... ok

test result: ok. 5 passed; 0 failed; 0 ignored; 0 measured

完美!

Iter也与我们的可变列表相同：

pub struct Iter<'a, T> {
  next: Option<&'a Node<T>>,
}

impl<T> List<T> {
  pub fn iter(&self) -> Iter<'_, T> {
    Iter { next: self.head.as_deref() }
  }
}

impl<'a, T> Iterator for Iter<'a, T> {
  type Item = &'a T;
  fn next(&mut self) -> Option<Self::Item> {
    self.next.map(|node| {
      self.next = node.next.as_deref();
      &node.elem
    })
  }
}

#[test]
fn iter() {
	let list = List::new().append(1).append(2).append(3);
	
	let mut iter = list.iter();
	assert_eq!(iter.next(), Some(&3));
	assert_eq!(iter.next(), Some(&2));
	assert_eq!(iter.next(), Some(&1));
}

cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 7 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test second::test::into_iter ... ok
test second::test::peek ... ok
test third::test::basics ... ok
test third::test::iter ... ok

test result: ok. 6 passed; 0 failed; 0 ignored; 0 measured

谁说过动态类型更容易?

注意，我们不能为这种类型实现IntoIter或IterMut。我们只能对元素进行共享访问。

4.3. Drop

和可变列表一样，我们也有一个递归的析构器问题。诚然，对于不可变列表来说，这并不是一个很糟糕的问题：如果我们曾经在某个地方碰到过另一个列表的头的节点，我们不会递归地放弃它。然而这仍然是一个我们应该关心的事情，如何处理并不是那么清楚。我们之前是这样解决的。

impl<T> Drop for List<T> {
  fn drop(&mut self) {
    let mut cur_link = self.head.take();
    while let Some(mut boxed_node) = cur_link {
      cur_link = boxed_node.next.take();
    }
  }
}

问题是loop中

cur_link = boxed_node.next.take();

这是在Box里面修改Node，但是我们不能用Rc来做，它只给我们共享的访问权，因为任意数量的其他Rc都可能指向它。

但是如果我们知道我们是最后一个知道这个节点的列表，其实把Node移出Rc就可以了。然后我们也可以知道什么时候停止：每当我们不能把Node提取出来的时候。

而你看，Rc有一个方法正是这样做的：try_unwrap：

impl<T> Drop for List<T> {
  fn drop(&mut self) {
    let mut head = self.head.take();
    while let Some(node) = head {
      if let Ok(mut node) = Rc::try_unwrap(node) {
        head = node.next.take();
      } else {
        break;
      }
    }
  }
}

> cargo test
   Compiling lists v0.1.0 (/Users/ABeingessner/dev/too-many-lists/lists)
    Finished dev [unoptimized + debuginfo] target(s) in 1.10s
     Running /Users/ABeingessner/dev/too-many-lists/lists/target/debug/deps/lists-86544f1d97438f1f

running 8 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::into_iter ... ok
test second::test::iter ... ok
test second::test::iter_mut ... ok
test second::test::peek ... ok
test third::test::basics ... ok
test third::test::iter ... ok

test result: ok. 8 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

好极了，干得漂亮！

4.4. Arc

使用不可变链表的一个原因是为了跨线程共享数据。毕竟共享的可变状态是万恶之源，解决这个问题的一个方法就是永远杀死可变部分。

只是我们的列表根本不是线程安全的。为了做到线程安全，我们需要原子地摆弄引用计数。否则，两个线程可能会尝试递增引用计数，而只有一个会发生。那么列表可能会过早地被释放!

为了获得线程安全，我们必须使用Arc。Arc与Rc完全相同，只是引用计数是原子化修改的。如果你不需要的话，这有一点开销，所以Rust暴露了这两个功能。我们需要做的就是把每一个对 Rc的引用替换为 std::sync::Arc。就是这样。我们的线程安全了。

但这提出了一个有趣的问题：我们如何知道一个类型是否是线程安全的？我们会不会不小心搞砸了？

不！在 Rust 中，你不能搞砸线程安全。

之所以如此，是因为Rust用两个特性以一流的方式来模拟线程安全。Send和Sync.

如果一个类型可以安全地移动到另一个线程，那么它就是Send。如果一个类型在多个线程之间共享是安全的，那么它就是Sync。也就是说，如果T是Sync，&T就是Send。在这种情况下，安全意味着不可能引起数据竞争，（不要误解为更一般的竞争条件问题）。

这些都是标记性特征，这是一种花哨的说法，它们是完全不提供接口的特征。你要么是发送，要么不是。这只是一个其他API可以要求的属性。如果你不是适当的Send，那么静态上就不可能被发送到不同的线程! 很好!

Send和Sync也是根据你是否完全由Send和Sync类型组成而自动派生的特征。这类似于只有由Copy类型构成时才能实现Copy，但如果你是Copy类型，我们就会自动去实现它。

几乎每个类型都是Send和Sync。大多数类型都是Send，因为它们完全拥有自己的数据。大多数类型是Sync，因为跨线程共享数据的唯一方法是把它们放在一个共享引用的后面，这使得它们是不可改变的。

然而，有一些特殊的类型违反了这些属性：那些具有内部可变性的类型。到目前为止，我们只真正地与继承的可变性（也就是外部可变性）进行了交互：一个值的可变性是由它的容器的可变性继承而来的。也就是说，你不能因为你觉得喜欢而随机突变一个不可变值的某个字段。

内部可变性类型违反了这一点：它们让你通过共享引用进行改变。内部可变性有两大类：单元格cells，它只在单线程上下文中工作；以及在多线程上下文中工作的锁locks。由于显而易见的原因，当你能使用单元格cells时，单元格cell开销更小的。还有原子atomics，它是类似锁的原语。

那么这些和Rc和Arc有什么关系呢？好吧，它们都使用内部可变性作为它们的引用计数。更糟糕的是，这个引用计数是在每个实例之间共享的！Rc只是使用一个单元格cell，这意味着它不是线程安全的。Arc使用原子atomic，这意味着它是线程安全的。当然，你不能通过把一个类型放在Arc中就神奇地使它成为线程安全的。Arc只能像其他类型一样派生出线程安全。

我真的真的不想深入讨论原子内存模型或非派生的Send实现的细节。不用说，随着您深入了解Rust的线程安全故事，事情会变得更加复杂。作为一个高级使用者，你真的不需要去思考它。

4.5. Final Code

use std::rc::Rc;

type Link<T> = Option<Rc<Node<T>>>;

pub struct List<T> {
    head: Link<T>,
}

struct Node<T> {
    elem: T,
    next: Link<T>,
}

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None }
    }

    pub fn append(&self, elem: T) -> Self {
        List {
            head: Some(Rc::new(Node {
                elem,
                next: self.head.clone(),
            })),
        }
    }

    pub fn tail(&self) -> Self {
        List {
            head: self.head.as_ref().and_then(|node| node.next.clone()),
        }
    }

    pub fn head(&self) -> Option<&T> {
        self.head.as_deref().map(|node| &node.elem)
    }
}

pub struct IterRef<'a, T>(Option<&'a Node<T>>);

impl<T> List<T> {
    pub fn iter_ref(&self) -> IterRef<'_, T> {
        IterRef(self.head.as_deref())
    }
}

impl<'a, T> Iterator for IterRef<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.map(|node| {
            self.0 = node.next.as_deref();
            &node.elem
        })
    }
}

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut head = self.head.take();
        while let Some(node) = head {
            if let Ok(mut node) = Rc::try_unwrap(node) {
                head = node.next.take();
            } else {
                break;
            }
        }
    }
}

#[cfg(test)]
mod test {
    use super::List;
    #[test]
    fn basics() {
        let list = List::new();
        assert_eq!(list.head(), None);

        let list = list.append(1).append(2).append(3);
        assert_eq!(list.head(), Some(&3));

        let list = list.tail();
        assert_eq!(list.head(), Some(&2));

        let list = list.tail();
        assert_eq!(list.head(), Some(&1));

        let list = list.tail();
        assert_eq!(list.head(), None);
        let list = list.tail();
        assert_eq!(list.head(), None);
    }

    #[test]
    fn iter_ref() {
        let list = List::new().append(1).append(2).append(3);
        let mut iter_ref = list.iter_ref();
        assert_eq!(iter_ref.next(), Some(&3));
        assert_eq!(iter_ref.next(), Some(&2));
        assert_eq!(iter_ref.next(), Some(&1));
    }
}

5. A Bad Safe Deque

现在，我们已经看到了Rc，听说了内部可变，这给了一个有趣的想法…也许我们可以通过Rc实现可变。如果是这样的话，也许我们可以完全安全地实现一个双链表!

在这个过程中，我们将会熟悉内部的可变性，并且可能会艰难地认识到安全并不意味着正确。双链表很难，而且我总是在某个地方犯错误。

让我们添加一个名为fourth.rs的新文件

// in lib.rs

pub mod first;
pub mod second;
pub mod third;
pub mod fourth;

免责声明:这一章基本上证明了这是一个非常糟糕的想法。

5.1. Layout

我们设计的关键是RefCell类型。RefCell的核心是一对方法：

fn borrow(&self) -> Ref<'_, T>;
fn borrow_mut(&self) -> RefMut<'_, T>;

borrow和borrow_mut的规则与&和&mut的规则完全相同：你可以随意调用borrow，但borrow_mut要求排他性。

RefCell并不是静态地强制它们，而是在运行时强制它们。如果你违反了规则，RefCell就会panic，让程序崩溃。为什么它返回这些Ref和RefMut的东西？它们的行为和Rc很像，只是引用而已。他们还会保持RefCell的借用，直到它们超出了范围。我们稍后会讲到。

现在，有了Rc和RefCell，我们可以成为… 一个难以置信的冗长的、可普遍突变的、不能收集周期的垃圾收集语言。Y-yaaaaay……

好了，我们要做双链路。这意味着每个节点都有一个指向上一个节点和下一个节点的指针。同时，List本身也有一个指向第一个节点和最后一个节点的指针。这样我们就可以在列表的两端快速插入和删除。

所以，我们可能想要这样的东西：

use std::rc::Rc;
use std::cell::RefCell;

pub struct List<T> {
  head: Link<T>,
  tail: Link<T>,
}
  
type Link<T> = Option<Rc<RefCell<Node<T>>>>;

struct Node<T> {
  elem: T,
  next: Link<T>,
  prev: Link<T>,
}

5.2. Building

好了，我们先从建立列表开始。这个新系统很直接，new还是很琐碎的，只要把所有字段都None掉就可以了。另外，由于它变得有点笨拙，让我们再使用一个Node构造函数

impl<T> Node<T> {
  fn new(elem: T) -> Rc<RefCell<Self>> {
    Rc::new(RefCell::new(Node {
      elem,
      prev: None,
      next: None,
    }))
  }
}

impl<T> List<T> {
  pub fn new() -> Self {
    List { head: None, tail: None }
  }
}

> cargo build
**一堆死代码警告但已建立成功**

耶!

现在，让我们尝试写push到列表的前面。因为双链表要复杂得多，所以我们需要做更多的工作。单链表操作可以简化为简单的一行操作，而双链表操作则相当复杂。

特别地，我们现在需要特别处理空列表周围的一些边界情况。大多数操作将只触及头部或尾部指针。然而，当切换到空列表或从空列表切换时，我们需要同时编辑这两个列表。

对我们来说，验证我们的方法是否合理的一个简单方法是，我们保持以下不变性：

每个节点都应该有两个指向它的指针
列表中间的每个节点由其前任和后继指向，而两端的节点则由列表本身指向。

让我们试一试吧：

pub fn push_front(&mut self, elem: T) {
  // 新节点需要+2个链接，其他节点都应该是+0
  let new_node = Node::new(elem);
  match self.head.take() {
  	Some(old_head) => {
      //非空列表，需要连接old_head
      old_head.prev = Some(new_head.clone()); // +1 new_head
      new_head.next = Some(old_head);	// +1 old_head
      self.head = Some(new_head);	// +1 new_head, -1 old_head
      // 总计：+2 new_head, +0 old_head -- OK!  
    }
    None => {
      // 空列表，需要设置尾部
      self.tail = Some(new_head.clone());	// +1 new_head
      self.head = Some(new_head);	// +1 new_head
      // 总计：+2 new_head -- OK!
    }
  }
}

> cargo build
error[E0609]: no field `prev` on type `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>`
  --> src/fourth.rs:39:26
   |
39 |                 old_head.prev = Some(new_head.clone()); // +1 new_head
   |                          ^^^^ unknown field

error[E0609]: no field `next` on type `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>`
  --> src/fourth.rs:40:26
   |
40 |                 new_head.next = Some(old_head);         // +1 old_head
   |                          ^^^^ unknown field

好吧。编译器错误。良好的开端。

为什么我们不能访问节点上的prev和next字段?之前我们只有Rc<Node>时，它可以工作。看来RefCell有点碍事了。我们应该查阅一下文档。

具有动态检查借位规则的可变内存位置

有关更多信息，请参阅模块级文档

共享可变容器。Cell<T>和RefCell<T>类型的值可以通过共享引用(即共同的&T类型)发生突变，而大多数Rust类型只能通过唯一引用(&mut T)发生突变。我们说Cell<T>和RefCell<T>提供了“内部突变性”，与典型的Rust类型表现出“继承突变性”相反。

Cell类型有两种:Cell<T>和RefCell<T>。Cell<T>提供了get和set方法，这些方法可以通过一个方法调用来更改内部值。Cell<T>只与实现复制的类型兼容。对于其他类型，必须使用RefCell<T>类型，在突变之前获取写锁。

RefCell<T>使用Rust的生命周期来实现“动态借用”，在这个过程中，人们可以声明对内部值的临时、独占、可变访问。RefCell<T>的借用是在“运行时”被跟踪的，不像Rust的原生引用类型是在编译时完全静态跟踪的。因为RefCell<T>的借用是动态的，所以可以尝试去借用一个已经被可变地借用的值;当这种情况发生时，会导致线程panic。

何时选择内部可变性

比较常见的继承可变性，必须有唯一的访问权限才能改变一个值，是使Rust能够有力地推理指针别名的关键语言元素之一，从而静态地防止崩溃bug。因此，继承的可变性是首选，而内部可变性是最后的手段。由于单元格类型在不允许突变的地方可以实现突变，所以在某些情况下，内部突变可能是合适的，甚至是必须使用的，如：

将继承的可变性根引入共享类型
逻辑不可变方法的实现细节
Clone的可变实现

在共享类型中引入继承变异性根部

共享的智能指针类型，包括Rc<T>和Arc<T>，提供了可以在多方之间克隆和共享的容器。因为包含的值可能是多重别名的，所以它们只能作为共享引用而不是可变引用借来。如果没有单元格，就根本不可能改变共享框中的数据。

在共享指针类型中放置RefCell<T>来重新引入可变性是很常见的

use std::collections::HashMap;
use std::cell::RefCell;
use std::rc::Rc;

fn main() {
    let shared_map: Rc<RefCell<_>> = Rc::new(RefCell::new(HashMap::new()));
    shared_map.borrow_mut().insert("africa", 92388);
    shared_map.borrow_mut().insert("kyoto", 11837);
    shared_map.borrow_mut().insert("piccadilly", 11826);
    shared_map.borrow_mut().insert("marbles", 38);
}

注意，这个例子使用的是Rc<T>，而不是Arc<T>。RefCell<T>用于单线程场景。如果在多线程环境中需要共享的可变性，可以考虑使用Mutex<T>。

嘿，Rust的文档仍然很棒。

我们关心的是以下这一行：

shared_map.borrow_mut().insert("africa", 92388);

尤其是borrow_mut的东西。似乎我们需要显式借用RefCell。 .运算符不会为我们这样做。奇怪, 咱们试试吧：

pub fn push_front(&mut self, elem: T) {
  let new_head = Node::new(elem);
  match self.head.take() {
    Some(old_head) => {
      old_head.borrow_mut().prev = Some(new_head.clone());
      new_head.borrow_mut().next = Some(old_head);
      self.head = Some(new_head);
    }
    None => {
      self.tail = Some(new_head.clone());
      self.head = Some(new_head);
    }
  }
}

> cargo build

warning: field is never used: `elem`
  --> src/fourth.rs:12:5
   |
12 |     elem: T,
   |     ^^^^^^^
   |
   = note: #[warn(dead_code)] on by default

嘿，它构建通过了！ Docs又赢了。

list           new_head          Node             Node             Node
+-------+   +--+--------+--+ +-----------+--+ +-----------+--+ +-----------+-----+
| head <----+  |  prev  |  +----->prev   |  +----> prev   |  +----> prev   |     |
+-------|      +--------+    |  +--------+    |  +--------+    |  +--------+     |
| tail <----+  |  next <-----+  | next <------+  | next <------+  | next   |     |
+-------+   |  +--------+       +--------+       +--------+       +--------+     |
            |  |  elem  |       | elem   |       | elem   |       | elem   |     |
            |  +--------+       +--------+       +--------+       +--------+     |
            |                                                                    |
            |                                                                    |
            +--------------------------------------------------------------------+

list
+-------+      new_head
| head <----+--+--------+     +-------+
+-------|   |  |  prev <----+-+  None |
| tail <----+  +--------|   | +-------+
+-------+      |  next <----+
               +--------+
               |  elem  |
               +--------+

list            new_head            old_head
+-------+   +---+--------+--+   +------------+   +--+-------+
| &head<----+   |  prev  |  +--------> prev  |   |  |  None |
+-------|       +--------+      |   +--------+   |  +-------+
| &tail<----+   |  next <-------+   |  next <----+
+-------+   |   +--------+      |   +--------+
            |   |  elem  |      |   |  elem  |
            |   +--------+      |   +--------+
            |                   |
            +-------------------+

5.3. Breaking

pop_front应该与push_front具有相同的基本逻辑，但必须是向后的。咱们试试吧：

pub fn pop_front(&mut self) -> Option<T> {
	// 需要取出old_head，确保它是 -2
  self.head.take().map(|old_head| {	// -1 old_head
    match old_head.borrow_mut().next.take() {
      Some(new_head) => {	// -1 new_head
        // 非空list
        new_head.borrow_mut().prev.take();	// -1 old
        self.head = Some(new_head);	// +1 new
        // 总计：-2 old, +0 new
      }
      None => {
        // 空list
        self.tail.take();		// -1 old
        // 总计：-2 old, (no new)
      }
    }
    old_head.elem
  })
}

> cargo build

error[E0609]: no field `elem` on type `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>`
  --> src/fourth.rs:64:22
   |
64 |             old_head.elem
   |                      ^^^^ unknown field

确认 RefCells。我猜要再来一次borrow_mut …

pub fn pop_front(&mut self) -> Option<T> {
	self.head.take().map(|old_head|{
    match old_head.borrow_mut().next.take() {
      Some(new_head) => {
        new_head.borrow_mut().prev.take();
        self.head = Some(new_head);
      }
      None => {
        self.tail.take();
      }
    }
    old_head.borrow_mut().elem
  })
}

cargo build

error[E0507]: cannot move out of borrowed content
  --> src/fourth.rs:64:13
   |
64 |             old_head.borrow_mut().elem
   |   

Hrm… 借用mut只能得到一个&mut Node<T>，但我们不能提出这个节点！

我们需要一些能把RefCell<T>转换成T的东西。让我们看看文档中有没有类似的东西。

fn into_inner(self) -> T

Consumes the RefCell, returning the wrapped value.

这看起来很有希望！

old_head.into_inner().elem

> cargo build

error[E0507]: cannot move out of an `Rc`
  --> src/fourth.rs:64:13
   |
64 |             old_head.into_inner().elem
   |             ^^^^^^^^ cannot move out of an `Rc`

啊,见鬼。into_inner想要将RefCell移出，但我们不能，因为它在Rc中。正如我们在前一章中看到的，Rc<T>只允许我们获得对其内部的共享引用。这是有道理的，因为这就是引用计数指针的全部意义：它们是共享的!

当我们想要为引用计数列表实现Drop时，这是一个问题，解决方案是相同的:Rc::try_unwrap，它将一个Rc的内容移出，如果它的refcount是1。

Rc::try_unwrap(old_head).unwrap().into_inner().elem

Rc::unwrap返回一个Result<T, Rc<T>>。Result基本上是一个通用Option，其中None情况下有相关的数据。在本例中，您试图展开的Rc。因为我们不关心它失败的情况(如果我们正确地编写了程序，它必须成功)，所以我们只对它调用unwrap。

无论如何，让我们看看接下来我们会遇到什么编译错误(让我们面对它，肯定会有一个)。

> cargo build

error[E0599]: no method named `unwrap` found for type `std::result::Result<std::cell::RefCell<fourth::Node<T>>, std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>>` in the current scope
  --> src/fourth.rs:64:38
   |
64 |             Rc::try_unwrap(old_head).unwrap().into_inner().elem
   |                                      ^^^^^^
   |
   = note: the method `unwrap` exists but the following trait bounds were not satisfied:
           `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>> : std::fmt::Debug`

啊。为Result进行unwrap解包要求可以调试打印错误情况。RefCell<T>仅在T实现Debug时才实现。Node没有实现调试。

我们不这样做，而是通过ok将Result转换为Option来解决这个问题：

Rc::try_unwrap(old_head).ok().unwrap().into_inner().elem

cargo build

是的。我们成功了。

我们实现了push和pop。

list.head = None, list.tail = None

list
+-------+      
| head <----+--+-------+
+-------|   |  +  None |
| tail <----+| +-------+
+-------+

list有一个链表

list
+-------+      new_head
| head <----+--+--------+     +-------+
+-------|   |  |  prev <----+-+  None |
| tail <----+  +--------|   | +-------+
+-------+      |  next <----+
               +--------+
               |  elem  |
               +--------+

list有多个链表

            +-------------------+
list        |   old_head        |   new_head
+-------+   |   +--------+      +---+--------+   +--+-------+
| &head<----+   |  prev  |      |   |  prev  |   |  |  None |
+-------|       +--------+      |   +--------+   |  +-------+
| &tail<----+   |  next  |      |   |  next <----+
+-------+   |   +--------+      |   +--------+
            |   |  elem  |      |   |  elem  |
            |   +--------+      |   +--------+
            +-------------------+

让我们通过旧的stack basic来进行测试(因为这是我们到目前为止所实现的所有内容)

#[cfg(test)]
mod test {
	use super::List;
  
  #[test]
  fn baiscs() {
        let mut list = List::new();

        // Check empty list behaves right
        assert_eq!(list.pop_front(), None);

        // Populate list
        list.push_front(1);
        list.push_front(2);
        list.push_front(3);

        // Check normal removal
        assert_eq!(list.pop_front(), Some(3));
        assert_eq!(list.pop_front(), Some(2));

        // Push some more just to make sure nothing's corrupted
        list.push_front(4);
        list.push_front(5);

        // Check normal removal
        assert_eq!(list.pop_front(), Some(5));
        assert_eq!(list.pop_front(), Some(4));

        // Check exhaustion
        assert_eq!(list.pop_front(), Some(1));
        assert_eq!(list.pop_front(), None);
  }
}

现在我们可以正确地从列表中删除东西，我们可以实现Drop。这一次Drop在概念上更有趣一些。以前我们费心为栈实现Drop只是为了避免无限递归，现在我们需要实现Drop来让任何事情发生。

Rc不能处理循环。如果有一个循环，所有的东西都会让其他的东西保活。事实证明，一个双链表只是一个由小循环组成的大链!因此，当我们删除我们的列表，两个末端节点的refcounts会被减为1.…然后什么也不会发生。好吧，如果我们的列表只包含一个节点，我们就可以了。但理想情况下，如果一个列表包含多个元素，它也应该正常工作。也许这只是我的想法。

正如我们所看到的，删除元素有点痛苦。所以最简单的方法就是一直弹出直到没有:

impl<T> Drop for List<T> {
  fn drop(&mut self) {
    while self.pop_front().is_some() {}
  }
}

(我们其实可以使用可变堆栈来实现这一点，但捷径是为那些理解事物的人准备的!)

我们可以看看push和pop的反向版本的实现，但它们只是复制-粘贴作业，我们将在本章后面讨论。现在让我们看看更有趣的东西

5.4. Peek

好了，我们通过了push和pop。不瞒你说，我当时有点激动。编译时的正确性是一种致命的毒药。

让我们做一些简单的事情来冷静一下:让我们先实现peek_front。

list            new_head            old_head
+-------+   +---+--------+--+   +------------+   +--+-------+
| &head<----+   |  prev  |  +--------> prev  |   |  |  None |
+-------|       +--------+      |   +--------+   |  +-------+
| &tail<----+   |  next <-------+   |  next <----+
+-------+   |   +--------+      |   +--------+
            |   |  elem  |      |   |  elem  |
            |   +--------+      |   +--------+
            +-------------------+

这在以前总是很容易的。还是很简单，对吧

事实上，我想我可以直接复制粘贴

pub fn peek_front(&self) -> Option<&T> {
  self.head.as_ref().map(|node| &node.elem)
}

等一下。这次不是

pub fn peek_front(&self) -> Option<&T> {
  self.head.as_ref().map(|node| {
    // borrow!!!
    &node.borrow().elem
  })
}

> cargo build

error[E0515]: 不能返回引用临时值的值
  --> src/fourth.rs:66:13
   |
66 |             &node.borrow().elem
   |             ^   ----------^^^^^
   |             |   |
   |             |   这里创建的临时值
   |             |
   |             返回一个引用当前函数所拥有的数据的值

这与我们的单链表完全相同。为什么事情会不同。为什么。

答案就是这一章的全部寓意:RefCell让一切都悲伤。到目前为止，RefCell一直是个讨厌的东西。现在他们将成为一场噩梦。

那么到底发生了什么呢?要理解这一点，我们需要回到borrow的定义

fn borrow<'a>(&'a self) -> Ref<'a, T>
fn borrow_mut<'a>(&'a self) -> RefMut<'a, T>

在layout节我们说：

RefCell并不是静态地强制它们，而是在运行时强制它们。如果你违反了规则，RefCell就会panic，让程序崩溃。为什么它返回这些Ref和RefMut的东西?它们的行为和Rc很像，只是借用而已。而且他们会一直借用RefCell直到他们超出了范围。

我们稍后会讲到

现在就是稍后

Ref和RefMut分别实现了Deref和DerefMut，所以对于大多数意图和目的来说，它们的行为与&T和&mut T完全相同。然而，由于这些特性的工作方式，返回的引用与Ref的生命期有关，而不是实际的RefCell。这就意味着，只要我们把引用留在身边，Ref就必须一直存在。

事实上，这对于正确性来说是必要的。当一个Ref被丢弃时，它会告诉RefCell它不再被借用了。因此，如果我们确实设法保持我们的引用比 Ref 存在的时间更长，我们可以在引用还在运行的时候得到一个 RefMut，并完全将Rust的类型系统破坏了一半。

那么我们现在的情况是什么呢？我们只想返回一个引用，但我们需要把Ref这个东西留在身边。但只要我们从peek中返回引用，函数就结束了，而Ref就超出了作用域。

😖

据我所知，我们在这里完全是死水一潭。您不能像那样完全封装RefCells的使用。但是…如果我们放弃完全隐藏实现细节呢?如果我们返回Ref？

pub fn peek_front(&self) -> Option<Ref<T>> {
  self.head.as_ref().map(|node| node.borrow())
}

> cargo build

error[E0412]: cannot find type `Ref` in this scope
  --> src/fourth.rs:63:40
   |
63 |     pub fn peek_front(&self) -> Option<Ref<T>> {
   |                                        ^^^ not found in this scope
help: possible candidates are found in other modules, you can import them into scope
   |
1  | use core::cell::Ref;
   |
1  | use std::cell::Ref;
   |

必须导入一些东西

use std::cell::{Ref, RefCell};

> cargo build

error[E0308]: mismatched types
  --> src/fourth.rs:64:9
   |
64 | /         self.head.as_ref().map(|node| {
65 | |             node.borrow()
66 | |         })
   | |__________^ expected type parameter, found struct `fourth::Node`
   |
   = note: expected type `std::option::Option<std::cell::Ref<'_, T>>`
              found type `std::option::Option<std::cell::Ref<'_, fourth::Node<T>>>`

嗯…这是正确的。我们有一个Ref<Node<T>>，但是我们想要一个Ref<T>。我们可以放弃所有封装的希望，直接返回这个。我们还可以让事情变得更加复杂，将Ref<Node<T>>包装为新的类型，只公开对&T的访问。

这两种选择都有点蹩脚。

相反，我们要深入下去。让我们找点乐子。我们的乐趣来源就是这个野兽

map<U, F>(orig: Ref<'b, T>, f: F) -> Ref<'b, U>
	where F: FnOnce(&T) -> &U,
				U: ?Sized

为借来的数据的一个组件创建一个新的Ref。

是的:就像你可以在一个Option上进行map映射一样，你可以也映射一个Ref。

我肯定有人在某处真的很兴奋，因为单子或任何东西，但我不关心任何这些。我也不认为这是一个适当的单子，因为没有类似的情况，但我离题了。

这很酷，这对我来说才是最重要的。我需要这个：

pub fn peek_front(&self) -> Option<Ref<T>> {
  self.head.as_ref().map(|node|{
    Ref::map(node.borrow(), |node| &node.elem)
  })
}

> cargo build

让我们通过从堆栈中添加测试来确保这是有效的。我们需要做些调整来处理Ref并未实现比较这一事实。

#[test]
fn peek() {
	let mut list = List::new();
  assert!(list.peek_front().is_none());
  list.push_front(1);
  list.push_front(2);
  list.push_front(3);
  
  assert_eq!(&*list.peek_front().unwrap(), &3);
}

5.5. Symmetric Cases

好了，让我们把组合对称现实

list
+-------+          +-------+
| &head<-----+------| None |
+-------|    |     +-------+
| &tail<-----+
+-------+

list
+-------+   +---+--------+--+   +------------+   +--+-------+
| &head<----+   |  prev  |  +--------> prev  |   |  |  None |
+-------|       +--------+      |   +--------+   |  +-------+
| &tail<----+   |  next <-------+   |  next <----+
+-------+   |   +--------+      |   +--------+
            |   |  elem  |      |   |  elem  |
            |   +--------+      |   +--------+
            +-------------------+

我们只需要做一些基本的文本替换

tail <-> head
next <-> prev
front -> back

哦，我们还需要添加_mut变体以进行peek查询

pub fn push_back(&mut self, elem: T) {
  let new_tail = Node::new(elem);
  match self.tail.take() {
    Some(old_tail) => {
      old_tail.borrow_mut().next = Some(new_tail.clone());
      new_tail.borrow_mut().prev = Some(old_tail);
      self.tail = Some(new_tail);
    }
    None => {
      self.head = Some(new_tail.clone());
      self.tail = Some(new_tail);
    }
  }
}

pub fn pop_back(&mut self) -> Option<T> {
  self.tail.take().map(|old_tail| {
    match old_tail.borrow_mut().prev.take() {
      Some(new_tail) => {
        new_tail.borrow_mut().next.take();
        self.tail = Some(new_tail);
      }
    	None => {
        self.head.take();
      }      
    }
    Rc::try_unwrap(old_tail).ok().unwrap().into_inner().elem
  })
}

pub fn peek_back(&self) -> Option<Ref<T>> {
  self.tail.as_ref().map(|node| {
    Ref::map(node.borrow(), |node| &node.elem)
  })
}

pub fn peek_back_mut(&mut self) -> Option<RefMut<T>> {
  self.tail.as_ref().map(|node|{
    RefMut::map(node.borrow_mut(), |node| &mut node.elem)
  })
}

pub fn peek_front_mut(&mut self) -> Option<RefMut<T>> {
  self.head.as_ref().map(|node|{
    RefMut::map(node.borrow_mut(), |node| &mut node.elem)
  })
}

大量充实我们的测试

#[cfg(test)]
mod test {
    use super::List;
    #[test]
    fn basics() {
        let mut list = List::new();
        assert_eq!(list.pop_front(), None);

        list.push_front(1);
        list.push_front(2);
        list.push_front(3);

        assert_eq!(list.pop_front(), Some(3));
        assert_eq!(list.pop_front(), Some(2));

        list.push_front(4);
        list.push_front(5);

        assert_eq!(list.pop_front(), Some(5));
        assert_eq!(list.pop_front(), Some(4));

        assert_eq!(list.pop_front(), Some(1));
        assert_eq!(list.pop_front(), None);

        // ----- back ------
        assert_eq!(list.pop_back(), None);

        list.push_back(1);
        list.push_back(2);
        list.push_back(3);

        assert_eq!(list.pop_back(), Some(3));
        assert_eq!(list.pop_back(), Some(2));

        list.push_back(4);
        list.push_back(5);

        assert_eq!(list.pop_back(), Some(5));
        assert_eq!(list.pop_back(), Some(4));
        assert_eq!(list.pop_back(), Some(1));
        assert_eq!(list.pop_back(), None);
    }

    #[test]
    fn peek() {
        let mut list = List::new();
        assert!(list.peek_front().is_none());
        assert!(list.peek_back().is_none());
        assert!(list.peek_front_mut().is_none());
        assert!(list.peek_back_mut().is_none());

        list.push_front(1);
        list.push_front(2);
        list.push_front(3);

        assert_eq!(&*list.peek_front().unwrap(), &3);
        assert_eq!(&mut *list.peek_front_mut().unwrap(), &mut 3);
        assert_eq!(&*list.peek_back().unwrap(), &1);
        assert_eq!(&mut *list.peek_back_mut().unwrap(), &mut 1);
    }
}

还有没有一些情况下我们没有测试？大概有。

组合空间确实在这里爆炸了。

我们的代码至少没有明显的错误。

> cargo test

好了。复制粘贴是最好的编程方式。

5.6. Iteration

像往常一样，IntoIter将是最简单的。只需要包装栈并调用pop

pub struct IntoIter<T>(List<T>);

impl<T> List<T> {
  pub fn into_iter(self) -> IntoIter<T> {
    IntoIter(self)
  }
}

impl<T> Iterator for IntoIter<T> {
  type Item = T;
  fn next(&mut self) -> Option<T> {
    self.0.pop_front()
  }
}

但我们有了一个有趣的新发展。在此之前，我们的列表只有一个“自然”迭代顺序，而Deque本质上是双向的。从前到后有什么特别之处?如果有人想要在另一个方向迭代该怎么办？

对于这个问题，Rust实际上有一个答案:DoubleEndedIterator 。DoubleEndedIterator 继承自Iterator(意味着所有DoubleEndedIterator 都是迭代器)，并且需要一个新方法:next_back。它与next具有完全相同的签名，但它应该从另一端产生元素。DoubleEndedIterator的语义对我们来说非常方便:迭代器变成了deque容器。您可以从前面和后面使用元素，直到两端收敛，此时迭代器为空。

就像Iterator和next一样，事实证明next_back并不是DoubleEndedIterator的用户真正关心的东西。相反，这个接口最好的地方在于它公开了rev方法，它将迭代器包装起来，生成一个新迭代器，以相反的顺序生成元素。它的语义相当直接:在反向迭代器上调用next就是调用next_back。

因为我们已经是deque了，提供这个API很容易：

impl<T> DoubleEndedIterator for IntoIter<T> {
  fn next_back(&mut self) -> Option<T> {
    self.0.pop_back()
  }
}

我们来测试一下：

#[test]
fn into_iter() {
  let mut list = List::new();
  list.push_front(1); list.push_front(2); list.push_front(3);
  
  let mut iter = list.into_iter();
  assert_eq!(iter.next(), Some(3));
  assert_eq!(iter.next_back(), Some(1));
  assert_eq!(iter.next(), Some(2));
  assert_eq!(iter.next_back(), None);
  assert_eq!(iter.next(), None);
}

> cargo test

好极了！

Iter

Iter就不那么宽容了。我们又得应付那些可怕的Ref了！由于引用Refs，我们不能像以前那样存储&Node。相反，让我们尝试存储Ref<Node>s：

pub struct Iter<'a T>(Option<Ref<'a, Node<T>>>);

impl<T> List<T> {
  pub fn iter(&self) -> Iter<T> {
    Iter(self.head.as_deref().map(|node| node.borrow()))
  }
}

到目前为止，一切都好。实现next会有点麻烦，但我认为它与旧堆栈IterMut的基本逻辑相同，但有额外的RefCell疯狂：

impl<'a, T> Iterator for Iter<'a, T> {
  type Item = Ref<'a, T>;
  fn next(&mut self) -> Option<Self::Item> {
    self.0.take().map(|node_ref: Ref<Node<T>> |{
      self.0 = node_ref.next: Option<Rc<RefCell<Node<T>>>>
               .as_ref(): Option<&Rc<RefCell<Node<T>>>>
               .map(|head: &Rc<RefCell<Node<T>>>| head: &Rc<RefCell<Node<T>>>
                    .borrow(): Ref<Node<T>>);
      Ref::map(node_ref, |node| &node.elem)
    })
  }
}

cargo build

error[E0521]: 借用的数据逃逸到闭包之外
   --> src/fourth.rs:155:13
    |
153 |     fn next(&mut self) -> Option<Self::Item> {
    |             --------- `self` 是在这里声明的，在闭包体之外
154 |         self.0.take().map(|node_ref| {
155 |             self.0 = node_ref.next.as_ref().map(|head| head.borrow());
    |             ^^^^^^   -------- 借用仅在闭包体中有效
    |             |
    |             对' node ref '的引用在这里逃逸出了闭包体

error[E0505]: 无法移出' node_ref '，因为它是借来的
   --> src/fourth.rs:156:22
    |
153 |     fn next(&mut self) -> Option<Self::Item> {
    |             --------- 生命期参数 “'1” 出现在 “self” 的类型中
154 |         self.0.take().map(|node_ref| {
155 |             self.0 = node_ref.next.as_ref().map(|head| head.borrow());
    |             ------   -------- 这里出现`node_ref`的借用
    |             |
    |             赋值要求 "node_ref "为"’1"借用
156 |             Ref::map(node_ref, |node| &node.elem)
    |                      ^^^^^^^^ 移出`node_ref`发生在这里

该死

node_ref的寿命不够长。不像一般的引用，Rust不允许我们像那样把引用Refs分开。我们从head.borrow()中得到的Ref只允许存在与node_ref相同的时间，但是我们最终在Ref::map调用中丢弃了它。

巧合的是，在我写这个的时候，我们想要的函数实际上两天前就稳定下来了。这意味着它还需要几个月的时间才能发布稳定版。因此，让我们继续使用最新的夜间构建：

pub fn map_split<U, V, F>(orig: Ref<'b, T>, f: F) -> (Ref<'b, U>, Ref<'b, V>) where
	F: FnOnce(&T) -> (&U, &V),
	U: ?Sized,
	V: ?Sized,

Woof，让我们试一试……

fn next(&mut self) -> Option<Self::Item> {
  self.0.take().map(|node_ref: Ref<Node<T>>| {
    let (next: Ref<Option<Rc<Ref<Node<T>>>>>, elem: Ref<T>) 
        = Ref::map_split(node_ref, |node: &Node<T>| {
      (&node.next, &node.elem)
    });
    self.0 = next.as_ref(): Option<&Rc<Ref<Node<T>>>>
             .map(|head: &Rc<Ref<Node<T>>>| head.borrow());
    elem
  })
}

cargo build
   Compiling lists v0.1.0 (/Users/ABeingessner/dev/temp/lists)
error[E0521]: borrowed data escapes outside of closure
   --> src/fourth.rs:159:13
    |
153 |     fn next(&mut self) -> Option<Self::Item> {
    |             --------- `self` is declared here, outside of the closure body
...
159 |             self.0 = next.as_ref().map(|head| head.borrow());
    |             ^^^^^^   ---- borrow is only valid in the closure body
    |             |
    |             reference to `next` escapes the closure body here

恩。我们需要再次使用Ref::Map才能使生命期正确。但是 Ref::Map 返回一个Ref，我们需要一个Option<Ref>，但是我们需要遍历Ref才能映射到我们的Option上…

长时间凝视远方

??????

fn next(&mut self) -> Option<Self::Item> {
  self.0.take().map(|node_ref: Ref<Node<T>>| {
    let (next, elem) = Ref::map_split(node_ref, |node| {
      (&node.next, &node.elem)
    });
    self.0 = if next.is_some() {
      Some(Ref::map(next: Ref<Option<Rc<RefCell<Node<T>>>>>, 
                   |next: &Option<Rc<RefCell<Node<T>>>>| 
            &**next
            .as_ref(): Option<&Rc<RefCell<Node<T>>>>
            .unwrap(): &Rc<RefCell<Node<T>>>
        		// &RefCell<Node<T>>
    ))} else {
      None
    };
    elem
  })
}

error[E0308]: mismatched types
   --> src/fourth.rs:162:22
    |
162 |                 Some(Ref::map(next, |next| &**next.as_ref().unwrap()))
    |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `fourth::Node`, found struct `std::cell::RefCell`
    |
    = note: expected type `std::cell::Ref<'_, fourth::Node<_>>`
               found type `std::cell::Ref<'_, std::cell::RefCell<fourth::Node<_>>>`

哦。对的。有多个重叠的RefCells。我们在列表中走得越深，每个RefCell下的嵌套就越深。例如，我们需要维护一个Refs栈来代表我们所持有的所有未偿还的借用，因为如果我们停止查看某个元素，则需要减少它之前的每个RefCell上的借位计数……

我认为我们在这里无能为力。这是一个死胡同。让我们尝试摆脱RefCell。

那我们的Rcs呢？谁说我们需要存储引用？为什么我们不能仅仅克隆整个Rc来在list中间找到一个很好的拥有者句柄？

pub struct Iter<T>(Option<Rc<Node<T>>>);

impl<T> List<T> {
  pub fn iter(&self) -> Iter<T> {
    Iter(self.head.as_ref().map(|head| head.clone()))
  }
}

impl<T> Iterator for Iter<T> {
  type Item =

嗯…等等，我们现在返回什么？ ＆T？ Ref<T>？

不，这些都没用……我们的Iter再也没有生命周期了!&T和Ref<T>都要求我们在进入next之前预先声明一些生命周期。但是我们从Rc中得到的任何东西都会借用Iterator……头……痛……aaaaaahhhhhh

也许我们可以…map……Rc……得到一个Rc<T>?这是答案吗?Rc的文档中似乎没有这样的内容。实际上有人做了个crate让你可以这么做。

但是，等等，即使我们这样做，也遇到了一个更大的问题：迭代器失效的可怕幽灵。以前，我们完全不受迭代器失效的影响，因为Iter借用了列表list，使其完全不可变。但是，如果我们的Iter产生的是Rcs，那么他们根本不会借用该列表！这意味着人们可以在持有列表中的指针的同时在列表上调用push和pop！

哦，上帝，那会有什么后果？

好吧，pushing其实是可以的。我们的视野已经进入了该列表的某些子范围，并且该列表将增长到超出我们的视线。没什么大不了的。

然而pop是另一回事。如果他们在我们的范围外弹出元素，那应该还是可以的。我们看不到那些节点，所以什么也不会发生。但是，但是如果他们试图弹出我们指向的节点……一切都会崩溃！特别是当他们去unwrap解包try_unwrap的结果时，它实际上将失败，并且整个程序将崩溃。

这其实是非常酷的。我们可以将大量内部自有指针添加到列表中，同时对其进行修改，直到他们试图删除我们指向的节点为止。即使我们没有得到悬空指针或其他东西，程序也肯定会崩溃。

但是在映射Rcs的基础上还要处理迭代器无效的问题，这似乎……很糟糕。 Rc<RefCell>真的让我们失望了。有趣的是，我们经历了持久栈情况的反转。在持久性堆栈努力获取数据所有权但每天都可以获取引用的地方，我们的列表在获得所有权方面没有问题，但却很难借出我们的引用。

虽然公平地说，但我们的大多数努力都围绕着希望隐藏实现细节并拥有一个优雅的API来进行。如果我们只是想到处传递Nodes，我们可以做到一切都很好。

哎呀，我们可以创建多个并发的IterMuts，这些IterMuts在运行时进行了检查，以确保不可变地访问同一元素！

实际上，这种设计更适合于内部数据结构，因为这些数据结构永远不会被API的用户看到。内部可变性对于编写安全的应用程序非常有用。没有比这安全的库了。

总之，我放弃了Iter和IterMut。我们可以做，但是……唉…….

5.7. Final Code

好了，这就是在Rust中实现一个100%安全的双链表。它的实现是个噩梦，泄露了实现细节，而且不支持几个基本操作。

但是，它是存在的。

哦，我猜它也被Rc和RefCell之间大量的“不必要的”运行时检查所困扰。我把不必要的放在引号里，因为它们实际上是必要的，以确保整个是安全的。我们遇到了一些地方，这些检查实际上是必要的。双向链表有一个可怕的混乱的别名和所有权故事。

尽管如此，这也是我们可以做的事情。尤其是当我们不在乎将内部数据结构暴露给用户的时候。

从现在开始，我们将专注于硬币的另一面：通过让我们的实现变得不安全来夺回所有的控制权

#![allow(unused_variables)]
fn main() {
use std::rc::Rc;
use std::cell::{Ref, RefMut, RefCell};

pub struct List<T> {
    head: Link<T>,
    tail: Link<T>,
}

type Link<T> = Option<Rc<RefCell<Node<T>>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
    prev: Link<T>,
}


impl<T> Node<T> {
    fn new(elem: T) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Node {
            elem: elem,
            prev: None,
            next: None,
        }))
    }
}

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None, tail: None }
    }

    pub fn push_front(&mut self, elem: T) {
        let new_head = Node::new(elem);
        match self.head.take() {
            Some(old_head) => {
                old_head.borrow_mut().prev = Some(new_head.clone());
                new_head.borrow_mut().next = Some(old_head);
                self.head = Some(new_head);
            }
            None => {
                self.tail = Some(new_head.clone());
                self.head = Some(new_head);
            }
        }
    }

    pub fn push_back(&mut self, elem: T) {
        let new_tail = Node::new(elem);
        match self.tail.take() {
            Some(old_tail) => {
                old_tail.borrow_mut().next = Some(new_tail.clone());
                new_tail.borrow_mut().prev = Some(old_tail);
                self.tail = Some(new_tail);
            }
            None => {
                self.head = Some(new_tail.clone());
                self.tail = Some(new_tail);
            }
        }
    }

    pub fn pop_back(&mut self) -> Option<T> {
        self.tail.take().map(|old_tail| {
            match old_tail.borrow_mut().prev.take() {
                Some(new_tail) => {
                    new_tail.borrow_mut().next.take();
                    self.tail = Some(new_tail);
                }
                None => {
                    self.head.take();
                }
            }
            Rc::try_unwrap(old_tail).ok().unwrap().into_inner().elem
        })
    }

    pub fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|old_head| {
            match old_head.borrow_mut().next.take() {
                Some(new_head) => {
                    new_head.borrow_mut().prev.take();
                    self.head = Some(new_head);
                }
                None => {
                    self.tail.take();
                }
            }
            Rc::try_unwrap(old_head).ok().unwrap().into_inner().elem
        })
    }

    pub fn peek_front(&self) -> Option<Ref<T>> {
        self.head.as_ref().map(|node| {
            Ref::map(node.borrow(), |node| &node.elem)
        })
    }

    pub fn peek_back(&self) -> Option<Ref<T>> {
        self.tail.as_ref().map(|node| {
            Ref::map(node.borrow(), |node| &node.elem)
        })
    }

    pub fn peek_back_mut(&mut self) -> Option<RefMut<T>> {
        self.tail.as_ref().map(|node| {
            RefMut::map(node.borrow_mut(), |node| &mut node.elem)
        })
    }

    pub fn peek_front_mut(&mut self) -> Option<RefMut<T>> {
        self.head.as_ref().map(|node| {
            RefMut::map(node.borrow_mut(), |node| &mut node.elem)
        })
    }

    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }
}

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        while self.pop_front().is_some() {}
    }
}

pub struct IntoIter<T>(List<T>);

impl<T> Iterator for IntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        self.0.pop_front()
    }
}

impl<T> DoubleEndedIterator for IntoIter<T> {
    fn next_back(&mut self) -> Option<T> {
        self.0.pop_back()
    }
}

#[cfg(test)]
mod test {
    use super::List;

    #[test]
    fn basics() {
        let mut list = List::new();

        // Check empty list behaves right
        assert_eq!(list.pop_front(), None);

        // Populate list
        list.push_front(1);
        list.push_front(2);
        list.push_front(3);

        // Check normal removal
        assert_eq!(list.pop_front(), Some(3));
        assert_eq!(list.pop_front(), Some(2));

        // Push some more just to make sure nothing's corrupted
        list.push_front(4);
        list.push_front(5);

        // Check normal removal
        assert_eq!(list.pop_front(), Some(5));
        assert_eq!(list.pop_front(), Some(4));

        // Check exhaustion
        assert_eq!(list.pop_front(), Some(1));
        assert_eq!(list.pop_front(), None);

        // ---- back -----

        // Check empty list behaves right
        assert_eq!(list.pop_back(), None);

        // Populate list
        list.push_back(1);
        list.push_back(2);
        list.push_back(3);

        // Check normal removal
        assert_eq!(list.pop_back(), Some(3));
        assert_eq!(list.pop_back(), Some(2));

        // Push some more just to make sure nothing's corrupted
        list.push_back(4);
        list.push_back(5);

        // Check normal removal
        assert_eq!(list.pop_back(), Some(5));
        assert_eq!(list.pop_back(), Some(4));

        // Check exhaustion
        assert_eq!(list.pop_back(), Some(1));
        assert_eq!(list.pop_back(), None);
    }

    #[test]
    fn peek() {
        let mut list = List::new();
        assert!(list.peek_front().is_none());
        assert!(list.peek_back().is_none());
        assert!(list.peek_front_mut().is_none());
        assert!(list.peek_back_mut().is_none());

        list.push_front(1); list.push_front(2); list.push_front(3);

        assert_eq!(&*list.peek_front().unwrap(), &3);
        assert_eq!(&mut *list.peek_front_mut().unwrap(), &mut 3);
        assert_eq!(&*list.peek_back().unwrap(), &1);
        assert_eq!(&mut *list.peek_back_mut().unwrap(), &mut 1);
    }

    #[test]
    fn into_iter() {
        let mut list = List::new();
        list.push_front(1); list.push_front(2); list.push_front(3);

        let mut iter = list.into_iter();
        assert_eq!(iter.next(), Some(3));
        assert_eq!(iter.next_back(), Some(1));
        assert_eq!(iter.next(), Some(2));
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
    }
}
}

6. 不安全的单链队列

好吧，引用计数的内部可变性有点失控了。Rust当然不会真的希望你做这种事吧？嗯，是也不是。Rc和Refcell可以很好地处理简单的情况，但它们可能会变得很笨重。特别是当你想隐藏它的发生时。一定有更好的方法！

在这一章中，我们将回到单链表，并实现一个单链路队列，以了解原始指针和Unsafe Rust。

让我们添加一个名为 fifth.rs 的新文件

// in lib.rs

pub mod first;
pub mod second;
pub mod third;
pub mod fourth;
pub mod fifth;

我们的代码主要是由second派生的。因为在链表的世界里，队列基本上是堆栈的扩充。不过，我们还是要从头开始，因为我们还需要解决一些关于布局之类的基本问题。

##6.1. Layout

那么，单链路的队列是什么样的呢？好吧，当我们有一个单链栈时，我们推到列表的一端，然后从同一端弹出。栈和队列的唯一区别是，队列会从另一端弹出。所以从我们的栈实现来看，我们有：

input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

stack push X:
[Some(ptr)] -> (X, Some(ptr)) -> (A, Some(ptr)) -> (B, None)

stack pop:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

为了创建一个队列，我们只需要决定将哪个操作移动到列表的末尾：push，还是pop?由于我们的列表是单链的，我们实际上可以用相同的努力将任意一个操作移动到最后。

要将push移动到末尾，只需一直走到None，并使用新元素将其设置为Some。

input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

flipped push X:
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)

要将pop移至末尾，我们只需要一直走到None之前的节点，然后将其取走：

input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)
  
flipped pop:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

我们可以在今天做完这一切，然后收手，但那会很糟糕! 这两种操作都会走过整个列表。有些人会认为，这样的队列实现确实是一个队列，因为它公开了正确的接口。然而我认为，性能保证也是接口的一部分。我并不关心精确的渐变边界，但在乎“快”与“慢”的区别。队列保证了push和pop是快速的，而遍历整个列表肯定不是快速的。

一个关键的观察是，我们浪费了大量的工作，重复做同样的事情。我们能记住这些工作吗? 为什么，是的！我们可以存储一个指向列表末尾的指针，然后直接跳到那里就可以了!

事实证明，只有push和pop的一种反转才能使用此功能。要反转pop，我们必须将“tail”指针向后移动，但是由于我们的列表是单链链接，因此我们无法有效地做到这一点。如果我们反转push，我们只需要向前移动“head”指针，这很容易。

list
+------+     +------+
| head <---+-+ None |
+------+   | +------+
| tail <---+
+------+

list
+------+   +--+------+   +--+------+
| head <---+  | elem |   |  | elem |
+------+      +------+   |  +------+
| tail <---+  | next <---+  | next |
+------+   |  +------+   |  +------+
           +-------------+

让我们试一试：

use std::mem;

pub struct List<T> {
  head: Link<T>,
  tail: Link<T>, // NEW!
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
  elem: T,
  next: Link<T>,
}

impl<T> List<T> {
  pub fn new() -> Self {
    List { head: None, tail: None }
  }
  
  pub fn push(&mut self, elem: T) {
    let new_tail = Box::new(Node {
      elem,
      // 当您push到tail时，next永远是None
      next: None,
    });
    // 换 old_tail 指向 new_tail
    let old_tail = mem::replace(&mut self.tail, Some(new_tail));
    
    match old_tail {
      Some(mut old_tail) => {
        // 如果 old_tail 存在，更新old_tail指向new_tail
        old_tail.next = Some(new_tail);
      }
      None => {
        // 否则，更新head指向new_tail
        self.head = Some(new_tail);
      }
    }
  }
}

我现在对 impl 的细节讲得比较快，因为我们对这种事情应该很熟悉。并不是说你一定要期望第一次就能产生这样的代码，我只是跳过了一些我们以前要处理的试错。其实我在写这段代码的时候犯了一大堆错误，我就不展示了。你只能看到我漏掉一个mut或;这么多次才会停止指导。别担心，我们会看到很多其他的错误信息!

> cargo build

error[E0382]: use of moved value: `new_tail`
  --> src/fifth.rs:38:38
   |
26 |         let new_tail = Box::new(Node {
   |             -------- move occurs because `new_tail` has type `std::boxed::Box<fifth::Node<T>>`, which does not implement the `Copy` trait
...
33 |         let old_tail = mem::replace(&mut self.tail, Some(new_tail));
   |                                                          -------- value moved here
...
38 |                 old_tail.next = Some(new_tail);
   |                                      ^^^^^^^^ value used here after move

该死！

使用了转移后的值：new_tail

Box并没有实现Copy，所以我们不能随便把它分配到两个位置。更重要的是，Box拥有它所指向的东西，当它被丢弃时，会尝试释放它。如果我们的push实现编译后，就会把列表的尾部双倍释放! 实际上，就像我们写的那样，我们的代码会在每次push时释放 old_tail。呀!🙀

我们知道如何创建一个非所有者指针。这只是一个参考！

pub struct List<T> {
  head: Link<T>,
  tail: Option<&mut Node<T>>,
}
type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
  elem: T,
  next: Link<T>,
}

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None, tail: None }
    }

    pub fn push(&mut self, elem: T) {
        let new_tail = Box::new(Node {
            elem: elem,
            // When you push onto the tail, your next is always None
            next: None,
        });

        // Put the box in the right place, and then grab a reference to its Node
        // 将box放在正确的位置，然后获取对其Node的引用
        let new_tail = match self.tail.take() {
            Some(old_tail) => {
                // If the old tail existed, update it to point to the new tail
                old_tail.next = Some(new_tail);
                old_tail.next.as_deref_mut()
            }
            None => {
                // Otherwise, update the head to point to it
                self.head = Some(new_tail);
                self.head.as_deref_mut()
            }
        };

        self.tail = new_tail;
    }
}

这没什么难的。和前面的代码基本思路一样，只是我们使用了一些隐式返回的好处，从我们塞入实际Box的地方提取尾部引用。

> cargo build

error[E0106]: missing lifetime specifier
 --> src/fifth.rs:3:18
  |
3 |     tail: Option<&mut Node<T>>, // NEW!
  |                  ^ expected lifetime parameter

对了，我们需要在类型生命周期中提供引用。嗯…这个引用的生命周期是多少?这看起来像IterMut，对吧?让我们尝试一下我们对IterMut所做的，只是添加一个泛型的'a'：

pub struct List<'a, T> {
    head: Link<T>,
    tail: Option<&'a mut Node<T>>, // NEW!
}

impl<'a, T> List<'a, T> {
  ...
}

cargo build

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting 
error[E0495]: 由于需求冲突，无法推断出自动引用的适当生命周期
requirements
  --> src/fifth.rs:35:27
   |
35 |                 self.head.as_deref_mut()
   |                           ^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 18:5...
注意:首先，生命周期不能超过18:5在方法体上定义的匿名生命周期#1…
  --> src/fifth.rs:18:5
   |
18 | /     pub fn push(&mut self, elem: T) {
19 | |         let new_tail = Box::new(Node {
20 | |             elem: elem,
21 | |             // When you push onto the tail, your next is always None
...  |
39 | |         self.tail = new_tail;
40 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
注意:……所以引用不会比借来的内容更长久
  --> src/fifth.rs:35:17
   |
35 |                 self.head.as_deref_mut()
   |                 ^^^^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the impl at 13:6...
注意:但是，生命周期必须在13:6 impl上定义的生命周期 'a 内有效。
  --> src/fifth.rs:13:6
   |
13 | impl<'a, T> List<'a, T> {
   |      ^^
   = note: ...so that the expression is assignable:
   = 注意:……这样表达式就可以赋值了
           expected std::option::Option<&'a mut fifth::Node<T>>
              found std::option::Option<&mut fifth::Node<T>>

哇，那是一条非常详细的错误消息。这有点令人担忧，因为这表明我们正在做的事情确实搞砸了。这是一个有趣的部分：

生命周期必须在impl上定义的生命周期a内有效

我们是从self借来的，但是编译器希望我们的生命期和'a一样长，如果我们告诉它self可以持续那么长时间呢？

pub fn push(&'a mut self, elem: T) {
  ...
}

cargo build

warning: field is never used: `elem`
 --> src/fifth.rs:9:5
  |
9 |     elem: T,
  |     ^^^^^^^
  |
  = note: #[warn(dead_code)] on by default

哦，嘿，成功了!太棒了!

我们也来完成 pop 吧

pub fn pop(&'a mut self) -> Option<T> {
  // 获取list的当前head
  self.head.take().map(|head| {
    let head = *head;
    self.head = head.next;
    // 如果我们的“head”没有，请确保将“tail”设置为“None”
    if self.head.is_none() {
      self.tail = None;
    }
    head.elem
  })
}

并为此编写一个快速测试：

mod test {
  use super::List;
  #[test]
  fn basics() {
    let mut list = List::new();
    
    assert_eq!(list.pop(), None);
    
    list.push(1); list.push(2); list.push(3);
    
    assert_eq!(list.pop(), Some(1));
    assert_eq!(list.pop(), Some(2));
    
    list.push(4); list.push(5);
    
    assert_eq!(list.pop(), Some(3));
    assert_eq!(list.pop(), Some(4));
    
    // check exhaustion
    assert_eq!(list.pop(), Some(5));
    assert_eq!(list.pop(), None);
  }
}

cargo test

error[E0499]: cannot borrow `list` as mutable more than once at a time
  --> src/fifth.rs:68:9
   |
65 |         assert_eq!(list.pop(), None);
   |                    ---- first mutable borrow occurs here
...
68 |         list.push(1);
   |         ^^^^
   |         |
   |         second mutable borrow occurs here
   |         first borrow later used here

error[E0499]: cannot borrow `list` as mutable more than once at a time
  --> src/fifth.rs:69:9
   |
65 |         assert_eq!(list.pop(), None);
   |                    ---- first mutable borrow occurs here
...
69 |         list.push(2);
   |         ^^^^
   |         |
   |         second mutable borrow occurs here
   |         first borrow later used here

error[E0499]: cannot borrow `list` as mutable more than once at a time
  --> src/fifth.rs:70:9
   |
65 |         assert_eq!(list.pop(), None);
   |                    ---- first mutable borrow occurs here
...
70 |         list.push(3);
   |         ^^^^
   |         |
   |         second mutable borrow occurs here
   |         first borrow later used here


....

** WAY MORE LINES OF ERRORS **

....

error: aborting due to 11 previous errors

🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀

哦~ 我的天哪。

编译者对我们的吐槽并没有错。我们只是犯了一个Rust的大罪：我们在自己的内部存储了一个对自己的引用。不知何故，我们设法说服Rust，这在我们的push和pop实现中完全是有意义的（我对此感到非常震惊）。我相信原因是Rust还不能从单纯的push和pop中判断出引用是属于我们自己的——或者更确切地说，Rust根本就没有这个概念。引用到自己身上失效只是一种紧急的行为。

当我们尝试使用我们的列表时，一切很快就崩溃了。当我们调用push或pop时，我们会立即将对自己的引用存储在我们自己中并陷入困境。我们实际上是在借用自己。

我们的pop实现暗示了为什么这可能真的很危险

// ...
if self.head.is_none() {
    self.tail = None;
}

如果我们忘了这样做呢？那我们的tail就会指向某个被从列表中删除的节点。这样的节点会被立即释放，我们会有一个悬空的指针，而Rust本来应该保护我们的。

而事实上，Rust正在保护我们免受这种危险。只是以一种非常… 迂回的方式。

所以，我们能做些什么？回到Rc <RefCell>>地狱？

行行好，不行

不，相反，我们将偏离常规，使用原始指针。我们的布局是这样的：

pub struct List<T> {
  head: Link<T>,
  tail: *mut Node<T>, // 危险 Danger
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
  elem: T,
  next: Link<T>,
}

就是这样。真的别跟我说这些没用的引用计数、动态借用检查的废话

硬核、没有检查的指针才是王道~

让我们成为C语言的人吧，让我们回到C语言一整天。

我准备好了。

你好，unsafe

6.2. Unsafe

这是一个严肃，重大，复杂和危险的话题。这是如此严重，以至于我写了另一本书。

简而言之，只要你允许调用其他语言，每一种语言实际上都是不安全的，因为你可以让C做任意错误的事情。是的:Java, Python, Ruby, Haskell…在外部函数接口(FFI)面前，每个人都非常不安全。

Rust通过将自己分成两种语言来接受这个事实。安全Rust和不安全Rust。到目前为止，我们只使用了安全Rust。它是完全100%安全的……除了它可以FFI成不安全的Rust。

不安全Rust是安全Rust的超级集。它的语义和规则与安全Rust完全相同，只是允许你做一些额外的事情，这些事情非常不安全，可能会导致可怕的未定义行为，困扰着C。

这是一个非常大的话题有很多有趣的特例。我真的不想太深入(好吧，我是想的。我读过那本书)。这没关系，因为使用链表，我们实际上可以忽略几乎所有这些。

我们将使用的主要不安全工具是原始指针。原始指针基本上是C的指针。它们没有固有的别名规则。他们没有生命期。它们可以是null。它们可以悬挂着。它们可以指向未初始化的内存。它们可以转换为整数，也可以从整数转换为指针。它们可以被强制转换指向另一种类型。可变性吗?转换它。几乎所有的东西都可以，这意味着几乎所有的东西都可以出错。

这是一些不好的东西，说实话，你永远不用去碰这些东西，你会活得更开心。不幸的是，我们想写链表，而链表是可怕的。这意味着我们将不得不使用不安全的指针。

原始指针有两种：*const T和*mut T。它们的意思是来自C的const T *和T *，但我们实际上并不关心C认为它们的含义是什么。您只能将* const T解引用到＆T，但是就像变量的可变性一样，这只是防止不正确使用的纱布。最多只是意味着您必须先将* const强制转换为* mut。但是如果你没有修改指针的引用的权限，你就会有麻烦了。

无论如何，当我们编写一些代码时，我们会对此有更好的感觉。目前，

*mut T = &unchecked mut T

6.3. Basics

好了，回到最基本的bascis。我们如何构造我们的列表

之前，我们是这样写的：

impl<T> List<T> {
  pub fn new() -> Self {
    List { head: None, tail: None }
  }
}

但我们不再对尾部使用Option了

> cargo build

error[E0308]: mismatched types
  --> src/fifth.rs:15:34
   |
15 |         List { head: None, tail: None }
   |                                  ^^^^ expected *-ptr, found enum `std::option::Option`
   |
   = note: expected type `*mut fifth::Node<T>`
              found type `std::option::Option<_>`

我们可以使用Option，但是与Box不同，* mut是可为空的。这意味着它不能从空指针优化中受益。相反，我们将使用null来表示None。

那么我们如何获得一个空指针呢？有几种方法，但是我更喜欢使用std::ptr::nul_mut()。如果需要，您也可以使用 0 as *mut _，但这似乎太混乱了。

use std::ptr;

// 定义 ...

impl<T> List<T> {
  pub fn new() -> Self {
    List { head: None, tail: ptr::null_mut() }
  }
}

> cargo build
** 一堆字段未使用的警告 **

嘘~ ，编译器，我们很快就会使用它们。

好了，我们继续写push。这一次，我们不是在插入后抓取一个Option<&mut Node<T>>，而是马上抓取一个*mut Node<T>到Box的内部。我们知道我们可以这样做，因为Box的内容有一个稳定的地址，即使我们移动Box。当然，这样做是不安全的，因为如果我们直接丢掉这个Box，就会有一个指向已释放内存的指针。

我们如何从普通指针制作原始指针？威逼！如果将变量声明为原始指针，则普通引用将强制进入该变量：

let raw_tail: *mut _ = &mut *new_tail;

我们需要的信息都有了。我们可以将我们的代码近似地翻译成以前的参考版本

pub fn push(&mut self, elem: T) {
  let mut new_tail = Box::new(Node {
    elem,
    next: None,
  });
  let raw_tail: *mut _ = &mut *new_tail;
  
  // .is_null 检查null，等同于检查None
  if !self.tail.is_null() {
    self.tail.next = Some(new_tail);
  } else {
    self.head = Some(new_tail);
  }
  self.tail = raw_tail;
}

> cargo build

error[E0609]: no field `next` on type `*mut fifth::Node<T>`
  --> src/fifth.rs:31:23
   |
31 |             self.tail.next = Some(new_tail);
   |             ----------^^^^
   |             |
   |             help: `self.tail` is a raw pointer; try dereferencing it: `(*self.tail).next`

嗯?我们有一个指向Node的指针，为什么我们不能得到next字段?

当你用原始指针的时候，Rust有点混蛋。为了访问原始指针的内容，它坚持要手动对其进行解引用，因为这是一个非常不安全的操作。我们来做一下:

*self.tail.next = Some(new_tail);

> cargo build

error[E0609]: no field `next` on type `*mut fifth::Node<T>`
  --> src/fifth.rs:31:23
   |
31 |             *self.tail.next = Some(new_tail);
   |             -----------^^^^
   |             |
   |             help: `self.tail` is a raw pointer; try dereferencing it: `(*self.tail).next`

呃~~ 运算优先级~~

(*self.tail).next = Some(new_tail);

> cargo build

error[E0133]: dereference of raw pointer is unsafe and requires unsafe function or block
  --> src/fifth.rs:31:13
   |
31 |             (*self.tail).next = Some(new_tail);
   |             ^^^^^^^^^^^^^^^^^ dereference of raw pointer
   |
   = note: raw pointers may be NULL, dangling or unaligned; they can violate aliasing rules and cause data races: all of these are undefined behavior

就不应该这么难！！！

还记得我说不安全的Rust就像一个FFI语言的安全Rust吗?编译器想让我们显式地界定我们在哪放置这个FFI。我们有两个选择。首先，我们可以将整个函数标记为不安全的，在这种情况下，它成为不安全的Rust函数，只能在不安全的上下文中调用。这并不好，因为我们希望我们的列表是安全使用的。其次，我们可以在函数内部编写一个不安全的块，来划定FFI边界。这声明了整个函数是安全的。我们来做这个：

pub fn push(&mut self, elem: T) {
  let mut new_tail = Box::new(Node {
    elem,
    next: None,
  });
  let raw_tail: *mut _ = &mut *new_tail;
  
  if !self.tail.is_null() {
    unsafe{
      (*self.tail).next = Some(new_tail);
    }
  } else {
    self.head = Some(new_tail);
  }
}

> cargo build
编译通过

耶!

有趣的是，到目前为止，这是我们唯一写不安全块的地方。但我们到处都是原始指针，这是怎么回事？

事实证明，在不安全的问题上，Rust是一个庞大的规则学究。我们很合理地想要最大化安全Rust程序集，因为这些程序我们可以更有信心。为了达到这个目的，Rust小心翼翼地为不安全划出了最小的表面积。请注意，我们使用原始指针的所有其他地方都是对它们进行赋值，或者只是观察它们是否为空。

如果你从来没有解引用过原始指针那是完全安全的事情。您只是读写一个整数!使用原始指针唯一可能遇到麻烦的情况是对它进行解引用。所以Rust说只有这个操作是不安全的，其他一切都是完全安全的。

超级学究。但技术上正确的。

然而，这引发了一个有趣的问题:尽管我们应该用不安全块来界定不安全块的范围，但它实际上取决于在块之外建立的状态。甚至是在函数之外！这就是我所说的不安全污染。

一旦你在一个模块中使用了unsafe，整个模块就会被unsafe污染。为了确保不安全代码的不变性得到维护，必须正确地编写所有内容。

由于隐私的关系，这种污染是可以处理的。在我们的模块之外，所有的struct字段都是完全私有的，所以其他人不能以任意的方式干扰我们的状态。只要我们公开的api组合没有导致糟糕的事情发生，就外部观察者而言，我们所有的代码都是安全的!实际上，这和FFI的情况没有什么不同。只要暴露出一个安全的接口，没有人需要关心某个python数学库是否会外壳到C语言。

不管怎样，我们来看看pop，它和参考版本几乎一字不差

pub fn pop(&mut self) -> Option<T> {
  self.head.take().map(|head| {
    let head = *head;
    self.head = head.next;
    
    if self.head.is_none() {
      self.tail = ptr::null_mut();
    }
    head.elem
  })
}

再一次，我们看到了另一种情况，即安全是有状态的。如果我们无法在该函数中使尾指针为零，那么我们将看不到任何问题。但是，随后的push调用将开始写入悬空的tail！

让我们来测试一下

#[cfg(test)]
mod test {
  use super::List;
  #[test]
  fn basics() {
    let mut list = List::new();
    assert_eq!(list.pop(), None);
    list.push(1); list.push(2); list.push(3);
    
    assert_eq!(list.pop(), Some(1));
    assert_eq!(list.pop(), Some(2));
    
    list.push(4);
    list.push(5);
    
    assert_eq!(list.pop(), Some(3));
    assert_eq!(list.pop(), Some(4));
    
    assert_eq!(list.pop(), Some(5));
    assert_eq!(list.pop(), None);
    
    list.push(6);
    list.push(7);
    
    assert_eq!(list.pop(), Some(6));
    assert_eq!(list.pop(), Some(7));
    assert_eq!(list.pop(), None);
  }
}

这只是堆栈测试，但是把预期的pop结果翻转过来了。我还在最后增加了一些额外的步骤，以确保pop中的尾指针损坏情况不会发生。

> cargo test

God Star!

6.4. Extras

现在已经编写了push和pop，其他所有内容与堆栈情况完全相同。只有更改列表长度的操作才需要真正担心尾指针。

因此，让我们从第二个列表中窃取所有内容（请确保反转预期的测试输出）：

// ...

pub struct IntoIter<T>(List<T>);

pub struct Iter<'a, T> {
  next: Option<&'a Node<T>>,
}
pub struct IterMut<'a, T> {
  next: Option<&'a mut Node<T>>,
}

impl<T> List<T> {
  // ...
  
  pub fn peek(&self) -> Option<&T> {
    self.head.as_ref().map(|node| &node.elem)
  }
  
  pub fn peek_mut(&mut self) -> Option<&mut T> {
    self.head.as_ref().map(|node| &mut node.elem)
  }
  
  pub fn into_iter(self) -> IntoIter<T> {
    IntoIter(self)
  }
  
  pub fn iter(&self) -> Iter<'_, T> {
    Iter { next: self.head.as_deref() }
  }
  
  pub fn iter_mut(&mut self) -> IterMut<'_, T> {
    IterMut { next: self.head.as_deref_mut() }
  }
}

impl<T> Drop for List<T> {
  fn drop(&mut self) {
    let mut cur_link = self.head.take();
    while let Some(mut boxed_node) = cur_link {
      cur_link = boxed_node.next.take();
    }
  }
}

impl<T> Iterator for IntoIter<T> {
  type Item = T;
  fn next(&mut self) -> Option<Self::Item> {
    self.0.pop()
  }
}

impl<'a, T> Iterator for Iter<'a, T> {
  type Item = &'a T;
  fn next(&mut self) -> Option<Self::Item> {
    self.next.map(|node| {
      self.next = node.next.as_deref();
      &node.elem
    })
  }
}

impl<'a, T> Iterator for IterMut<'a, T> {
  type Item = &'a mut T;
  fn next(&mut self) -> Option<Self::Item> {
    self.next.take().map(|node| {
      self.next = node.next.as_deref_mut();
      &mut node.elem
    })
  }
}

#[cfg(test)]
mod test {
    // ...

    #[test]
    fn into_iter() {
        let mut list = List::new();
        list.push(1); list.push(2); list.push(3);

        let mut iter = list.into_iter();
        assert_eq!(iter.next(), Some(1));
        assert_eq!(iter.next(), Some(2));
        assert_eq!(iter.next(), Some(3));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn iter() {
        let mut list = List::new();
        list.push(1); list.push(2); list.push(3);

        let mut iter = list.iter();
        assert_eq!(iter.next(), Some(&1));
        assert_eq!(iter.next(), Some(&2));
        assert_eq!(iter.next(), Some(&3));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn iter_mut() {
        let mut list = List::new();
        list.push(1); list.push(2); list.push(3);

        let mut iter = list.iter_mut();
        assert_eq!(iter.next(), Some(&mut 1));
        assert_eq!(iter.next(), Some(&mut 2));
        assert_eq!(iter.next(), Some(&mut 3));
        assert_eq!(iter.next(), None);
    }
}

> cargo test

大声疾呼的复制粘贴编程。

起初我以为用IntoIter会弄乱，但我们还是很方便地按迭代顺序弹出结果了！

6.5. Final Code

好了，通过一点点的不安全性，我们成功地在简单的安全队列上得到了线性时间上的改进，并且我们成功地重用了来自安全堆栈的几乎所有逻辑!我们也不需要编写任何疯狂的Rc或RefCell内容。

pub struct List<T> {
    head: Link<T>,
    tail: *mut Node<T>,
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

impl<T> Node<T> {
    pub fn new(elem: T) -> Box<Node<T>> {
        Box::new(Node { elem, next: None })
    }
}

impl<T> List<T> {
    pub fn new() -> Self {
        List {
            head: None,
            tail: std::ptr::null_mut(),
        }
    }

    pub fn push(&mut self, elem: T) {
        let mut new_tail = Node::new(elem);
        let raw_tail: *mut _ = &mut *new_tail;

        if !self.tail.is_null() {
            unsafe {
                (*self.tail).next = Some(new_tail);
            }
        } else {
            self.head = Some(new_tail);
        }
        self.tail = raw_tail;
    }

    pub fn pop(&mut self) -> Option<T> {
        self.head.take().map(|old_head| {
            self.head = old_head.next;
            if self.head.is_none() {
                self.tail = std::ptr::null_mut();
            }
            old_head.elem
        })
    }

    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }

    pub fn iter(&self) -> Iter<T> {
        Iter {
            next: self.head.as_deref(),
        }
    }

    pub fn iter_mut(&mut self) -> IterMut<T> {
        IterMut {
            next: self.head.as_deref_mut(),
        }
    }

    pub fn peek(&self) -> Option<&T> {
        self.head.as_ref().map(|old_head| &old_head.elem)
    }

    pub fn peek_mut(&mut self) -> Option<&mut T> {
        self.head.as_mut().map(|old_head| &mut old_head.elem)
    }
}

pub struct IntoIter<T>(List<T>);

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.head.take().map(|old_head| {
            self.0.head = old_head.next;
            old_head.elem
        })
    }
}
pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|old_head| {
            self.next = old_head.next.as_deref();
            &old_head.elem
        })
    }
}
pub struct IterMut<'a, T> {
    next: Option<&'a mut Node<T>>,
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|old_head| {
            self.next = old_head.next.as_deref_mut();
            &mut old_head.elem
        })
    }
}

#[cfg(test)]
mod test {
    use super::List;
    #[test]
    fn basics() {
        let mut list = List::new();

        // Check empty list behaves right
        assert_eq!(list.pop(), None);

        // Populate list
        list.push(1);
        list.push(2);
        list.push(3);

        // Check normal removal
        assert_eq!(list.pop(), Some(1));
        assert_eq!(list.pop(), Some(2));

        // Push some more just to make sure nothing's corrupted
        list.push(4);
        list.push(5);

        // Check normal removal
        assert_eq!(list.pop(), Some(3));
        assert_eq!(list.pop(), Some(4));

        // Check exhaustion
        assert_eq!(list.pop(), Some(5));
        assert_eq!(list.pop(), None);

        // Check the exhaustion case fixed the pointer right
        list.push(6);
        list.push(7);

        // Check normal removal
        assert_eq!(list.pop(), Some(6));
        assert_eq!(list.pop(), Some(7));
        assert_eq!(list.pop(), None);
    }

    #[test]
    fn into_iter() {
        let mut list = List::new();
        list.push(1);
        list.push(2);
        list.push(3);

        let mut iter = list.into_iter();
        assert_eq!(iter.next(), Some(1));
        assert_eq!(iter.next(), Some(2));
        assert_eq!(iter.next(), Some(3));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn iter() {
        let mut list = List::new();
        list.push(1);
        list.push(2);
        list.push(3);

        let mut iter = list.iter();
        assert_eq!(iter.next(), Some(&1));
        assert_eq!(iter.next(), Some(&2));
        assert_eq!(iter.next(), Some(&3));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn iter_mut() {
        let mut list = List::new();
        list.push(1);
        list.push(2);
        list.push(3);

        let mut iter = list.iter_mut();
        assert_eq!(iter.next(), Some(&mut 1));
        assert_eq!(iter.next(), Some(&mut 2));
        assert_eq!(iter.next(), Some(&mut 3));
        assert_eq!(iter.next(), None);
    }
}

7. 一个Ok但不安全的双链双端队列

不，我还没写完这本书!这并没有什么意义。如果你真的想要更多的话，请阅读The Rustonomicon和std::collections::LinkedList的源代码

8. 一堆愚蠢的清单

好吧。就是这样。我们列了所有的清单。哈哈，不，总是会有更多的清单这一章是一个活生生的文档，讲述了更荒谬的链表，以及它们如何与Rust互动

The Double Single
TODO: BList?
TODO: SkipList?
TODO: std::channel? – That’s like another whole chapter. Or 3.

8.1. 双单链表

我们在处理双重链接列表时很费劲，因为它们的所有权语义很纠结:没有一个节点严格地拥有任何其他节点。然而我们之所以在这个问题上挣扎，是因为我们带来了我们对链接列表是什么的先入为主的概念。也就是说，我们假设所有的链接都是朝同一个方向走的。

相反，我们可以把列表分成两半:一个向左，一个向右：

// lib.rs
// ...
pub mod silly;

// silly1.rs
use second::List as Stack;

struct List<T> {
  left: Stack<T>,
  right: Stack<T>,
}

现在，我们有了一个通用列表，而不仅仅是一个安全堆栈。我们可以通过推入任意一个堆栈来向左或向右增长列表。我们还可以通过将值从一端弹出到另一端来“遍历”列表。为了避免不必要的分配，我们将复制安全堆栈的源码，以访问其私有详细信息

pub struct Stack<T> {
  head: Link<T>,
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
  elem: T,
  next: Link<T>
}

impl<T> Stack<T> {
  pub fn new() -> Self {
    Stack { head: None }
  }
  
  pub fn push(&mut self, elem: T) {
    let new_node = Box::new(Node {
      elem,
      next: self.head.take(),
    });
    self.head = Some(new_node);
  }
  
  pub fn pop(&mut self) -> Option<T> {
    self.head.take().map(|node| {
      let node = *node;
      self.head = node.next;
      node.elem
    })
  }
  
  pub fn peek(&self) -> Option<&T> {
    self.head.as_ref().map(|node| &node.elem)
  }
  
  pub fn peek_mut(&mut self) -> Option<&mut T> {
    self.head.as_mut().map(|node| &mut node.elem)
  }
}

impl<T> Drop for Stack<T> {
  fn drop(&mut self) {
    let mut cur_link = self.head.take();
    while let Some(mut boxed_node) = cur_link {
      cur_link = boxed_noded.next.take();
    }
  }
}

然后再重写push和pop

pub fn push(&mut self, elem: T) {
  let new_node = Box::new(Node{
    elem,
    next: None,
  });
  self.push_node(new_node);
}

fn push_node(&mut self, mut node: Box<Node<T>>) {
  node.next = self.head.take();
  self.head = Some(node);
}

pub fn pop(&mut self) -> Option<T> {
  self.pop_node().map(|node| node.elem)
}

fn pop_node(&mut self) -> Option<Box<Node<T>>> {
  self.head = node.next.take();
  node
}

现在我们可以做出我们的链表了：

pub struct List<T> {
  left: Stack<T>,
  right: Stack<T>,
}

impl<T> List<T> {
  fn new() -> Self {
    List { left: Stack::new(), right: Stack::new() }
  }
}

而且我们可以做一些常用的接口：

pub fn push_left(&mut self, elem: T) { self.left.push(elem) }
pub fn push_right(&mut self, elem: T) { self.right.push(elem) }
pub fn pop_left(&mut self) -> Option<T> { self.left.pop() }
pub fn pop_right(&mut self) -> Option<T> { self.right.pop() }
pub fn peek_left(&self) -> Option<&T> { self.left.peek() }
pub fn peek_right(&self) -> Option<&T> { self.right.peek() }
pub fn peek_left_mut(&mut self) -> Option<&mut T> { self.left.peek_mut() }
pub fn peek_right_mut(&mut self) -> Option<&mut T> { self.right.peek_mut() }

但最有趣的是，我们可以遍历：

pub fn go_left(&mut self) -> bool {
  self.left.pop_node().map(|node| {
    self.right.push_node(node);
  }).is_some()
}

pub fn go_right(&mut self) -> bool {
  self.right.pop_node().map(|node| {
    self.left.push_node(node);
  }).is_some()
}

我们在这里返回booleans只是为了方便表示我们是否真的成功移动。现在我们来测试一下这个宝贝：

#[cfg(test)]
mod test {
    use super::List;

    #[test]
    fn walk_aboot() {
        let mut list = List::new();             // [_]

        list.push_left(0);                      // [0,_]
        list.push_right(1);                     // [0, _, 1]
        assert_eq!(list.peek_left(), Some(&0));
        assert_eq!(list.peek_right(), Some(&1));

        list.push_left(2);                      // [0, 2, _, 1]
        list.push_left(3);                      // [0, 2, 3, _, 1]
        list.push_right(4);                     // [0, 2, 3, _, 4, 1]

        while list.go_left() {}                 // [_, 0, 2, 3, 4, 1]

        assert_eq!(list.pop_left(), None);
        assert_eq!(list.pop_right(), Some(0));  // [_, 2, 3, 4, 1]
        assert_eq!(list.pop_right(), Some(2));  // [_, 3, 4, 1]

        list.push_left(5);                      // [5, _, 3, 4, 1]
        assert_eq!(list.pop_right(), Some(3));  // [5, _, 4, 1]
        assert_eq!(list.pop_left(), Some(5));   // [_, 4, 1]
        assert_eq!(list.pop_right(), Some(4));  // [_, 1]
        assert_eq!(list.pop_right(), Some(1));  // [_]

        assert_eq!(list.pop_right(), None);
        assert_eq!(list.pop_left(), None);

    }
}

> cargo test

这是手指数据结构的一个极端例子，我们在结构中保持了某种手指，因此可以支持在时间上对与手指距离成正比的位置进行操作。

我们可以对手指周围的列表进行非常快速的更改，但是如果我们要在离手指很远的地方进行更改，我们就必须一直走到那边去。我们可以通过将元素从一个堆栈转移到另一个堆栈来永久地走过去，或者我们可以用&mut暂时沿着链接走过去来进行更改。然而，&mut永远不能回到列表中去，而我们的手指可以。

附录

转换	函数
`Option<T> -> Option<&T>`	`Option::as_ref(&self) -> Option<&T>`
`Option<T> -> Option<&mut T>`	`Option::as_mut(&self) -> Option<&mut T>`
`Option<T> -> Option<&<T as Deref>::Target>`	`Option::as_deref(&self)`
`Option<T> -> Option<&mut <TasDeref>::Target>`	`Option::as_deref_mut(&self)`
`Option<T> -> Option<U>`	`Option::map(\|node\| node)` `Option::and_then(\|node\| Some(node))`
`Option<T> -> None`	`x = y.take()` `x = mem::replace(&mut y, None)`
`Option<T> -> T`	`Option::unwrap(self) -> T`
`Rc<T> -> Result<T, Rc<T>> / Ok<T>`	`Rc::try_unwrap(x: Rc<T>)`
`Rc<RefCell<Node<T>>> -> &RefCell<Node<T>>`	`x.as_deref()`
`RefCell<T> -> T`	`RefCell::into_inner(self) -> T`
`Result<T> -> Option<T>`	`Result::ok(self) -> Option<T>`
`Ref<T> -> Ref<U>/ Ref<Node<T>> -> Ref<U>`	`Ref::map(Ref<T>, F) -> Ref<'_, U>` `where F: FnOnce<&T> -> &U`
`Ref<T> -> &T`	`Ref::map(Ref<T>, \|x: &T\| &x.elem) -> Ref<U>`

match 表达式

match表达式在模式上产生分支。匹配的具体形式取决于模式。匹配表达式有一个检查表达式，它是要与模式进行比较的值。被审查者的表达和模式必须具有相同的类型。

匹配的行为不同，取决于检查对象表达式是位置表达式还是值表达式。如果检查对象表达式是一个值表达式，那么它首先会被计算，并放进一个临时位置，然后将结果值按顺序与arms中的模式进行比较，直到找到匹配的为止。带有匹配模式的第一个arm被选择为匹配的分支目标，模式所绑定的任何变量都被分配给arm块中的局部变量，控制流进入匹配块中。

当检审查达式是位置表达式时，匹配不分配临时位置;但是，按值绑定可以从内存位置复制或移动。如果可能的话，更可取的方法是匹配位置表达式，因为这些匹配的生存期继承place表达式的生存期，而不是被限制在匹配的内部。

let x = 1;
match x {
  1 => println!("one"),
  2 => println!("two"),
  _ => println!("something else"),
}

模式中变量绑定的作用域是匹配守护match guard和arm表达式。绑定方式(移动、复制或引用)取决于模式。可以用|操作符连接多个匹配模式。每个模式将按照从左到右的顺序进行测试，直到找到一个成功的匹配。

上篇rust 所有权

下篇leetcode 数组