布局

好了，回到设计图板上来。

关于不可变列表的最重要的事情是，您可以基本上零开销地操纵列表的尾部。

例如，对于不可变列表，这是一种常见的工作负载：

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？对于 Box，我们当然会这样期待！

函数式语言——实际上几乎所有其他语言——都可以通过使用垃圾回收来避免这种情况。有了垃圾收集的魔力，B只有在所有对象都停止对它的使用之后才会被释放。万岁！

没有这些语言所拥有的垃圾收集器，它们有跟踪 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>,
   |     ^^^^^^^^^^^^^

看起来是合法的，仍然完全是琐碎的编写。我敢打赌，我们能找到Box并将其替换为Rc的那一天。

...

不，不，我们不能。