1. 聞き流しプログラミング言語学習
  2. Rust 029 BTreeMap と BTreeSe..
Rust 029 BTreeMap と BTreeSet - 順序を保つ対応表
2026-05-11 12:14

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

第29章へようこそ。


これまでに扱ったHashMapとHashSetには、共通する性質がありました。

内部はハッシュテーブルで、要素はハッシュ関数によって決まる位置に置かれる。

そのため、要素は挿入順にも整列順にも並ばず、イテレーションの順序は保証されない。

個々の操作はほぼ一定時間で動くが、順序にまつわる操作は構造的に難しい。


順序が必要な場面があります。

キーが範囲で問い合わされる場合。たとえば「ある日付以降のすべてのエントリ」「キーが10から20の間にあるもの」。

イテレーション順序が一定であることが望ましい場合。出力順を整えたい、結果を予測可能にしたい。

最小のキーや最大のキーを高速に取り出したい場合。


これらの場面のために用意されているのがBTreeMapとBTreeSetです。

役割はHashMapとHashSetと同じく、ペアの対応表と要素の集合。違うのは内部構造で、ハッシュテーブルではなくBツリーと呼ばれる木構造を使う。

今日扱うのは、Bツリーがどう順序を保つか、その代償は何か、求められるトレイトはなぜ変わるか、そして範囲クエリという固有の操作です。


感想

まだ感想はありません。最初の1件を書きましょう!

12:14

コメント

スクロール