「Learn Rust With Entirely Too Many Linked Lists」を読んだ記録

Rustが好きと書いておきながら、「Learn Rust With Entirely Too Many Linked Lists」を知らなかったので読んでみます。これはその記録です。

「1. Introduction」では連結リストの使いどころって少ないはずというのを訴えている様子(正しく読めていれば)。

「2. A Bad Stack」

• std::boxedに書いてある連結リストの実装だと、分割・結合時に無駄が生じる
  • 最後の要素に、次がList::Emptyであることを示さなければいけない
  • List::EmptyもList型と同じ大きさを持ってしまう
• 0か0でないかという持ち方をすればnullポインタ最適化が行われて嬉しい
  • そのために、データは連結リストの外側で持ったほうが良い
• std::mem::replaceを使うことで一時的なmoveを避けることができる
• 自動的に実装されるDropだとBoxの都合で末尾再帰にできないため、先頭から順にLink::Emptyに置き換える必要がある

「3. An Ok Stack」はOptionを使うようになったのとイテレータの実装。IntoIteratorの実装にIntoIterを使ったのはIterとかIterMutと合わせるため？

「4. A Persistent Stack」

• std::rc::Rcでも最後の参照であればOption::takeと同様のことができる

「5. A Bad but Safe Doubly-Linked Deque」

• 要素を追加するたびに参照カウンタが2つ増えてしまう
• std::rc::RefCellからimmutable referenceがほしいとき、その型は&TではなくRef<T>となる
• この方法だとIteratorの実装ができない

「6. An Ok Unsafe Queue」

• "pop"した際に必ずtailの指す先も変えないといけないが、それはunsafeでプログラマが責任を負うしかない
• miriを使えばunsafeなコードをある程度チェックしてくれる

「6. An Ok Unsafe Queue」

• "pop"した際に必ずtailの指す先も変えないといけないが、それはunsafeでプログラマが責任を負うしかない
• miriを使えばunsafeなコードをある程度チェックしてくれる

「7. A Production Unsafe Deque」

• "Variance"という概念がある(正直難しくてよくわからない)
  • この記事が参考になりそう
• "covariant"にしたいが*mut Tを持つ構造体は"invariant"になってしまう
• std::ptr::NonNullは生のポインタを*const Tとして持っているため"covariant"
• unsafeなコードを書くときはpanic!時の挙動にも気を使う必要がある
  • debug_assert!によってpanic!になりうる箇所が増えるのはむしろ危険なことがある
• コレクション系でstd::hash::Hashを実装するときは、lenもハッシュ値の計算に用いないと、区切り方が異なるコレクションでも同じハッシュ値となってしまう