Rust勉強メモ/コレクション
Rustと他言語のコレクションの体系的な差
「プログラミングRust 第2版」p.361
移動と借用が多用される
StringをVec<String>へ格納する際、値は移動される
文字列のコピーは発生しない
無効化によるエラーが生じない
Rustでは、コレクション要素を指すポインタが生存している間にコレクションが変更されない
要素への共有参照がある間は、コレクションへの可変参照を作れないから
Nullの代わりにOptionを使う
Rustの標準コレクション8選
「プログラミングRust 第2版」p.362
table:RustとC++のコレクション対応（表16-1より）
Rust C++
Vec<T> vector
VecDeque<T> deque
LinkedList<T> list
BinaryHeap<T: Ord> priority_queue
HashMap<K: Eq + Hash, V> unordered_map
BTreeMap<K: Ord, V> map
HashSet<T: Eq + Hash> unordered_set
BTreeSet<T: Ord> set
Vec<T>のメモリレイアウト
「プログラミングRust 第2版」p.363
Vec<T>は、Tがなんであっても、3ワードの値
ヒープ上のデータ先頭のポインタ
容量
要素数
スライスの複製
「プログラミングRust 第2版」p.365
slice.to_vec()は、スライス全体を複製し新しいVecを返す
これを使うには要素型がCloneを実装している必要がある
Vec<T> where T: Clone
Vecのメソッドで気になったもの
「プログラミングRust 第2版」p.366
vec.push(value)は参照ではなく値を取り、値の所有権がvecへと移動される
vec.pop()は値を返し、値の所有権が呼び出し元へと移動される
vec.drain(range)はvecからrange範囲を削除し、削除した要素へのイテレータを返す
vec.dedup()は重複した要素をドロップする
ドロップ=所有権の解放
配列の分割
「プログラミングRust 第2版」p.369
複数の（異なる）要素へのmut参照を作りたいケース
code:Rust
*a = 6;
*b = 7;
これはコンパイルエラー
i==jのときに、同一要素の複数のmut参照になってしまう
slice.split_at_mut(index) = (&mut slice[..index], &mut slice[index..])
他にも多くの分割メソッドがある
それらは、領域が重複しないように設計されているため、mut参照のルールに違反しない
ランダムな要素
「プログラミングRust 第2版」p.374
乱数は、Rustの標準ライブラリには含まれていない。
な、なんだってー！？今どきの言語でそんなことあるんだ……
?VecDeque
「プログラミングRust 第2版」p.376
なぜこの名前？内部実装がVecを基にしているから？
ヒープ上のデータ領域をリングバッファとして用いる
BinaryHeapのイテレータ
「プログラミングRust 第2版」p.380
BinaryHeapは優先度付きキュー（要素をソートされた状態で保持する）
BinaryHeapは.iter()を持つが、要素を返す順序はランダム
大きい順に処理するには while let Some(v) = heap.pop() { ... }
?BTreeMapとエントリの数
「プログラミングRust 第2版」p.380
BTreeMapは木構造でエントリを保持する
平衡二分探索木ではなく、B-木
平衡二分探索木の方が比較回数は少ない
B-木の方がキャッシュミスが少なく高速になりやすい
例えば本当のBTreeMapには4つではなく11のエントリが格納できる。
11個にした理由は？
キャッシュラインサイズは典型的に64バイト
1エントリ5バイトなら11個収まる？
そんなに小さいとは思えない
?マップのEntry型
「プログラミングRust 第2版」p.383
特定のレコードを取得したいが、レコードが存在しなければ生成する例
code:Rust
if !student_map.contains_key(name) {
student_map.insert(name.to_string(), Student::new());
}
let record = student_map.get_mut(name).unwrap();
マップの検索が、キーが存在する場合に2回、存在しない場合に3回行われる
insertが挿入場所を探すために検索する、ということか？
?Entry型の目的
検索を減らすこと
code:Rust
let record = student_map.entry(name.to_string()).or_insert_with(Student::new);
Entry値は、指定したキーが占有しているか、占有するはずの空き地への可変参照ぽく振る舞う
entry.or_insert(value)
空き地にvalueを挿入する。mut参照を返す。
entry.or_insert_with(default_fn)
与えた関数を呼び出し、その戻り値を挿入する。
値の生成コストが高い場合に使う？