Rust 使用Box<T>指向堆上的數(shù)據(jù)

ch15-01-box.md
commit 359895c6b2e440275a663ee1a3c17e6a94fdc62b

最簡單直接的智能指針是 box，其類型是 Box<T>。 box 允許你將一個值放在堆上而不是棧上。留在棧上的則是指向堆數(shù)據(jù)的指針。如果你想回顧一下棧與堆的區(qū)別請參考第四章。

除了數(shù)據(jù)被儲存在堆上而不是棧上之外，box 沒有性能損失。不過也沒有很多額外的功能。它們多用于如下場景：

• 當(dāng)有一個在編譯時未知大小的類型，而又想要在需要確切大小的上下文中使用這個類型值的時候
• 當(dāng)有大量數(shù)據(jù)并希望在確保數(shù)據(jù)不被拷貝的情況下轉(zhuǎn)移所有權(quán)的時候
• 當(dāng)希望擁有一個值并只關(guān)心它的類型是否實(shí)現(xiàn)了特定 trait 而不是其具體類型的時候

我們會在 “box 允許創(chuàng)建遞歸類型” 部分展示第一種場景。在第二種情況中，轉(zhuǎn)移大量數(shù)據(jù)的所有權(quán)可能會花費(fèi)很長的時間，因為數(shù)據(jù)在棧上進(jìn)行了拷貝。為了改善這種情況下的性能，可以通過 box 將這些數(shù)據(jù)儲存在堆上。接著，只有少量的指針數(shù)據(jù)在棧上被拷貝。第三種情況被稱為 trait 對象（trait object），第十七章剛好有一整個部分 “顧及不同類型值的 trait 對象” 專門講解這個主題。所以這里所學(xué)的內(nèi)容會在第十七章再次用上！

使用 Box<T> 在堆上儲存數(shù)據(jù)

在討論 Box<T> 的用例之前，讓我們熟悉一下語法以及如何與儲存在 Box<T> 中的值進(jìn)行交互。

示例 15-1 展示了如何使用 box 在堆上儲存一個 i32：

文件名: src/main.rs

fn main() {
    let b = Box::new(5);
    println!("b = {}", b);
}

示例 15-1：使用 box 在堆上儲存一個 i32 值

這里定義了變量 b，其值是一個指向被分配在堆上的值 5 的 Box。這個程序會打印出 b = 5；在這個例子中，我們可以像數(shù)據(jù)是儲存在棧上的那樣訪問 box 中的數(shù)據(jù)。正如任何擁有數(shù)據(jù)所有權(quán)的值那樣，當(dāng)像 b 這樣的 box 在 main 的末尾離開作用域時，它將被釋放。這個釋放過程作用于 box 本身（位于棧上）和它所指向的數(shù)據(jù)（位于堆上）。

將一個單獨(dú)的值存放在堆上并不是很有意義，所以像示例 15-1 這樣單獨(dú)使用 box 并不常見。將像單個 i32 這樣的值儲存在棧上，也就是其默認(rèn)存放的地方在大部分使用場景中更為合適。讓我們看看一個不使用 box 時無法定義的類型的例子。

Box 允許創(chuàng)建遞歸類型

Rust 需要在編譯時知道類型占用多少空間。一種無法在編譯時知道大小的類型是 遞歸類型（recursive type），其值的一部分可以是相同類型的另一個值。這種值的嵌套理論上可以無限的進(jìn)行下去，所以 Rust 不知道遞歸類型需要多少空間。不過 box 有一個已知的大小，所以通過在循環(huán)類型定義中插入 box，就可以創(chuàng)建遞歸類型了。

讓我們探索一下 cons list，一個函數(shù)式編程語言中的常見類型，來展示這個（遞歸類型）概念。除了遞歸之外，我們將要定義的 cons list 類型是很直白的，所以這個例子中的概念，在任何遇到更為復(fù)雜的涉及到遞歸類型的場景時都很實(shí)用。

cons list 的更多內(nèi)容

cons list 是一個來源于 Lisp 編程語言及其方言的數(shù)據(jù)結(jié)構(gòu)。在 Lisp 中，cons 函數(shù)（“construct function" 的縮寫）利用兩個參數(shù)來構(gòu)造一個新的列表，他們通常是一個單獨(dú)的值和另一個列表。

cons 函數(shù)的概念涉及到更常見的函數(shù)式編程術(shù)語；“將 x 與 y 連接” 通常意味著構(gòu)建一個新的容器而將 x 的元素放在新容器的開頭，其后則是容器 y 的元素。

cons list 的每一項都包含兩個元素：當(dāng)前項的值和下一項。其最后一項值包含一個叫做 Nil 的值且沒有下一項。cons list 通過遞歸調(diào)用 cons 函數(shù)產(chǎn)生。代表遞歸的終止條件（base case）的規(guī)范名稱是 Nil，它宣布列表的終止。注意這不同于第六章中的 “null” 或 “nil” 的概念，他們代表無效或缺失的值。

注意雖然函數(shù)式編程語言經(jīng)常使用 cons list，但是它并不是一個 Rust 中常見的類型。大部分在 Rust 中需要列表的時候，Vec<T> 是一個更好的選擇。其他更為復(fù)雜的遞歸數(shù)據(jù)類型 確實(shí) 在 Rust 的很多場景中很有用，不過通過以 cons list 作為開始，我們可以探索如何使用 box 毫不費(fèi)力的定義一個遞歸數(shù)據(jù)類型。

示例 15-2 包含一個 cons list 的枚舉定義。注意這還不能編譯因為這個類型沒有已知的大小，之后我們會展示：

文件名: src/main.rs

enum List {
    Cons(i32, List),
    Nil,
}

示例 15-2：第一次嘗試定義一個代表 i32 值的 cons list 數(shù)據(jù)結(jié)構(gòu)的枚舉

注意：出于示例的需要我們選擇實(shí)現(xiàn)一個只存放 ?i32? 值的 cons list。也可以用泛型，正如第十章講到的，來定義一個可以存放任何類型值的 cons list 類型。

使用這個 cons list 來儲存列表 1, 2, 3 將看起來如示例 15-3 所示：

文件名: src/main.rs

use crate::List::{Cons, Nil};

fn main() {
    let list = Cons(1, Cons(2, Cons(3, Nil)));
}

示例 15-3：使用 List 枚舉儲存列表 1, 2, 3

第一個 Cons 儲存了 1 和另一個 List 值。這個 List 是另一個包含 2 的 Cons 值和下一個 List 值。接著又有另一個存放了 3 的 Cons 值和最后一個值為 Nil 的 List，非遞歸成員代表了列表的結(jié)尾。

如果嘗試編譯示例 15-3 的代碼，會得到如示例 15-4 所示的錯誤：

$ cargo run
   Compiling cons-list v0.1.0 (file:///projects/cons-list)
error[E0072]: recursive type `List` has infinite size
 --> src/main.rs:1:1
  |
1 | enum List {
  | ^^^^^^^^^ recursive type has infinite size
2 |     Cons(i32, List),
  |               ---- recursive without indirection
  |
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to make `List` representable
  |
2 |     Cons(i32, Box<List>),
  |               ++++    +

error[E0391]: cycle detected when computing drop-check constraints for `List`
 --> src/main.rs:1:1
  |
1 | enum List {
  | ^^^^^^^^^
  |
  = note: ...which immediately requires computing drop-check constraints for `List` again
  = note: cycle used when computing dropck types for `Canonical { max_universe: U0, variables: [], value: ParamEnvAnd { param_env: ParamEnv { caller_bounds: [], reveal: UserFacing }, value: List } }`

Some errors have detailed explanations: E0072, E0391.
For more information about an error, try `rustc --explain E0072`.
error: could not compile `cons-list` due to 2 previous errors

示例 15-4：嘗試定義一個遞歸枚舉時得到的錯誤

這個錯誤表明這個類型 “有無限的大小”。其原因是 List 的一個成員被定義為是遞歸的：它直接存放了另一個相同類型的值。這意味著 Rust 無法計算為了存放 List 值到底需要多少空間。讓我們一點(diǎn)一點(diǎn)來看：首先了解一下 Rust 如何決定需要多少空間來存放一個非遞歸類型。

計算非遞歸類型的大小

回憶一下第六章討論枚舉定義時示例 6-2 中定義的 ?Message? 枚舉：

enum Message {
    Quit,
    Move { x: i32, y: i32 },
    Write(String),
    ChangeColor(i32, i32, i32),
}

當(dāng) Rust 需要知道要為 Message 值分配多少空間時，它可以檢查每一個成員并發(fā)現(xiàn) Message::Quit 并不需要任何空間，Message::Move 需要足夠儲存兩個 i32 值的空間，依此類推。因為 enum 實(shí)際上只會使用其中的一個成員，所以 Message 值所需的空間等于儲存其最大成員的空間大小。

與此相對當(dāng) Rust 編譯器檢查像示例 15-2 中的 List 這樣的遞歸類型時會發(fā)生什么呢。編譯器嘗試計算出儲存一個 List 枚舉需要多少內(nèi)存，并開始檢查 Cons 成員，那么 Cons 需要的空間等于 i32 的大小加上 List 的大小。為了計算 List 需要多少內(nèi)存，它檢查其成員，從 Cons 成員開始。Cons成員儲存了一個 i32 值和一個List值，這樣的計算將無限進(jìn)行下去，如圖 15-1 所示：

圖 15-1：一個包含無限個 Cons 成員的無限 List

使用 Box<T> 給遞歸類型一個已知的大小

Rust 無法計算出要為定義為遞歸的類型分配多少空間，所以編譯器給出了示例 15-4 中的錯誤。這個錯誤也包括了有用的建議：

help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to make `List` representable
  |
2 |     Cons(i32, Box<List>),
  |               ^^^^    ^

在建議中，“indirection” 意味著不同于直接儲存一個值，我們將間接的儲存一個指向值的指針。

因為 Box<T> 是一個指針，我們總是知道它需要多少空間：指針的大小并不會根據(jù)其指向的數(shù)據(jù)量而改變。這意味著可以將 Box 放入 Cons 成員中而不是直接存放另一個 List 值。Box 會指向另一個位于堆上的 List 值，而不是存放在 Cons 成員中。從概念上講，我們?nèi)匀挥幸粋€通過在其中 “存放” 其他列表創(chuàng)建的列表，不過現(xiàn)在實(shí)現(xiàn)這個概念的方式更像是一個項挨著另一項，而不是一項包含另一項。

我們可以修改示例 15-2 中 List 枚舉的定義和示例 15-3 中對 List 的應(yīng)用，如示例 15-65 所示，這是可以編譯的：

文件名: src/main.rs

enum List {
    Cons(i32, Box<List>),
    Nil,
}

use crate::List::{Cons, Nil};

fn main() {
    let list = Cons(1, Box::new(Cons(2, Box::new(Cons(3, Box::new(Nil))))));
}

示例 15-5：為了擁有已知大小而使用 Box<T> 的 List 定義

Cons 成員將會需要一個 i32 的大小加上儲存 box 指針數(shù)據(jù)的空間。Nil 成員不儲存值，所以它比 Cons 成員需要更少的空間?，F(xiàn)在我們知道了任何 List 值最多需要一個 i32 加上 box 指針數(shù)據(jù)的大小。通過使用 box ，打破了這無限遞歸的連鎖，這樣編譯器就能夠計算出儲存 List 值需要的大小了。圖 15-2 展示了現(xiàn)在 Cons 成員看起來像什么：

圖 15-2：因為 Cons 存放一個 Box 所以 List 不是無限大小的了

box 只提供了間接存儲和堆分配；他們并沒有任何其他特殊的功能，比如我們將會見到的其他智能指針。它們也沒有這些特殊功能帶來的性能損失，所以他們可以用于像 cons list 這樣間接存儲是唯一所需功能的場景。我們還將在第十七章看到 box 的更多應(yīng)用場景。

Box<T> 類型是一個智能指針，因為它實(shí)現(xiàn)了 Deref trait，它允許 Box<T> 值被當(dāng)作引用對待。當(dāng) Box<T> 值離開作用域時，由于 Box<T> 類型 Drop trait 的實(shí)現(xiàn)，box 所指向的堆數(shù)據(jù)也會被清除。讓我們更詳細(xì)的探索一下這兩個 trait。這兩個 trait 對于在本章余下討論的其他智能指針?biāo)峁┑墓δ苤?，將會更為重要?br>