Rustのデータ構造について調べた - std::vec::Vec

データ構造を制する者はアルゴリズムを制する。

Rustのデータ構造について、日本語で詳しく書いている情報が無かったので調べました。
全部だとキリがないので、今回はベクターのみをまとめました。

そのうち別のやつもまとめます。

## ベクターの長さとサイズ

まずベクターを作る。
作り方には2通りあって、newで作る方法と、with_capacityで初期サイズを指定して作る方法がある。
サイズを指定した方は、長さが指定サイズ以内なら領域の再確保(reallocate)が起きない。

```rust
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);
```

## ベクターのサイズを縮小

メモリ使用量削減のため、ベクターのサイズを現在使われている大きさまで縮小する。
この後に要素を追加すると領域の再確保が起きる。

```rust
vec_cap.shrink_to_fit();
assert!(vec_cap.capacity() == 10);
```

## ベクターの要素を削除

要素を削除する方法は複数ある。
一般的な削除法である、指定位置の要素を削除してから残りの要素を左にシフトする方式はremoveだ。

```rust
assert!(vec.remove(3) == 3);
assert!(vec.remove(6) == 7);
assert!(vec == [0, 1, 2, 4, 5, 6, 8, 9]);
```

また、指定位置の要素を削除してから一番最後の要素で詰める方法がある。
アクセスする回数が少ない分、上記よりはこっちの方が速い。計算量はO(1)。

```rust
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と同じ。

```rust
vec.retain(|&x| x > 4);
assert!(vec == [8, 5, 6]);
```

連続する重複要素を削除する方法。
ベクターがソートされていれば、全ての重複が削除される。

```rust
vec = vec![0, 1, 1, 2, 3, 2, 5, 7, 7, 7];
vec.dedup();
assert!(vec == [0, 1, 2, 3, 2, 5, 7]);
```

配列を空にするにはclearを実行すれば良い。

```rust
vec.clear();
assert!(vec.is_empty());
```

## ベクターに要素を追加する

ベクターに要素を追加する方法は追加する位置や要素によって異なる。
まずベクターの最後尾に要素を追加する方法。

```rust
vec.push(3);
vec.push(5);
vec.push(7);
assert!(vec == [3, 5, 7]);
```

複数要素を追加したい場合は以下のようにする。

```rust
vec.extend_from_slice(&[2, 4, 6]);
assert!(vec == [3, 5, 7, 2, 4, 6]);
```

上に似た手段として、appendというのがある。
ただし追加したベクターは空になる。つまり吸収される。

```rust
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());
```

指定位置に要素を追加したい場合はこうする。

```rust
vec.insert(3, 0);
vec.insert(7, 0);
assert!(vec == [3, 5, 7, 0, 2, 4, 6, 0, 1, 2, 3]);
```

## ベクターから要素を取得する

単純なインデックス以外の方法を見ていく。
以下でベクターの後ろから要素を取り出す。

```rust
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]);
```

また、指定位置以降を切り落とす方法がある。

```rust
assert!(vec.split_off(7) == [0, 1]);
assert!(vec == [3, 5, 7, 0, 2, 4, 6]);
```

ベクターの先頭の要素の参照を得るにはこうする。

```rust
assert!(vec.first() == Some(&3));
assert!(vec == [3, 5, 7, 0, 2, 4, 6]);
```

同様に最後の要素の参照を得ることも出来る。

```rust
assert!(vec.last() == Some(&6));
assert!(vec == [3, 5, 7, 0, 2, 4, 6]);
```

Consセルのように、ベクターの先頭と残りの要素をsliceの形で取得する。

```rust
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]);
```

ベクターの要素を安全に取得したい場合は以下のようにする。
この方法なら領域外を参照することを未然に防ぐことが出来る。

```rust
assert!(vec.get(3) == Some(&0));
assert!(vec.get(10) == None); // 領域外を参照しようとするとNoneが返る
assert!(vec == [3, 5, 7, 0, 2, 4, 6]);
```

ベクターを指定した数の要素のかたまりとして取り出すには以下のようにする。
余った要素のかたまりは指定した長さとはならない。

```rust
for chunk in vec.chunks(3) {
	println!("{:?}", chunk);
}

// 出力
// [3, 5, 7]
// [0, 2, 4]
// [6]
```

指定した位置で分割して、タプルで返すメソッド。

```rust
assert!(vec.split_at(3) == (&[3, 5, 7], &[0, 2, 4, 6]));
assert!(vec == [3, 5, 7, 0, 2, 4, 6]);
```

条件に合致する要素を区切りとして分割するメソッド。

```rust
for group in vec.split(|x| *x == 0) {
	println!("{:?}", group);
}

// 出力
// [3, 5, 7]
// [2, 4, 6]
```

上記のsplitに分割数の制限を設けたメソッドもある。

```rust
for group in vec.splitn(3, |x| *x > 3) {
	println!("{:?}", group);
}

// 出力
// [3]
// []
// [0, 2, 4, 6]
```

以下はそれをベクターの後ろから実行するメソッド。

```rust
for group in vec.rsplitn(3, |x| *x > 3) {
	println!("{:?}", group);
}

// 出力
// []
// []
// [3, 5, 7, 0, 2]
```

## ベクターに要素が含まれるか調べる

ベクターに指定要素が含まれるか調べるには以下のようにする。

```rust
assert!(vec.contains(&2));
assert!(!vec.contains(&10));
```

ベクターが指定した要素で始まるかを調べたい場合はこう。

```rust
assert!(vec.starts_with(&[3, 5]));
assert!(vec.starts_with(&[1, 2]));
```

逆に、指定した要素で終わるかを調べるならこう。

```rust
assert!(vec.ends_with(&[4, 6]));
assert!(!vec.ends_with[&[2, 4]]);
```

## ベクターを操作する

ベクターの要素を交換する。

```rust
vec.swap(0, 4);
assert!(vec == [2, 5, 7, 0, 3, 4, 6]);
```

ベクターを反転する。

```rust
vec.reverse();
assert!(vec == [6, 4, 3, 0, 7, 5, 2]);
```

ベクターをソートする。

```rust
vec.sort();
assert!(vec == [0, 2, 3, 4, 5, 6, 7]);
```

ベクターをバイナリサーチする。

```rust
assert!(vec.binary_search(&4) == Ok(3usize));
```

指定したキーの要素をバイナリサーチ。
(Rust >= 1.10.0)

```rust
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));
```

指定したキーの要素でソート。

```rust
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を付けると変更可能な参照を得られるものもある。

参考:
[Rust Standard Library API Reference - std::vec::Vec](https://doc.rust-lang.org/std/vec/struct.Vec.html)