基本データ設計

よし，で，連結リストってなんでしょう？えー，基本的にはヒープに割り当てられたデータの山で（カーネル勢はちょっと黙っててください），それぞれが順番に互いのポインタを持っています．連結リストは，手続き型言語のプログラマが10m以内に近づかないものであり，関数型言語のプログラマがあらゆる用途に使うものです．それなら，関数型言語のプログラマにどんなものか説明してもらうのがよさそうですね．彼らはこんな感じの定義をよこすでしょう：

List a = Empty | Elem a (List a)

これはだいたい「リストは空か，リストが後ろにつながった要素である」みたいな感じに読めます． 直和型を用いた再起的な定義ですね．直和型というのは「異なる型の値を持つことができる型」のことです．Rustでは直和型はenumに相当します！もしCライクな言語に慣れているなら， Rustのenumはあなたが大好きなあのenumそのものです．じゃあ上の関数型の定義をRustっぽく書き換えてみましょう！

とりあえず話を簡単にするためにジェネリクスは使わず，32bit intだけを要素として持つことにします：

// in first.rs

// pubはListが外部から使えることを意味します
pub enum List {
    Empty,
    Elem(i32, List),
}

ぬわ疲．それじゃコンパイルしましょう：

> cargo build

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

えっと，あなたはどうか分かりませんが私は関数型界隈に裏切られた気分です．

エラーメッセージを見てみると（裏切られた絶望を乗り越えたあとで），rustcはまさにエラーを解決する方法を示しています：

insert indirection (e.g., a Box, Rc, or &) at some point to make first::List representable

おっけー，boxね．何それ？ググってみましょう．rust box...

std::boxed::Box - Rust

これかな...

pub struct Box<T>(_);

A pointer type for heap allocation.
See the module-level documentation for more.

リンクをクリックする

Box<T>, casually referred to as a 'box', provides the simplest form of heap allocation in Rust. Boxes provide ownership for this allocation, and drop their contents when they go out of scope.

Examples

Creating a box:

let x = Box::new(5);

Creating a recursive data structure:

（訳） Box<T>，通称BoxはRustにおける最も単純なヒープ割当を行います．Boxは割り当てられたメモリの所有権を持ち，内容物はBoxがスコープから外れたときにdropされます．

使用例

Boxを作る：

let x = Box::new(5);

再帰的なデータ構造を作る：
#[derive(Debug)]
enum List<T> {
    Cons(T, Box<List<T>>),
    Nil,
}

let list: List<i32> = List::Cons(1, Box::new(List::Cons(2, Box::new(List::Nil))));
println!("{:?}", list);
This will print Cons(1, Box(Cons(2, Box(Nil)))).

Recursive structures must be boxed, because if the definition of Cons looked like this:

Cons(T, List<T>),

It wouldn't work. This is because the size of a List depends on how many elements are in the list, and so we don't know how much memory to allocate for a Cons. By introducing a Box, which has a defined size, we know how big Cons needs to be.

（訳）これはCons(1, Box(Cons(2, Box(Nil))))をprintします．

再帰的なデータ構造はBoxを持たなくてはいけません．もしConsの定義がこのようであった場合：

Cons(T, List<T>),

これは動きません．なぜならListの大きさはその要素数によるため，Consのためにどのくらいメモリを割り当てればよいか分からないからです．定義された大きさを持つBoxを使うことで，どのくらいConsが大きければよいかあらかじめ知ることができます．

わお，うん．多分今まで見た中で一番知りたいことが書いてあるドキュメントですね．ドキュメントのまさに最初に書いてあるのは私達がやろうとしていたことそのものと，なぜそれが動かないのかと，どうやって直すかです．

ドキュメントが強すぎる．

よし，じゃあやってみましょう：

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

> cargo build

   Finished dev [unoptimized + debuginfo] target(s) in 0.22s

やった，ビルドが通りました！

...でもちょっと考えてみるとこれはかなりバカっぽいリストです．

要素が2つあるリストを考えてみましょう．

[] = スタック
() = ヒープ

[要素A, ポインタ] -> (要素B, ポインタ) -> (Empty *ゴミ*)

問題は2つあります：

最後のノードは「僕は実はノードじゃないヨ」を意味するデータを割り当てられている．
最初のノードは全くヒープのメモリ空間を割り当てられていない．

表面的には，これらは互いに打ち消し合っているように見えます．一方で追加のノードを割当て，もう一方では割り当てていない...でも次のようなデータ構造を見てみましょう：

[ポインタ] -> (要素A, ポインタ) -> (要素B, *null*)

この構成では要素数に関わらず各要素のためにヒープのメモリ空間を割り当てます．重要な違いは一つ目の設計にあったゴミがないことです．このゴミはなんなのでしょうか？それを知るために，enumがどのようにメモリに割り当てられるか見てみましょう．

一般にenumはこんな感じです：

enum Foo {
    D1(T1),
    D2(T2),
    ...
    Dn(Tn),
}

Fooはどの列挙子（D1, D2, .. Dn）であるかを表す整数をもつ必要があります．これが enumのタグです．それに加え，T1, T2, .. Tnのうち最大のものが入るメモリ空間が必要になります（あとメモリの整列のためのパディング）．

ここで発生している大いなるムダは，Emptyがたった1bitの情報であるにもかかわらずポインタ1個と要素1個分のメモリが必要であることです．Elemにいつ変換されてもいいようにしなくてはならないのです．そんなわけで1つ目の設計ではゴミデータを割り当てざるを得ず，2つ目の構成より若干大きいスペースが必要になります．

ノードの一つがヒープにないのも，常に全ノードがヒープに割り当てられるより，多分ビビるほど悪いです．ノードの扱いが統一的でないと，pushやpopではそれほど困らないかもしれませんが分割や結合の際に厄介なことになります．

それぞれの設計でリストを分割することを考えてみましょう：

設計1:

[要素A, ポインタ] -> (要素B, ポインタ) -> (要素C, ポインタ) -> (Empty *ゴミ*)

Cを分割:

[要素A, ポインタ] -> (要素B, ポインタ) -> (Empty *ゴミ*)
[要素C, ポインタ] -> (Empty *ゴミ*)

設計2:

[ポインタ] -> (要素A, ポインタ) -> (要素B, ポインタ) -> (要素C, *null*)

Cを分割:

[ポインタ] -> (要素A, ポインタ) -> (要素B, *null*)
[ポインタ] -> (要素C, *null*)

設計2では要素Bのポインタをスタックにコピーして，元あった場所をnullにするだけです．設計1でも同じことをしていますが，要素Cをヒープからスタックにコピーする必要があります．結合は同じことを逆にやるだけです．

連結リストの数少ない良いところのひとつに要素をノード自体の中で組み立て，メモリ空間を移動させずに順番を入れ替える事ができる点があります．ポインタをいじるだけでリスト内の順番が動くのです．設計1はこの特長を持ちません．

はい，設計1がクソなことが証明されました．ではどう書き直せばいいでしょうか？じゃあこんな感じで：

pub enum List {
    Empty,
    ElemThenEmpty(i32),
    ElemThenNotEmpty(i32, Box<List>),
}

悪化してるように見えたなら良かったです．特筆すべき点は，この設計はElemThenNotEmpty(0, Box(Empty)) というまったく無意味な状態を持てるようになっており，ロジックを複雑にしていることです．しかも相変わらずノードがスタックにあったりヒープにあったりします．

とはいえ，この設計はひとつ興味深い特徴を持っています：Emptyの状態がなく，ヒープの割当が1要素分小さいことです．不幸にもそれによって更に大きいメモリ空間を無駄にしているんですけどね！なぜかというと，先程の設計がヌルポインタ最適化を行っているからです．

さっきenumはどの列挙子を持つかを管理するタグを持っていると言いました．しかし，このような特別な形のenumについては：

enum Foo {
    A,
    B(ContainsANonNullPtr),
}

ヌルポインタ最適化が行われ，タグのためにはメモリ空間が使われなくなります．列挙子Aのとき enumはすべて0が割り当てられ，そうでないとき列挙子Bが割り当てられます．列挙子Bはnullでないポインタを含むため，中身が全て0ということはあり得ないのでこういう事ができるのです．かっこいい！

他にこういう最適化ができるenumの形はどんなのがあるか思いつきますか？実はいっぱいあります！これがRustがenumのメモリレイアウトを定義しない理由です．他にもいくつか複雑なRustの enumメモリレイアウト最適化戦略がありますが，ヌルポインタ最適化が明らかに一番重要です！ヌルポインタ最適化によって&, &mut, Box, Rc, Arc, VecなどをOption に入れてもオーバーヘッドが発生しません（これらの型についてはおいおい触れます）．

で，どうすればゴミデータの割当を防ぎ，統一的にメモリを割り当たうえでヌルポインタ最適化の恩恵を得ることができるでしょうか？要素を持つということとリストを新しく割り当てるということを切り離して考えるほうがよさそうです．そのためにはCライクな構造体についてもう少し考えなくてはいけません！

enumがいくつかある値のひとつを保持する型なら，構造体は複数を一度に保持する型です．リストを2つの型に分割しましょう．ListとNodeです．

さっきと同様Listは空（Empty）かリストが後ろにくっついた要素です．「リストが後ろにくっついた要素」を別の型で表現することでBoxをさらに最適化された状態にもっていくことができます：

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

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

ちゃんとできてるか確認してみましょう：

リストの末尾にゴミがない：OK!
enumがヌルポインタ最適化されている：OK!
ノードが統一的に割り当てられる：OK!

よし！これで問題があった（ことがRustの公式ドキュメントに指摘された）はじめの設計の問題点を克服しました．

> cargo build

warning: private type `first::Node` in public interface (error E0446)
 --> src/first.rs:8:10
  |
8 |     More(Box<Node>),
  |          ^^^^^^^^^
  |
  = note: #[warn(private_in_public)] on by default
  = warning: this was previously accepted by the compiler but
    is being phased out; it will become a hard error in a future release!

またRustに怒られました．Listを（外部から使ってほしいので）publicにしましたがNode をpublicにはしていませんでした．問題は，publicなenumの中は全てpublicでなくてはならないことです． Nodeをpublicにすることもできますが，一般にRustでは実装の詳細を隠蔽することが好まれます． Listを構造体にすることで実装の詳細を隠すことにしましょう：

pub struct List {
    head: Link,
}

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

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

Listはフィールドがひとつしかない構造体なので，サイズはフィールドと同じになります．ゼロコスト抽象化です．イエーイ！

> cargo build

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

warning: variant is never constructed: `Empty`
 --> src/first.rs:6:5
  |
6 |     Empty,
  |     ^^^^^

warning: variant is never constructed: `More`
 --> src/first.rs:7:5
  |
7 |     More(Box<Node>),
  |     ^^^^^^^^^^^^^^^

warning: field is never used: `elem`
  --> src/first.rs:11:5
   |
11 |     elem: i32,
   |     ^^^^^^^^^

warning: field is never used: `next`
  --> src/first.rs:12:5
   |
12 |     next: Link,
   |     ^^^^^^^^^^

よっしゃ，コンパイルが通りました！Rustは私達が作ったものが完全に無駄だといってめちゃくちゃ怒ってます．headをどこでも使ってないし，プライベートフィールドなので外部からも参照できないからです．したがってLinkとNodeも同様に無意味というわけです．というわけで次はこれを解決しましょう．このリストを使うコードを実装していきましょう！

あまりにも超大量の連結リストで学ぶRust

基本データ設計