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

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

概要

キーの順序（比較関数で決まる並び）を保ったまま要素を管理する汎用コンテナ sorted.Map と sorted.Set を、golang.org/x/exp/collection/sorted に追加する提案です。C++ の std::map、Java の TreeMap/TreeSet、Rust の BTreeMap/BTreeSet にあたるものです。

ステータス変更

active → likely_accept
この proposal は 2023 年に出されました。最初は「イテレータの仕様（range-over-func）が決まるまで汎用コンテナは追加しない」（@ianlancetaylor）という理由で保留されていました。Go 1.23 でイテレータが入った後、@jba が試作パッケージ github.com/jba/omap を作り、Go チームの Collections Working Group が API を練り直しました。2026 年 10 月 7 日に最終 API（Map/MapSpan/Set/SetSpan）が示され、実装 CL も出ています。
レビューでは @aclements が span の考え方を「I love the span concept」と高く評価しました。指摘は小さなものが 2 点だけでした。

マップ全体を MapSpan として取り出す手段がない
String() の出力が昇順であることをドキュメントに書くべき
大きな異論がないため likely accept となりました。

技術的背景

現状の問題点

Go 組み込みの map は反復の順序が決まっていません。順序付きで扱いたいときは、毎回キーを取り出してソートするか、github.com/google/btree などのサードパーティ製ライブラリに頼るしかありません。GitHub 上には TreeMap や OrderedMap といった自前実装が数千あります。@jba は google/btree を詳しく分析し、次の弱点を挙げました。

API が使いにくい
範囲をまとめて削除する機能がない
反復中に変更したときの保証を得るには、コストの大きいクローンが必要

提案された解決策

主な API は次のとおりです。

NewMap[K, V any](cmp func(K, K) int) *Map[K, V]、NewSet[T any](cmp func(T, T) int) *Set[T]
- 比較関数を渡して作成します。ゼロ値や nil は使えません。
Map のメソッド
- 基本操作: Set、Get（ないときはゼロ値）、Lookup（値と bool）、Delete、DeleteFunc、Contains、Len、Clear、Clone
- 反復: All、Keys、Values、Backward（すべて iter.Seq/iter.Seq2 を返す）
- 最小・最大: Min、Max（キー・値・bool を返す）
- インデックス: Nth(i)（i 番目の要素）、Index(key)（キーの位置）
範囲指定: From(lo)（lo 以上）、Above(lo)（lo より大きい）、To(hi)（hi 以下）、Below(hi)（hi 未満）
- これらは MapSpan を返します。MapSpan はスライスと配列の関係のように、元のマップの一部を指す「ビュー」です。
- さらに絞り込むことができ、Clear で範囲内の要素をまとめて削除できます。
Set には上記に加えて集合演算があります。
- 新しい集合を返す: Union、Intersection、Difference、SymmetricDifference
- 自分自身を書き換える: UnionWith など ...With 系
- 判定: Equal、Intersects
反復の保証: 反復中にマップを変更してもかまいません。次に返るのは、直前に返したキーの「その時点での後続キー」です。

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

時系列データやイベントのスケジューリング: タイムスタンプをキーにして、「ある時刻以降」の範囲を取り出したり、古いデータを範囲ごと削除したりできます。
疎行列やインデックス構造: キー順の走査や Nth による順位の取得ができます。リーダーボードの順位計算などに向いています。
区間検索: 「x 以上で最小のキー」（From(x).Min()）や「x 未満で最大のキー」（Below(x).Max()）を対数時間で求められます。

コード例

// Before: 組み込み map + 毎回ソート（O(n log n)）
m := map[int]string{}
m[30], m[10], m[20] = "c", "a", "b"
keys := slices.Sorted(maps.Keys(m))
for _, k := range keys {
    if k >= 15 && k < 30 {
        fmt.Println(k, m[k])
    }
}
// After: sorted.Map
sm := sorted.NewMap[int, string](cmp.Compare[int])
sm.Set(30, "c"); sm.Set(10, "a"); sm.Set(20, "b")
for k, v := range sm.From(15).Below(30).All() {
    fmt.Println(k, v) // 20 b
}
sm.Below(15).Clear()           // 15 未満をまとめて削除
k, v, ok := sm.From(25).Min()  // 25 以上で最小のエントリ
s := sorted.NewSet(strings.Compare)
s.Insert("b"); s.Insert("a")
u := s.Union(other)            // 集合演算

議論のハイライト

範囲 API の設計: Rust の RangeBounds のような Bound 型を使う案や、「すべての Map が境界を持つ」案（スライス風）も検討されました。しかし後者は、コードを読む人が境界を把握しにくく分かりにくいとして見送られました。結果として、From/To/Above/Below を連鎖させる MapSpan 方式になりました。最初は同じ方向の境界を重ねて指定すると panic していましたが、範囲が狭まらない指定は何もしない（no-op）仕様に変わりました。
cmp.Ordered 専用型（OMap）の削除: 比較関数を明示的に書けばインライン化されて速くなる、という性能上の理由で別型が提案されていました。しかし「将来コンパイラやランタイムの改善で不要になりうる」として削除され、比較関数を受け取る NewMap だけになりました。
パッケージ名: container/ordered、tree、maps.Sorted と何度も変わりました。「hashed は実装を表し、sorted は振る舞いを表すので一貫しない」という指摘もありましたが、最終的に x/exp/collection/sorted に落ち着きました。@ianlancetaylor は「命名ではドット import を考慮すべきでない」と述べています。
Set の復活: 一度は「Map[K, struct{}] で足りる」として外されました。しかし Java の TreeSet の利用実績などを根拠に要望が出て、集合演算付きの Set が再び加わりました。
最終レビューでの指摘: @aclements と @adonovan が、全体を表す span を得る手段がないことを指摘し、内部の span() メソッドを公開すべきだとしています。そのため、最終的な API に小さな追加が入る可能性があります。

Go Proposal Weekly Digest

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

要約

概要