Rustのコレクション型まとめ (VecやHashMapなど)

Rustの標準ライブラリでは、`Vec`や`HashMap`などいくつかのコレクション型が用意されています。どういった型が用意されているか、以下で簡単にまとめていきます。なお、`Vec`以外は`std::collections`以下に定義されています。

# Vec
おなじみの可変長配列です。`std::vec`以下に定義されていますが、デフォルトでインポートされているため、`use std::vec::Vec;`と書く必要はありません。作成するには、`Vec::new()`の他に`vec![]`マクロを使うことができます。

``` Rust
let mut v = vec![1, 2, 3];
assert_eq!(v[0], 1);
assert_eq!(v[1], 2);
assert_eq!(v[2], 3);
v[1] = 4;
assert_eq!(v[1], 4);
```

末尾への追加・削除は、メモリが足りなくなった時の再割当てが発生しない限り高速に実行できます。そのため、スタックが欲しい場合も`Vec`を使います。末尾に要素を追加する場合は`push()`を、取り出したいときは`pop()`を使います。

``` Rust
let mut v = Vec::new();
v.push(2);
v.push(3);
v.push(5);
assert_eq!(v.pop(), Some(5));
assert_eq!(v.pop(), Some(3));
assert_eq!(v.pop(), Some(2));
assert_eq!(v.pop(), None);
```

# VecDeque
[リングバッファ](https://ja.wikipedia.org/wiki/%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%90%E3%83%83%E3%83%95%E3%82%A1)による[両端キュー](https://ja.wikipedia.org/wiki/%E4%B8%A1%E7%AB%AF%E3%82%AD%E3%83%A5%E3%83%BC)です。`Vec`と異なり、末尾だけでなく先頭への追加・削除も高速に実行できます。そのため、キューが欲しいときに使うことになります。先頭への追加・取り出しにはそれぞれ`push_front()`と`pop_front()`を、末尾への追加・取り出しにはそれぞれ`push_back()`と`pop_back()`を使います。

``` Rust
use std::collections::VecDeque;
let mut v = VecDeque::new();
v.push_front(2);
v.push_front(3);
v.push_front(5);
assert_eq!(v.pop_back(), Some(2));
assert_eq!(v.pop_back(), Some(3));
assert_eq!(v.pop_back(), Some(5));
assert_eq!(v.pop_back(), None);
```

`Vec`と同様にi番目の要素にアクセスすることもできます。ただし、リングバッファを使っているため、i番目の要素のアドレスを得るのにわずかながら追加の計算が必要になります。単純に配列として使うのであれば`Vec`の方が高速です。

``` Rust
let mut v = VecDeque::new();
v.push_front(1);
v.push_back(2);
v.push_front(3);
assert_eq!(v[0], 3);
assert_eq!(v[1], 1);
assert_eq!(v[2], 2);
```

# LinkedList

各要素が前後の要素へのポインタを持つ[連結リスト](https://ja.wikipedia.org/wiki/%E9%80%A3%E7%B5%90%E3%83%AA%E3%82%B9%E3%83%88)です。先頭と末尾に要素を追加したり、要素を取り出したりできる点では`VecDeque`に似ていますが、2つのリストを結合したり、1つのリストを2つに分離したりする操作が効率的に行えます。各要素のメモリ上の位置を変えることなく、ポインタの指す位置を変えるだけで、要素の連結・分離ができるためです。

``` Rust
use std::collections::LinkedList;
let mut list_a = LinkedList::new();
list_a.push_back(0);
list_a.push_back(1);
let mut list_b = LinkedList::new();
list_b.push_back(2);
list_b.push_back(3);
list_a.append(&mut list_b); // list_aの後ろにlist_bを連結

assert_eq!(list_a.pop_back(), Some(3));
assert_eq!(list_a.pop_back(), Some(2));
assert_eq!(list_a.pop_back(), Some(1));
assert_eq!(list_a.pop_back(), Some(0));
assert_eq!(list_a.pop_back(), None);
assert_eq!(list_b.pop_back(), None); // list_bは空になる
```

リストの中間地点に要素を追加したり、削除する操作が効率的にできるのも連結リストの特徴ですが、Rust1.26の時点では、そのような操作のためのメソッドが用意されていません(イテレータ経由で少しnightly用のメソッドが用意されています)。連結リストの途中にある要素にアクセスするには、先頭もしくは末尾からリストをたどる必要があるので、計算時間が線形に増えていきます。そのため、リストの途中の要素に対する操作を提供するメソッドを安易に提供したくなかったのでしょう[^1]。

先述のように先頭・末尾以外の要素へのアクセスに時間がかかること、また各要素のデータがメモリ上に分散するため、CPUのキャッシュ効率に劣ることから、基本的にリストを表現する方法として`Vec`か`VecDeque`を用いることが推奨されています。現状は連結リストとしての機能が制限されていることもあり、あまり利用する場面はないかもしれません。

# HashMap

おなじみの[ハッシュテーブル](https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB)です。キーと値をペアで記録してくれるもので、他の言語では連想配列や辞書型と呼ばれたりします。キーに使う型は`Eq`と`Hash`を実装している必要があります。自作の構造体等をキーにしたい場合、`#[derive(PartialEq, Eq, Hash)]`を宣言に追加しておきましょう。キーからの値の探索、ペアの挿入、削除にかかる計算時間は定数時間、つまりO(1)です(理想的な場合は)。

``` Rust
use std::collections::HashMap;
let mut map = HashMap::new();
map.insert("lisp", 1958);
map.insert("c", 1972);
map.insert("rust", 2006);

assert_eq!(map["lisp"], 1958); // [ ] でアクセス可能。存在しないキーだとパニック
assert_eq!(map.get("c"), Some(&1972)); // get()を使うと、キーが存在する場合はSomeを、
assert_eq!(map.get("perl"), None);     // 存在しない場合はNoneを返す
assert!(map.contains_key("rust"), true); // contains_key()でキーが存在するかの判定
```

イテレータでキーと値のペアを参照することもできます。

``` Rust
for (k, v) in &map {
    println!("{} was born in {}", k, v);
}
```

ちなみに、ここで示したイテレータで`HashMap`の中身を表示するコードですが、実行するたびにどのペアが表示されるかの順番が変わります。これは、異なるキーから同じハッシュ値が生成されると、ハッシュテーブルの効率が低下することを利用するDoS攻撃の回避策として、ハッシュの計算にランダム性を加えているためです。このあたりのアルゴリズムはプログラマの判断で変更でき、ランダム性のない`HashMap`も作れるようになっていますが、多くの場合はデフォルトで問題ないでしょう。ただ、`HashMap`を使ったプログラムが、なぜか実行するたびに結果が異なる、といったことが起こりうるため、このデフォルトの挙動は覚えていたほうが良いでしょう。

# BTreeMap

`HashMap`のように、キーと値のペアを記録してくれます。`HashMap`との違いは、ハッシュテーブルではなく[B木](https://ja.wikipedia.org/wiki/B%E6%9C%A8)を用いて実装されているということです。キーは大小の比較ができるもの、つまり`Ord`を実装している型である必要があります。キーからの値の探索、ペアの挿入、削除にかかる計算時間のオーダーはO(log n)になります。

``` Rust
use std::collections::BTreeMap;
let mut map = BTreeMap::new();
map.insert("lisp", 1958);
map.insert("c", 1972);
map.insert("rust", 2006);

assert_eq!(map["lisp"], 1958); // [ ] でアクセス可能。存在しないキーだとパニック
assert_eq!(map.get("c"), Some(&1972)); // get()を使うと、キーが存在する場合はSomeを、
assert_eq!(map.get("perl"), None);     // 存在しない場合はNoneを返す
assert!(map.contains_key("rust"), true); // contains_key()でキーが存在するかの判定
```

`HashMap`と同様に、イテレータでキーと値のペアを参照することができます。

``` Rust
for (k, v) in &map {
    println!("{} was born in {}", k, v);
}
```

このイテレータの順序は、キーに対して昇順になります。

``` Rust
let mut iter = map.iter();
assert_eq!(iter.next(), Some((&"c", &1972)));
assert_eq!(iter.next(), Some((&"lisp", &1958)));
assert_eq!(iter.next(), Some((&"rust", &2006)));
assert_eq!(iter.next(), None);
```

# HashSet

値がなくキーのみの`HashMap`です。内部的には値の型が`()`である`HashMap`として実装されています。

``` Rust
use std::collections::HashSet;
let mut set = HashSet::new();
set.insert("abc");
set.insert("xyz");
assert!(set.contains("abc"));
assert!(!set.contains("ijk"));
```

# BTreeSet

`HashSet`と同じく、`BTreeMap`の値なしバージョンです。

``` Rust
use std::collections::BTreeSet;
let mut set = BTreeSet::new();
set.insert("abc");
set.insert("xyz");
assert!(set.contains("abc"));
assert!(!set.contains("ijk"));
```

# BinaryHeap

[二分ヒープ](https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E3%83%92%E3%83%BC%E3%83%97)により実装された[優先度付きキュー](https://ja.wikipedia.org/wiki/%E5%84%AA%E5%85%88%E5%BA%A6%E4%BB%98%E3%81%8D%E3%82%AD%E3%83%A5%E3%83%BC)です。大小関係を比較可能な型、つまり`Ord`を実装した型を格納でき、そして取り出す時には最も大きい要素を返します。

``` Rust
use std::collections::BinaryHeap;
let mut bh = BinaryHeap::new();
bh.push(10);
bh.push(5);
bh.push(16);
bh.push(8);

assert_eq!(bh.pop(), Some(16));
assert_eq!(bh.pop(), Some(10));
assert_eq!(bh.pop(), Some(8));
assert_eq!(bh.pop(), Some(5));
assert_eq!(bh.pop(), None);
```

# 結局どれを使えばいいのか

配列が欲しい = `Vec`
連想配列が欲しい = `HashMap`
連想配列が欲しい & キーの順序が重要 = `BTreeMap`
スタックが欲しい = `Vec`
キューが欲しい = `VecDeque`
このあたりを覚えておけばたいてい事足りるはずです。

# 参考

[std::collections 公式ドキュメント](https://doc.rust-lang.org/std/collections/index.html)

[^1]: 将来的にはなんらかのメソッドが提供されるかもしれません。[この問題に関するissueもあります。](https://github.com/rust-lang/rust/issues/27794)