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

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

Vec

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

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()を使います。

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

リングバッファによる両端キューです。Vecと異なり、末尾だけでなく先頭への追加・削除も高速に実行できます。そのため、キューが欲しいときに使うことになります。先頭への追加・取り出しにはそれぞれpush_front()とpop_front()を、末尾への追加・取り出しにはそれぞれpush_back()とpop_back()を使います。

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の方が高速です。

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

各要素が前後の要素へのポインタを持つ連結リストです。先頭と末尾に要素を追加したり、要素を取り出したりできる点ではVecDequeに似ていますが、2つのリストを結合したり、1つのリストを2つに分離したりする操作が効率的に行えます。各要素のメモリ上の位置を変えることなく、ポインタの指す位置を変えるだけで、要素の連結・分離ができるためです。

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用のメソッドが用意されています)。連結リストの途中にある要素にアクセスするには、先頭もしくは末尾からリストをたどる必要があるので、計算時間が線形に増えていきます。そのため、リストの途中の要素に対する操作を提供するメソッドを安易に提供したくなかったのでしょう¹。

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

HashMap

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

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()でキーが存在するかの判定

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

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

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

BTreeMap

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

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と同様に、イテレータでキーと値のペアを参照することができます。

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

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

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として実装されています。

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の値なしバージョンです。

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

BinaryHeap

二分ヒープにより実装された優先度付きキューです。大小関係を比較可能な型、つまりOrdを実装した型を格納でき、そして取り出す時には最も大きい要素を返します。

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 公式ドキュメント

1. 将来的にはなんらかのメソッドが提供されるかもしれません。この問題に関するissueもあります。 ↩