Rust 029 BTreeMap と BTreeSet - 順序を保つ対応表

第29章へようこそ。これまでに扱ったHashMapとHashSetには、共通する性質がありました。内部はハッシュテーブルで、要素はハッシュ関数によって決まる位置に置かれる。そのため、要素は挿入順にも整列順にも並ばず、イテレーションの順序は保証されない。個々の操作はほぼ一定時間で動くが、順序にまつわる操作は構造的に難しい。順序が必要な場面があります。キーが範囲で問い合わされる場合。たとえば「ある日付以降のすべてのエントリ」「キーが10から20の間にあるもの」。イテレーション順序が一定であることが望ましい場合。出力順を整えたい、結果を予測可能にしたい。最小のキーや最大のキーを高速に取り出したい場合。これらの場面のために用意されているのがBTreeMapとBTreeSetです。役割はHashMapとHashSetと同じく、ペアの対応表と要素の集合。違うのは内部構造で、ハッシュテーブルではなくBツリーと呼ばれる木構造を使う。今日扱うのは、Bツリーがどう順序を保つか、その代償は何か、求められるトレイトはなぜ変わるか、そして範囲クエリという固有の操作です。