データ構造を制する者はアルゴリズムを制する。
Rustのデータ構造について、日本語で詳しく書いている情報が無かったので調べました。
全部だとキリがないので、今回はベクターのみをまとめました。
そのうち別のやつもまとめます。
ベクターの長さとサイズ
まずベクターを作る。
作り方には2通りあって、newで作る方法と、with_capacityで初期サイズを指定して作る方法がある。
サイズを指定した方は、長さが指定サイズ以内なら領域の再確保(reallocate)が起きない。
let mut vec: Vec<i32> = Vec::new();
let mut vec_cap: Vec<i32> = Vec::with_capacity(100);
for i in 0..10 {
vec.push(i);
vec_cap.push(i);
}
assert!(vec == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
assert!(vec.len() == 10);
assert!(vec_cap.len() == 10);
assert!(vec.capacity() == 16);
assert!(vec_cap.capacity() == 100);
ベクターのサイズを縮小
メモリ使用量削減のため、ベクターのサイズを現在使われている大きさまで縮小する。
この後に要素を追加すると領域の再確保が起きる。
vec_cap.shrink_to_fit();
assert!(vec_cap.capacity() == 10);
ベクターの要素を削除
要素を削除する方法は複数ある。
一般的な削除法である、指定位置の要素を削除してから残りの要素を左にシフトする方式はremoveだ。
assert!(vec.remove(3) == 3);
assert!(vec.remove(6) == 7);
assert!(vec == [0, 1, 2, 4, 5, 6, 8, 9]);
また、指定位置の要素を削除してから一番最後の要素で詰める方法がある。
アクセスする回数が少ない分、上記よりはこっちの方が速い。計算量はO(1)。
assert!(vec.swap_remove(2) == 2);
assert!(vec == [0, 1, 9, 4, 5, 6, 8]);
assert!(vec.swap_remove(2) == 9);
assert!(vec == [0, 1, 8, 4, 5, 6]);
クロージャーに合致しない要素を削除する方法がある。
いわゆる関数型言語のfilterと同じ。
vec.retain(|&x| x > 4);
assert!(vec == [8, 5, 6]);
連続する重複要素を削除する方法。
ベクターがソートされていれば、全ての重複が削除される。
vec = vec![0, 1, 1, 2, 3, 2, 5, 7, 7, 7];
vec.dedup();
assert!(vec == [0, 1, 2, 3, 2, 5, 7]);
配列を空にするにはclearを実行すれば良い。
vec.clear();
assert!(vec.is_empty());
ベクターに要素を追加する
ベクターに要素を追加する方法は追加する位置や要素によって異なる。
まずベクターの最後尾に要素を追加する方法。
vec.push(3);
vec.push(5);
vec.push(7);
assert!(vec == [3, 5, 7]);
複数要素を追加したい場合は以下のようにする。
vec.extend_from_slice(&[2, 4, 6]);
assert!(vec == [3, 5, 7, 2, 4, 6]);
上に似た手段として、appendというのがある。
ただし追加したベクターは空になる。つまり吸収される。
let mut v = vec![1, 2, 3];
vec.append(&mut v);
assert!(vec == [3, 5, 7, 2, 4, 6, 1, 2, 3]);
assert!(v.is_empty());
指定位置に要素を追加したい場合はこうする。
vec.insert(3, 0);
vec.insert(7, 0);
assert!(vec == [3, 5, 7, 0, 2, 4, 6, 0, 1, 2, 3]);
ベクターから要素を取得する
単純なインデックス以外の方法を見ていく。
以下でベクターの後ろから要素を取り出す。
assert!(vec.pop() == Some(3));
assert!(vec == [3, 5, 7, 0, 2, 4, 6, 0, 1, 2]);
assert!(vec.pop() == Some(2));
assert!(vec == [3, 5, 7, 0, 2, 4, 6, 0, 1]);
また、指定位置以降を切り落とす方法がある。
assert!(vec.split_off(7) == [0, 1]);
assert!(vec == [3, 5, 7, 0, 2, 4, 6]);
ベクターの先頭の要素の参照を得るにはこうする。
assert!(vec.first() == Some(&3));
assert!(vec == [3, 5, 7, 0, 2, 4, 6]);
同様に最後の要素の参照を得ることも出来る。
assert!(vec.last() == Some(&6));
assert!(vec == [3, 5, 7, 0, 2, 4, 6]);
Consセルのように、ベクターの先頭と残りの要素をsliceの形で取得する。
v = vec![2, 4, 6, 8];
let cons = v.split_first().unwrap();
assert!(cons.0 == &2);
assert!(cons.1 == &[4, 6, 8]);
assert!(v == [2, 4, 6, 8]);
ベクターの要素を安全に取得したい場合は以下のようにする。
この方法なら領域外を参照することを未然に防ぐことが出来る。
assert!(vec.get(3) == Some(&0));
assert!(vec.get(10) == None); // 領域外を参照しようとするとNoneが返る
assert!(vec == [3, 5, 7, 0, 2, 4, 6]);
ベクターを指定した数の要素のかたまりとして取り出すには以下のようにする。
余った要素のかたまりは指定した長さとはならない。
for chunk in vec.chunks(3) {
println!("{:?}", chunk);
}
// 出力
// [3, 5, 7]
// [0, 2, 4]
// [6]
指定した位置で分割して、タプルで返すメソッド。
assert!(vec.split_at(3) == (&[3, 5, 7], &[0, 2, 4, 6]));
assert!(vec == [3, 5, 7, 0, 2, 4, 6]);
条件に合致する要素を区切りとして分割するメソッド。
for group in vec.split(|x| *x == 0) {
println!("{:?}", group);
}
// 出力
// [3, 5, 7]
// [2, 4, 6]
上記のsplitに分割数の制限を設けたメソッドもある。
for group in vec.splitn(3, |x| *x > 3) {
println!("{:?}", group);
}
// 出力
// [3]
// []
// [0, 2, 4, 6]
以下はそれをベクターの後ろから実行するメソッド。
for group in vec.rsplitn(3, |x| *x > 3) {
println!("{:?}", group);
}
// 出力
// []
// []
// [3, 5, 7, 0, 2]
ベクターに要素が含まれるか調べる
ベクターに指定要素が含まれるか調べるには以下のようにする。
assert!(vec.contains(&2));
assert!(!vec.contains(&10));
ベクターが指定した要素で始まるかを調べたい場合はこう。
assert!(vec.starts_with(&[3, 5]));
assert!(vec.starts_with(&[1, 2]));
逆に、指定した要素で終わるかを調べるならこう。
assert!(vec.ends_with(&[4, 6]));
assert!(!vec.ends_with[&[2, 4]]);
ベクターを操作する
ベクターの要素を交換する。
vec.swap(0, 4);
assert!(vec == [2, 5, 7, 0, 3, 4, 6]);
ベクターを反転する。
vec.reverse();
assert!(vec == [6, 4, 3, 0, 7, 5, 2]);
ベクターをソートする。
vec.sort();
assert!(vec == [0, 2, 3, 4, 5, 6, 7]);
ベクターをバイナリサーチする。
assert!(vec.binary_search(&4) == Ok(3usize));
指定したキーの要素をバイナリサーチ。
(Rust >= 1.10.0)
let mut vec_key: Vec<(i32, i32)> = vec![(0,0), (1,1), (2,2),
(0,3), (1,4), (2,5),
(0,6), (1,7), (2,8)];
assert!(vec_key.binary_search_by_key(&7, |&(a,b)| b) == Ok(7usize));
指定したキーの要素でソート。
vec_key.sort_by_key(|&(a,b)| a);
assert!(vec_key == vec![(0,0), (0,3), (0,6),
(1,1), (1,4), (1,7),
(2,2), (2,5), (2,8)]);
以上がベクターで利用出来るほぼ全てのメソッドだ。
挙げきれていないものもあるが、一般的な用途としては十分だろう。また、参照を得るメソッドは_mutを付けると変更可能な参照を得られるものもある。