#60630 golang.org/x/exp/collection/sorted: add Map/Set based on key order

AIによる要約であり、誤りを含む場合があります。

概要

キーの順序（比較関数で決まる大小）に沿って要素を保持する汎用コレクション sorted.Map[K, V] と sorted.Set[T] を golang.org/x/exp/collection/sorted に追加する提案です。Java の TreeMap/TreeSet や Rust の BTreeMap/BTreeSet に当たるもので、Go の標準ライブラリにはまだありません。

ステータス変更

(なし) → active
2023年に提案された当初は、Ian Lance Taylor 氏が「イテレータの仕組みが決まるまで汎用コンテナは追加しない」と述べ、議論は保留になっていました。その後 Go 1.23 で range-over-func（関数を range で回せる仕組み）が導入されました。さらに 2025年末に Go チームの Collections working group（@jba、@adonovan、@griesemer、@ianlancetaylor など）が発足し、コレクション型をまとめて検討し始めました。2026年10月7日に @jba が最新 API を掲載し、実装 CL（846345、846365）も出たため、週次の proposal review meeting で正式に審議する段階に入ったと考えられます。この提案は、umbrella issue #80590（Go 1.28 向けのコレクション一式）の一部として扱われています。

技術的背景

現状の問題点

Go で順序付きのマップが必要な場合は、組み込みの map を作ってからキーをソートするか、github.com/google/btree のようなサードパーティ実装を使うしかありません。似た実装は GitHub 上に数千件あります。
「ある値以上・未満のキーだけを取り出す」といった範囲検索や、最小値・最大値の取得を、挿入や削除をしながら効率よく行えません。
@jba によると、google/btree には次の弱点があります。
- API がキーと値を 1 つの Item 型にまとめている
- 範囲をまとめて削除する機能がない
- 反復用のメソッドが 8 個もあって使いにくい
- 反復中にマップを変更したときの動作が保証されていない

提案された解決策

NewMap[K, V any](cmp func(K, K) int) *Map[K, V]：比較関数を渡して作ります。ゼロ値や nil ポインタのままでは使えません。
基本操作：Set、Get、Lookup、Delete、DeleteFunc、Contains、Len、Clear、Clone、String
順序に関する操作：Min、Max、Nth(i)（i 番目の要素）、Index(key)（キーの位置）
反復：All、Keys、Values、Backward。いずれも iter.Seq/iter.Seq2 を返します。反復中にマップを変更しても、次に返るのは「直前に返したキーの次のキー」であることが保証されます。
範囲指定：From（以上）、To（以下）、Above（より大きい）、Below（より小さい）で MapSpan を作ります。MapSpan はスライスと同じように元のマップを共有する「部分ビュー」で、Clear を呼ぶと範囲内のエントリをまとめて削除できます。
Set[T]：集合演算 Union、Intersection、Difference、SymmetricDifference（と、自分自身を書き換える ...With 版）、Insert、Equal、Intersects に加え、範囲指定用の SetSpan を持ちます。

これによって何ができるようになるか

タイムスタンプをキーにしたイベントから、指定した時間帯の分だけを取り出したり、古い分をまとめて削除したりできます。
スコア順のランキングで、Nth を使って順位を引いたり、Index で特定エントリの順位を調べたりできます。
疎行列、区間管理、OpenAPI 仕様のレンダリングなど、決まった順序で出力する必要がある処理に使えます。

コード例

// Before: 組み込み map とソートで範囲検索（呼び出すたびに O(n log n)）
m := map[int]string{}
// ... m にエントリを追加 ...
keys := slices.Sorted(maps.Keys(m))
for _, k := range keys {
    if k >= 100 && k < 200 {
        fmt.Println(k, m[k])
    }
}
// After: sorted.Map を使う
sm := sorted.NewMap[int, string](cmp.Compare[int])
sm.Set(150, "a")
for k, v := range sm.From(100).Below(200).All() {
    fmt.Println(k, v)
}
sm.Below(50).Clear()      // 50 未満のエントリをまとめて削除
k, v, ok := sm.Min()      // 最小のキーとその値

議論のハイライト

イテレータ待ち：当初は Go のイテレータ設計（#56413）が決まっていなかったため保留になりました。Go 1.23 以降、@adonovan の提案で、Keys/Values/All がスライスを作らずに iter.Seq を返す形に改められました。
範囲 API の設計：Rust 風に境界値を表す Bound 型を引数で渡す案も出ましたが、m.From(lo).Below(hi).All() のようなメソッドチェーンの方が読みやすいとして採用されました。Map 自体に範囲（境界）を持たせる案は、コードを読む人がどの範囲のマップなのか把握しにくくなるため却下されました。名前は Range だと range キーワードと紛らわしいため MapSpan になりました。
cmp.Ordered 専用の型（OMap）の削除：比較関数がインライン化されるので速くなる利点はありましたが、API が倍になるため外されました。将来、コンパイラや言語の進化で不要になる可能性がある、という判断です。
Set の復活：一度は「Map[K, struct{}] で足りる」として外されました。しかし @willfaught が Java の TreeSet の利用実績を示して反論し、Union などの集合演算を持つ Set が再び追加されました。
パッケージ名：container/tree → container/ordered → x/exp/container/maps.Sorted → x/exp/collection/sorted と変遷しました。Linux のコンテナ仮想化と紛らわしいため、「container」ではなく「collection」が選ばれています。メソッド名は hashed.Map（#69559）と揃えられています（Get/Lookup/Set/Delete）。

Go Proposal Weekly Digest

golang.org/x/exp/collection/sorted: add Map/Set based on key order

要約

概要