RustのLinked ListのサンプルでBox<T>の使い方を学習した

Tatsuya Nakano
ゲーム
無料

apps.apple.com

Linked ListのサンプルでBoxの使い方が出ていて、理解が深まったので備忘録として置いておきます。

コード

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()メソッドがあり、これを呼び出すにはT::len()を実装してあげないといけないみたいです。なので実態はBox::len()が呼ばれるので、List::len()が呼ばれる仕組みです。
もし実装していないと以下のようなエラーが出ます。

the method `len` exists but the following trait bounds were not satisfied:

個人的メモ

refと&の違いがわかっていない。
&と*をなぜ使い分けたかわかっていない。

TAKOYAKING’s blog

たこ焼き系

RustのLinked ListのサンプルでBox<T>の使い方を学習した

コード

Box

なぜBoxを使用するのか？

感想

本筋とは関係なけど気になったコード

個人的メモ