Linked ListのサンプルでBox
コード
テストケース: 連結リスト | Rust by Example
ここより拝借
use List::*; enum List { // Cons: これは、要素をラップし、次の要素へのポインタを保持するタプル。 Cons(u32, Box<List>), // Nil: 連結リストの終端であることを示すノード Nil, } // 列挙型にはメソッドを付与することができる。 impl List { // 空リストの作成。 fn new() -> List { // `Nil` は `List`型を持つ。 Nil } // リストを受け取り、その始端に新しい要素を付加したものを返す関数。 fn prepend(self, elem: u32) -> List { // この`Cons` 自体も、その第2要素もどちらもlist型である。 Cons(elem, Box::new(self)) } // list の長さを返すメソッド fn len(&self) -> u32 { // このメソッドは、`self`の状態によって振る舞いが // 変化するため、matchをする必要がある。 // `self`の型は`&List`であるので、`*self`は`List`になる。マッチングは // リファレンス(`&T`)ではなく実体(`T`)に対して行うのが好ましい。 match *self { // `self`をすでに借用しているので、tailの所有権を取ることができない。 // 代わりに参照を使用する。 Cons(_, ref tail) => 1 + tail.len(), // 空リストならば長さは0 Nil => 0 } } // Listをheap上の文字列として表したものを返すメソッド。 fn stringify(&self) -> String { match *self { Cons(head, ref tail) => { // `format!`は`print!`に似ているが、コンソール上に出力 // する代わりに、heap上の文字列を返す。 format!("{}, {}", head, tail.stringify()) }, Nil => { format!("Nil") }, } } } fn main() { // 空の連結リストを作成 let mut list = List::new(); // 要素を追加 list = list.prepend(1); list = list.prepend(2); list = list.prepend(3); // 追加後の状態を表示 println!("linked list has length: {}", list.len()); println!("{}", list.stringify()); }
Box
引用
ボックスは、間接参照とヒープメモリ確保だけを提供します。他のスマートポインタ型で目撃するような、 他の特別な能力は何もありません。これらの特別な能力が招くパフォーマンスのオーバーヘッドもないので、 間接参照だけが必要になる唯一の機能であるコンスリストのような場合に有用になり得ます。 より多くのボックスのユースケースは第17章でもお見かけするでしょう。
ユースケースをたくさん見た方が良い気がしてきましたが、ここでは再帰のユースケースを見ました。
Rustの思想ゆえに、こんなシンプルな機能になっているんだろうなと思いました。
なぜBoxを使用するのか?
Box<T>はヒープのデータを指し、既知のサイズである - The Rust Programming Language
解説はここにあって、まとめると
- コンパイラは事前に使用される領域のサイズを知る必要がある
- Linked Listは再帰的なデータ構造型になるのでRustはコンパイル時にサイズを知ることはできない
- 代わりに、Box
というポインタ型にしてしまうことで事前にサイズを計算することを可能にする
なるほどと思ってしまいました。確かにもしデータ構造を以下のように定義すると
enum List { Cons(i32, List), Nil, }
無限ループでサイズを計算しないといけないことになってしまうので事前に計算できない。
感想
再帰の使用例しかまだ見ていないので他にも使いどころがきっとあるんだろうと思いながら、Rust勉強しなかったら、こんなこと考えもしなかっただろうなと思いました!
先はまだまだ長い!
本筋とは関係なけど気になったコード
- len
- stringify
Box::len()が呼ばれるので、List::len()が呼ばれる仕組みです。
もし実装していないと以下のようなエラーが出ます。
the method `len` exists but the following trait bounds were not satisfied:
個人的メモ
- refと&の違いがわかっていない。
- &と*をなぜ使い分けたかわかっていない。