使用 Box<T> 指向堆積上的資料

使用 `Box<T>` 指向堆積上的資料

最直白的智慧指標是 box 其型別為 Box<T>。Box 允許你儲存資料到堆積上，而不是堆疊。留在堆疊上的會是指向堆積資料的指標。你可以回顧第四章瞭解堆疊與堆積的差別。

Box 沒有額外的效能開銷，就只是將它們的資料儲存在堆積上而非堆疊而已。不過相對地它們也沒有多少額外功能。你大概會在這些場合用到它們：

當你有個型別無法在編譯時期確定大小，而你又想在需要知道確切大小的情況下使用該型別的數值。
當你有個龐大的資料，而你想要轉移所有權並確保資料不會被拷貝。
當你想要擁有某個值，但你只在意該型別有實作特定的特徵，而不是何種特定型別。

我們會在「透過 Box 建立遞迴型別」段落解說第一種情形。而在第二種情形，轉移龐大的資料的所有權可能會很花費時間，因為在堆疊上的話會拷貝所有資料。要改善此情形，我們可以用 box 將龐大的資料儲存在堆積上。這樣就只有少量的指標資料在堆疊上被拷貝，而其參考的資料仍然保留在堆積上的同個位置。第三種情況被稱之為特徵物件（trait object），第十七章會花整個「允許不同型別數值的特徵物件」段落來討論此議題。所以你在此學到的到第十七章會再次用上！

使用 `Box<T>` 儲存資料到堆積上

在我們討論 Box<T> 在堆積儲存空間上的使用場合前，我們會先介紹語法以及如何對 Box<T> 內儲存的數值進行互動。

範例 15-1 顯示如何使用 box 在堆積上儲存一個 i32 數值：

檔案名稱：src/main.rs

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

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

我們定義了變數 b 其數值為 Box 配置在堆積上指向的數值 5。程式在此例會印出 b = 5，在此例中我們可以用在堆疊上相同的方式取得 box 的資料。就像任何有所有權的數值一樣，當 box 離開作用域時會釋放記憶體，在此例就是當 b 抵達 main 結尾的時候。釋放記憶體作用於 box（儲存在堆疊上）以及其所指向的資料（儲存在堆積上）。

將單一數值放在堆積上的確沒什麼用處，所以你不會對這種類型經常使用 box。在大多數情況下將像 i32 這種單一數值預設儲存在堆疊的確比較適合。

透過 Box 建立遞迴型別

遞迴型別（recursive type）的數值可以用相同型別的其他數值作為自己的一部分。遞迴型別對 Rust 來說會造成問題，因為 Rust 得在編譯期間時知道型別佔用的空間。由於這種巢狀數值理論上可以無限循環下去，Rust 無法知道一個遞迴型別的數值需要多大的空間。然而 box 則有已知大小，所以將 box 填入遞迴型別定義中，你就可以有遞迴型別了。

讓我們來探索 cons list 來作為遞迴型別的範例。這是個在函式程式語言中常見的資料型別，很適合作為遞迴型別的範例。我們要定義的 cons list 型別除了遞迴的部分以外都很直白，因此這個例子的概念在往後你遇到更複雜的遞迴型別時會很實用。

更多關於 Cons List 的資訊

cons list 是個起源於 Lisp 程式設計語言與其方言的資料結構，用巢狀配對組成，相當於 Lisp 版的鏈結串列（linked list）。這名字來自於 Lisp 中的 cons 函式（「construct function」的縮寫），它會從兩個引數建構一個新的配對，而這通常包含一個數值與另一個配對。對其呼叫 cons 就我們能建構出擁有遞迴配對的 cons list。

舉例來說，以下是個 cons list 的範例，包含了用括號包起來的 1、2、3 列表配對：

(1, (2, (3, Nil)))

每個 cons list 的項目都包含兩個元素：目前項目的數值與下一個項目。列表中的最後一個項目只會包含一個數值叫做 Nil，並不會再連接下一個項目。cons list 透過遞迴呼叫 cons 函式來產生。表示遞迴終止條件的名稱為 Nil。注意這和第六章提到的「null」或「nil」的概念不全然相同，這些代表的是無效或空缺的數值。

在 Rust 中 cons lists 不是常見的資料結構。大多數當你在 Rust 需要項目列表時，Vec<T> 會是比較好的選擇。而其他時候夠複雜的遞迴資料型別確實在各種特殊情形會很實用，不過先從 cons list 開始的話，我們可以專注探討 box 如何讓我們定義遞迴資料型別。

範例 15-2 包含了 cons list 的列舉定義。注意到此程式碼還不能編譯過，因為 List 型別並沒有已知的大小，我們接下來會繼續說明。

檔案名稱：src/main.rs

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

fn main() {}

範例 15-2：第一次嘗試定義一個列舉來代表有 i32 數值的 cons list 資料結構

注意：我們定義的 cons list 只有 i32 數值是為了範例考量。我們當然可以使用第十章討論過的泛型來定義它，讓 cons list 定義的型別可以儲存任何型別數值。

使用 List 型別來儲存 1, 2, 3 列表的話會如範例 15-3 的程式碼所示：

檔案名稱：src/main.rs

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

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 數值是另一個 Cons 數值且持有 2 與另一個 List 數值。此 List 數值是另一個 Cons 數值且擁有 3 與一個 List 數值，其就是最後的 Nil，這是傳遞列表結尾訊號的非遞迴變體。

如果我們嘗試編譯範例 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>),
  |               ++++    +

For more information about this error, try `rustc --explain E0072`.
error: could not compile `cons-list` due to previous error

範例 15-4：嘗試定義遞迴列舉所得到的錯誤

錯誤顯示此型別的「大小為無限」，原因是因為我們定義的 List 有個變體是遞迴：它直接存有另一個相同類型的數值。所以 Rust 無法判別出它需要多少空間才能儲存一個 List 的數值。讓我們進一步研究為何會得到這樣的錯誤，首先來看 Rust 如何決定要配置多少空間來儲存非遞迴型別。

計算非遞迴型別的大小

回想一下第六章中，當我們在討論列舉定義時，我們在範例 6-2 定義的 Message 列舉：

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

fn main() {}

要決定一個 Message 數值需要配置多少空間，Rust 會遍歷每個變體來看哪個變體需要最大的空間。Rust 會看到 Message::Quit 不佔任何空間、Message::Move 需要能夠儲存兩個 i32 的空間，以此類推。因為只有一個變體會被使用，一個 Message 數值所需的最大空間就是其最大變體的大小。

將此對應到當 Rust 嘗試檢查像是範例 15-2 的 List 列舉來決定遞迴型別需要多少空間時，究竟會發生什麼事。編譯器先從查看 Cons 的變體開始，其存有一個 i32 型別與一個 List 型別。因此 Cons 需要的空間大小為 i32 的大小加上 List 的大小。為了要瞭解 List 型別需要的多少記憶體，編譯器再進一步看它的變體，也是從 Cons 變體開始。Cons 變體存有一個型別 i32 與一個型別 List，而這樣的過程就無限處理下去，如圖示 15-1 所示。

圖示 15-1：無限個 List 包含著無限個 Cons 變體

使用 `Box<T>` 取得已知大小的遞迴型別

由於 Rust 無法判別出遞迴定義型別要配置多少空間，所以編譯器會針對此錯誤提供些實用的建議：

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

在此建議中，「indirection」代表與其直接儲存數值，我們可以變更資料結構，間接儲存指向數值的指標。

因為 Box<T> 是個指標，Rust 永遠知道 Box<T> 需要多少空間：指標的大小不會隨著指向的資料數量而改變。這代表我們可以將 Box<T> 存入 Cons 變體而非直接儲存另一個 List 數值。Box<T> 會指向另一個存在於堆積上的 List 數值而不是存在 Cons 變體中。概念上我們仍然有建立一個持有其他列表的列表，但此實作更像是將項目接著另一個項目排列，而非包含另一個在內。

我們可以改變範例 15-2 的 List 列舉定義以及範例 15-3 List 的使用方式，將其寫入範例 15-5，這次就能夠編譯過了：

檔案名稱：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 指標的空間。Nil 變體沒有儲存任何數值，所以它需要的空間比 Cons 變體少。現在我們知道任何 List 數值會佔的空間都是一個 i32 加上 box 指標的大小。透過使用 box，我們打破了無限遞迴，所以編譯器可以知道儲存一個 List 數值所需要的大小。圖示 15-2 顯示了 Cons 變體看起來的樣子。

圖示 15-2：不再是無限大小的 List，因為其 Cons 存的是 Box

Boxes 只提供了間接儲存與堆積配置，它們沒有其他任何特殊功能，比如我們等下就會看到的其他智慧指標型別。它們也沒有任何因這些特殊功能產生的額外效能開銷，所以它們很適合用於像是 cons list 這種我們只需要間接儲存的場合。我們在第十七章還會再介紹到更多 box 的使用情境。

Box<T> 型別是智慧指標是因為它有實作 Deref 特徵，讓 Box<T> 的數值可以被視為參考所使用。當 Box<T> 數值離開作用域時，該 box 指向的堆積資料也會被清除，因為其有 Drop 特徵實作。這兩種特徵對於本章將會討論的其他智慧指標型別所提供的功能，將會更加重要。讓我們來探討這兩種特徵的細節吧。

Rust 程式設計語言

使用 Box<T> 儲存資料到堆積上

透過 Box 建立遞迴型別

更多關於 Cons List 的資訊

計算非遞迴型別的大小

使用 Box<T> 取得已知大小的遞迴型別