Go Collections: 標準ライブラリへの新たなコレクション API

背景と目的

Go Collections ワーキンググループは、2025 年末に設立されました。

• 設立趣旨: Go の「実践主義」と「簡潔性」の原則に基づき、共通のコレクションデータ構造を標準ライブラリに取り入れることを目的としています。
• 主要メンバー:
  • Jonathan Amsterdam (@jba)
  • Alan Donovan (@adonovan)
  • Robert Griesemer (@griesemer)
  • Daniel Martí (@mvdan)
  • Roger Peppe (@rogpeppe)
  • Keith Randall (@khr)
  • Ian Lance Taylor (@ianlancetaylor)
• 現状の課題:
  • 標準ライブラリにはスライスとマップしか提供されておらず、ヒープ以外の実装は限られています。

  • 集合

    は完全に欠けており、慣習として

    map[T]bool

    または

    map[T]struct{}

    が使用されています。
  • 順序付けされたマップやセットも存在しません。
• ジェネリックとイテレータの進展:
  • Go 1.18 でジェネリック、Go 1.23 でイテレータ機能が追加され、ライブラリ型でも組み込み型に近い使いやすさが実現可能になりました。
  • 本作業は標準ライブラリに重要なデータ構造を追加し、API の慣習を設定することを目的としています。

提案される新しい API

以下のように、複数の新しい型やパッケージが追加予定されています。

hash/maphash.Hasher

map[K]V

container/hash.Map[K,V]

container/hash.Set[T]

container/set.Set[T]

map[T]struct{}

container/mapset

set.Set

container/ordered.Map[K,V]

container/heap/v2.Heap

将来の計画: 挿入順序を保証するハッシュマップ (#80194) やスタックなどの追加も検討中です。

初期実装のアプローチ: API と漸近的性能（時間計算量）を満たすことに焦点を当て、定数係数の最適化は後回しとしています。

抽象的なコレクション制約インターフェース

Map

Set

そのため、F 境界多形を使用する抽象的な制約インターフェースが導入されました。

• 非公開: 現時点で公式に公開されておりませんが、一貫性を保つための内部利用のみ可能です。
• 将来性: 具体的なコレクション型の経験に基づき、将来的なリリースで公開される可能性があります。

インターフェース定義の例

テストにおける適合性保証のみを目的とした簡易的な再掲です。

// _AbstractCollection は要素 E の集合 C（*hash.Map, *hash.Set など）を表します。
type _AbstractCollection[E any, C _AbstractCollection[E, C]] interface {
    Clear()
    Clone() C
    Contains(E) bool
    ContainsAll(iter.Seq[E]) bool
    Len() int
    String() string
}

// _AbstractMap はキー K から値 V へのマッピング M を表します。
type _AbstractMap[K, V any, M _AbstractMap[K, V, M]] interface {
    _AbstractCollection[K, M]

    All() iter.Seq2[K, V]
    At(K) V
    Delete(K) (V, bool)
    DeleteAll(iter.Seq[K]) bool
    DeleteFunc(func(K, V) bool) bool
    Get(K) (V, bool)
    Keys() iter.Seq[K]
    Set(K, V) (V, bool)
    SetAll(iter.Seq2[K, V]) bool
    Values() iter.Seq[V]
}

// _AbstractSet は要素 E の集合 S を表します。
type _AbstractSet[E any, S _AbstractSet[E, S]] interface {
    _AbstractCollection[E, S]

    All() iter.Seq[E]
    Delete(E) bool
    DeleteAll(iter.Seq[E]) bool
    DeleteFunc(func(E) bool) bool
    Difference(S) S
    DifferenceWith(S)
    Equal(S) bool
    Insert(E) bool
    InsertAll(iter.Seq[E]) bool
    Intersection(S) S
    IntersectionWith(S)
    Intersects(S) bool
    SymmetricDifference(S) S
    SymmetricDifferenceWith(S)
    Union(S) S
    UnionWith(S)
}

汎用関数の定義例

最小限の制約型を定義することで、ユーザーが必要な操作を実装可能です。

// _TakeSet は [Take] 関数に必要な抽象的なセットを定義します。
type _TakeSet[E any, S _TakeSet[E, S]] interface {
    All() iter.Seq[E]
    Delete(E) bool
}

// Take はセットから任意の要素を取り出し返します（空の場合はゼロ値）。
func Take[S _TakeSet[E, S], E any](set S) (e E, found bool) {
    for e = range set.All() {
        found = true
        set.Delete(e)
        break
    }
    return
}

メソッド選択に関する判断基準

• 主観性とバランス: すべての操作をインターフェースに含めると実装負担が不釣り合いになるため、実装者への影響を考慮して慎重な選択が行われています。

  • Subset

    メソッドは省略されました（高速化が必要な特殊ケースを除き、コストがかかるため）。

  • DeleteFunc

    は残されています（ツリー内の要素削除における漸近的パフォーマンス低下を防ぐため、O(n log n) を O(n) にするため）。
• 将来の拡張: 具体的な使用状況に基づき、必要なメソッドを追加していく予定です。

その他の設計上の考察

メソッドの返戻値と再検索防止

• 変異メソッド: コレクションサイズを変更したかどうかを報告します。
• 置換ロジック (

  Map.Set

  /

  Map.Delete

  ): 既存のキーがあればその値を返し、ブール値で存在の有無も区別します（ゼロ値との混同を防ぐため）。
• 取得メソッド (

  Get

  vs

  At

  ):

  At

  は式文脈での使い勝手を考慮し提供されています。

マップとセットの違い

• マップ:

  Equal

  メソッドを持っていません（値が比較不可能になり得るため）。
• 置換ルール:

  Map.Set

  は既存のキーを持つエントリを置換します（組み込みの

  map

  に従う）。

集合演算のパフォーマンスと実装手法

集合代数演算（Union など）は、純粋関数的に新しいセットを返す方式を採用しました。

• 理由:

  math/big.Int

  API の経験を踏まえ、副作用や結果の忘却を防ぐためです。
• バリエーション:

  • -With

    オプションなし: 左演算子を不変として新しいセットを返します（「便利なもの」）。

  • -With

    オプションあり: 左演算子を直接変更し、何もしません（割当効率の良いもの）。

キーセットビュー

• KeySetView[M, K, V]

  というラッパー型により、マップ

  [K,V]

  のキーセットとして

  Set[K]

  を抽象的に満たすことができます。
• このビューには挿入は無意味であり、パニックを引き起こします。

maps

パッケージとの機能比較

Clear

Len

clear

len

Clone

DeleteFunc

All

Keys

Values

maps.Clone

Contains

ContainsAll

DeleteAll

m[k]

Set

prev, ok = m[k]; m[k] = newval

今後、「

maps.{Contains, ContainsAll, DeleteAll}

• Contains

  : 式文脈において

  _ , ok = s[k]

  よりも有用です。

• ContainsAll

  ,

  DeleteAll

  : ループおよびブール値の管理を不要にする利点があります。