『みんなのデータ構造』
なぜこの本を読むか
やりたいことリストの第一弾として、難易度も高くなく、かつ自分で実装もできそうなものとして選んだ すごい人はデータ構造に詳しい人が多いのと、自分はあまりデータ構造に詳しくないので、勉強したい メモ
1回目読んだ
これちゃんとやればかなり力つきそう、というイメージを持った
実装、証明のところは今回はほとんど読み飛ばした
2回目は実装しながら読みたい
難易度は思ったよりも高かったけど、じっくりやれば大丈夫そう
PFDSより丁寧だし…
演習もけっこうある
自分で実装して演習も全部やるなら、数ヶ月は最低でもかかりそう
とりあえず最初の一個を実装してみると、後のハードルがだいぶ下がるので早めにやりたい
実装
Rust でやりたい
双方向リストが厳しいという話は聞いてたけど
まあ unsafe の練習と思えば
いきなり array でつまずいた
Rust の配列は動的なサイズで作ることができない
かといってVecを使うと勝手にリサイズとかされてしまう
RawVec相当のを自分で作る必要がある
boxed slice で十分かも
イントロダクション
インタフェースと実装
インタフェースはそれが何をするか
実装はそれをどうやるか
note.icon この本では破壊的操作をするようだ
キュー
最初に入れた要素を取り出す (FIFO)
優先度付きキュー
最小の要素を取り出す
スタック
最後に入れた要素を取り出す (LIFO)
Deque
双方向キュー
先頭に入れたり取り除いたり、最後に入れたり取り除いたりできる
List インタフェース
size(), get(i), set(i, x), add(i, x), remove(i)
Queue, Stack, Deque は List としてまとめられる
question.icon Queue、Stack、Deque を List として使うことできなくない？(効率悪くてもよければできそうだけど)
List を Queue にできる、ということだろうか
でも「Stack と Deque を List インタフェースを実装したデータ構造の名前として」と書いてあるし、逆ではなさそうではある
読み間違いしてそうな気もする
USet インタフェース
unordered set
size(), add(x), remove(x), find(x)
find は集合に x が入っていたらそれを見つける
Map とか
Map では find(x) はキーから値を取り出す操作になる
SSet インタフェース
sorted set
USet のメソッドと同じ
find(x) は y >= x を満たす最小の y を見つける
後継探索というらしい
…こんな粒度でメモしてたら終わらんし丸写しになってしまってよくない
配列を使ったリスト
backing array
「裏でも」あ、たぶんインタフェースに隠された裏側のこと、だと思う