# 布局

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

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

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

```
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被删除时，它的内存才会被释放。不幸的是，这种灵活性付出了严重的代价：我们只能共同引用其内部。这意味着我们不能真正从我们的列表中获取数据，也不能对它们进行修改。

那么我们的布局会是什么样？ 好吧，以前我们有：

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

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

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

我们能不能把 Box 改成 Rc？

```rust
// 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>,
}
```

```rust
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程序中。真是个失败者。

```rust
use std::rc::Rc;
```

```rust
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的那一天。

...

不，不，我们不能。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://chapin666.gitbook.io/too-many-list-zh/yi-ge-bu-ke-bian-zhan/bu-ju.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.