btreemap

目的もくてき

• BTreeMap<.K, .V> を提供ていきょうし、new / insert / get / contains / remove / len / clear / free の bare 名で扱あつかえるようにします。
• key の比較ひかくは Ord trait に委譲いじょうし、i32 固定から脱却だっきゃくします。

実装じっそう

• 名前なまえは BTreeMap ですが、現実げんじつの内部表現ないぶひょうげんは整列済せいれつずみ key/value 配列はいれつです。
• 検索けんさくは lower_bound、挿入そうにゅう / 削除さくじょは shift で実装じっそうします。

注意ちゅうい

• 本物ほんものの B-tree ではありません。
• Ord impl が全順序ぜんじゅんじょを満みたすことを前提ぜんていにします。

計算量けいさんりょう

• get / contains は O(log n)、insert / remove は O(n) です。

BTreeMap

順序付きじゅんじょつき key/value 配列はいれつの本体ほんたい

new

空からの BTreeMap<.K, .V> を作つくる

len

要素数ようそすうを返かえす

contains

key の存在そんざいを確たしかめる

get

key に対応たいおうする value を返かえす

insert

key/value を挿入そうにゅうまたは更新こうしんする

remove

key を削除さくじょする

clear

全要素ぜんようそを削除さくじょする

free

内部ないぶメモリを解放かいほうする