HN 日本語サマリー

← 一覧へ戻る
プログラミング

Golang提案: container/: ジェネリックコレクション型

Golang proposal: container/: generic collection types (github.com)

167 pointsby jabits144 コメント

要約

Go言語のコレクションワーキンググループは、Go 1.28に向けて標準ライブラリに一般的なコレクションデータ構造(ハッシュマップ、セット、順序付きマップ、バイナリヒープなど)を導入する提案を発表しました。ジェネリクスとイテレータの追加により、より人間工学的なAPIと効率的な実装が可能になり、既存のコードとの互換性も考慮されています。

全文翻訳

proposal: container/...: ジェネリックコレクション型 #80590

更新: 挿入順序を保持するマップ、およびJSONマーシャリング動作の指定を含む。2026年10月13日。-jba

最新の変更を反映しました。2026年10月7日。-jba

背景: Goコレクションワーキンググループは、実用性とシンプルさというGoの慣習に導かれ、一般的なコレクションデータ構造を標準ライブラリにもたらすことを目的として、2025年後半に設立されました。グループは、姓のアルファベット順で、Jonathan Amsterdam (@jba)、Alan Donovan (@adonovan)、Robert Griesemer (@griesemer)、Daniel Martí (@mvdan)、Roger Peppe (@rogpeppe)、Keith Randall (@khr)、Ian Lance Taylor (@ianlancetaylor) で構成されています。私たちは今、コミュニティに成果を共有できる段階に達しました。

このIssueは、Go 1.28向けのいくつかの関連する新しいコレクションAPIの提案を議論するための包括的なものです。テーマの概要と、さまざまな具体的な提案および関連する実装CLへのリンクを示します。

Goは現在、ライブラリにほとんどコレクション型を提供しておらず、当初から組み込みのスライス型とマップ型の柔軟性を重視してきました。提供されている中で最も重要なのは、優先度付きキューに使用されるヒープです。セットさえも欠けており、それらは慣習的に map[T]bool または map[T]struct{} として表現されています。バイナリツリーに基づいた順序付きマップとセットは、全く存在しません。

Go 1.18でのジェネリクスの追加とGo 1.23でのイテレータの導入により、ライブラリ定義型が組み込み型と同等のエルゴノミクスを達成できるようになり、スライスやマップに対する多くの一般的な操作がライブラリ関数呼び出しとして表現できるようになりました。この作業は、より重要なデータ型のいくつかを標準ライブラリに追加し、それらのAPIおよび将来の追加のための規約を確立することを目指しています。

提案: 提案されている追加機能は以下の通りです。

  • #70471, CL 657296 (go1.27でリリース): hash/maphash.Hasher: カスタムハッシュ関数と任意のデータ型の等価関係を表現するための標準インターフェース。これらはマップ map[K]V で使用されるコンパイラ定義のものとは異なり、キー型が比較不可能(スライスやマップなど)である場合、またはデフォルトの比較が誤った結果を生成する場合(例えば、深層比較操作 types.Identical を必要とする types.Type 値の場合)に役立ちます。そのパッケージドキュメントには、ブルームフィルタでの使用例が含まれています。

  • #69559, CL 612217: golang.org/x/collection/hashed.Map[K,V]: 上記のカスタムハッシュ関数を使用するハッシュベースのMapです。

  • #80584, CL 741160: golang.org/x/collection/hashed.Set[T]: 同様のハッシュベースのSetです。

  • #69230, CL 745441: golang.org/x/collection/set.Set[T]: セット要素が比較可能な場合の、標準的なデータ型です。これは map[T]struct{} として透過的に表現され、UnionやIntersectionなどのすべての通常のセット操作をサポートします。これは「レガシー」な map[T]bool や map[T]struct{} ベースのセットよりも便利で、map[T]bool における偽値の可能性に関する曖昧さを回避します。多くの新しいGo APIで標準的なセットになると予想されます。

  • #60630: golang.org/x/collection/sorted.Map[K,V]: 順序付きマップです。現在の実装は平衡二分木を使用していますが、設計上それに限定されるわけではありません。一般的なGoのパターンである map[K]V を構築してからキーをソートする方法は、ほとんどの場合うまく機能しますが、範囲クエリが必要な場合など、他のデータ構造がはるかに優れたパフォーマンスを発揮することがあります。

  • #60630: golang.org/x/collection/sorted.Set[K,V]: 同様の順序付きセットです。

  • #77397: golang.org/x/collection/heap.Heap: 標準ライブラリの既存のヒープは使用が困難な場合があるため、それを置き換えるジェネリックなバイナリヒープAPIです。

  • #80194: 挿入順序を保持するハッシュマップ: アイテムが挿入された順序でのイテレーションが拡張されたハッシュマップです。

[ mapset パッケージとして当初提案されていたものは取り下げられました。]

今後、キューやスタックなどの追加提案を検討する予定です。

提案されたすべてのデータ構造の初期実装は、APIと漸近的パフォーマンスの期待値を可能な限りシンプルに満たすことを目指しています。定数係数を削減するための最適化の機会は間違いなく多くありますが、それらは提案プロセスの範囲外です。

新しいパッケージは golang.org/x/exp に配置され、コミュニティにフィードバックのための十分な時間を与えます。最終的にはこれらのパッケージを標準ライブラリに追加したいと考えています。

標準ライブラリはデータ構造パッケージに container を使用していますが、Linuxのコンテナ仮想化の概念との混同を避けるため、「コレクション」という用語を好みます。

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

新しいMap型とSet型のほとんどのメソッドは、特定の具象表現型に固有のものではなく、すべてのMapとSetに共通しています。しかし、“バイナリメソッド問題”のため、これらは共通のインターフェース型の実装ではありません。各セットデータ型Sが func (S) Union(S) S の形式のUnionメソッドを持つ場合、異なるセット型のUnionメソッドは互換性がないため、共通の通常のインターフェースを持ちません。この抽象Set型を表現するには、F-bounded多相または再帰的制約インターフェースを使用する必要があります。

CL 761460 は、container パッケージに、パッケージ実装者が具象コレクション、セット、またはマップ型の範囲で機能する抽象ヘルパー関数(ContainsAny、Subset、Arbitraryなど)を記述できるようにする、エクスポートされない 抽象Collection、Set、Map制約インターフェース型を追加します。これらを簡単な解説とともに以下に再現しますが、これらはどの提案の一部でもありません。これらはテストでの適合性を保証するだけです。詳細については、個別の提案を参照してください。

// _AbstractCollection は、*hash.Map、*hash.Set、*ordered.Map、またはset.Setのような、
// 要素Eを持つコレクションCをモデル化します。
type _AbstractCollection[E any, C _AbstractCollection[E, C]] interface {
	Clear()
	Clone() C
	Contains(E) bool
	Len() int
	String() string
}

// _AbstractMap は、*hash.Map または *ordered.Map のような、
// キーKから値VへのマッピングMをモデル化します。
type _AbstractMap[K, V any, M _AbstractMap[K, V, M]] interface {
	_AbstractCollection[K, M]

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

// _AbstractSet は、*hash.Set または set.Set のような、
// 要素Eを持つセットSをモデル化します。
type _AbstractSet[E any, S _AbstractSet[E, S]] interface {
	_AbstractCollection[E, S]

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

今のところ、これらの抽象型はエクスポートされず、具象コレクション型の適合性を保証するためのGoの規約のドキュメントとして機能するだけです。まだ公開する予定はありませんが、具象コレクション型での経験を積んだ後に、後続のリリースで公開する可能性があります。それまでの間、ユーザーは必要に応じて最小限の制約型を定義できます。これは、抽象セット全体でジェネリックな Take 関数のような例です(CL 761460 より)。

// _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
}

各インターフェースに含まれるメソッドのセットには、ある種の任意性があります。一部のデータ構造では、メソッドがより効率的な特殊化された実装を可能にします。しかし、考えられるすべての操作がインターフェースに追加された場合、実装者への負担は不当に大きくなります。

例えば、Setインターフェースに Subset(Set) bool メソッドを含めるべきか、それともSubsetはTakeの例のように抽象セット全体でジェネリックな操作として記述されるべきでしょうか?順序付きセットは、2つのオペランドが互いに素な範囲を持つ場合にSubsetテストを迅速に拒否できますが、それでも一般的なケースではSubsetテストは通常O(n)であるため、インターフェースからSubsetを省略することにしました。対照的に、SetとMapのインターフェースで DeleteFunc を保持しました。なぜなら、それがないと、ツリーの各要素を条件付きで削除するのは漸近的に悪化するためです(O(n)ではなくO(n log n))。

メソッドの特定のセットへのコミットメントを遅らせることで、実践から学ぶことができます。最終的に、標準的な制約型を全く公開する必要がないことが判明するかもしれません。

コレクションのJSONマーシャリング

コレクションは以下のようにJSONにマーシャル/アンマーシャルされます。

  • マップは、キー型の扱いを含め、組み込みマップとまったく同じようにマーシャルされます。JSON v2では、hashed.Map のマーシャリングは、挿入順序ではないマップに対して Deterministic オプションを尊重し、trueの場合はキーをソートします。挿入順序を保持するマップは常に挿入順にマーシャルされ、sorted.Map は常にソートされたキー順にマーシャルされます。

  • セットはJSON配列としてマーシャルされます。セット要素に対する特別な扱いはありません(JSON配列要素は文字列である必要はないため)。それらは他のGo値と同様にマーシャルされます。v2の Deterministic オプションは、set.Set および hashed.Set で尊重されます。trueの場合、要素のマーシャルされたバイトスライスは辞書順にソートされます(これは、マップキーとして使用される同じ要素とは異なる順序になる可能性があります)。sorted.Set では要素はソート順にマーシャルされます。

  • heap.Heap には組み込みのマーシャリング動作はありません。ヒープをマーシャルするユースケースはありません。JSON v2ユーザーは、必要であれば heap.Heap 用の独自のマーシャラーをインストールできます。

その他の合理化

このドキュメントの残りの部分では、現在の提案セットにつながった多くの小さな設計上の選択肢のいくつかを簡単に説明します。

メソッドは、繰り返しルックアップを避けるために、可能な限り多くの情報を返します。例えば:

  • ほとんどのミューテーションメソッドは、コレクションのサイズを変更したかどうかを報告します。
  • Map.Set および Map.Delete は、前のキー(存在する場合)と、既存のキーをゼロ値と区別するためのブール値を返します。
  • Get は、ブール値を提供するAtのバリアントです。(Atは式での使用の便宜のために提供されます。)

Map.Set は、組み込みマップに従って、同じキーを持つ既存のエントリをすべて置き換えるべきです。

セットとは異なり、マップにはEqualメソッドがありません。なぜなら、マップの値は比較不可能である可能性があるからです。

基本的なセット操作(Intersects、Unionなど)は、Setインターフェースの一部であり、さまざまな表現形式にわたる効率的な具象実装を可能にします。たとえこれらの多くが、この表に示すように、All、Len、Contains のみを使用して抽象的に表現できたとしても、ある程度の漸近的パフォーマンスコストがかかります。

- Union{,With}               interface{ All() iter.Seq[E] }
- Intersection               interface{ All() iter.Seq[E]; Contains(E) bool; Len() int }
- IntersectionWith           interface{                    Contains(E) bool }
- Difference                 interface{ All() iter.Seq[E]; Contains(E) bool }
- DifferenceWith             interface{ All() iter.Seq[E]; Contains(E) bool }
- SymmetricDifference{,With} interface{ All() iter.Seq[E] }

Set.{Take,Arbitrary,Subset,Superset} のような二次的な操作はインターフェースから削除され、抽象セットインターフェースを使用したジェネリック操作として表現されました。これもまた、潜在的な漸近的パフォーマンスコストがかかります。DeleteFunc は保持されました。

Unionのようなセット代数演算は純粋に関数型であり、結果を新しいセットとして返します。それぞれに、左オペランドを変更し、結果を返さない -With バリアントが付属しています。この2つのバリアントは、それぞれ「便利」と「メモリ効率が良い」です。math/big.Int APIでの経験と、意図しない変更や結果の使用忘れのリスクを避けるために、それらを単一のメソッドに統合するアイデアは却下しました。

KeySetView[M, K, V] ラッパー型を定義して、基になる Map[K,V] 型Mのキーセットを使用して Set[K] 抽象を満たすことが可能です。(もちろん、セットへの要素の挿入は無意味であり、パニックしなければなりません。)

対称性のために、AbstractMapの各メソッドと既存の「maps」パッケージによって提供される操作を検討しましょう。

  • maps.Clearなし:組み込みの clear(m) で対応
  • AbstractMap.Clone = maps.Clone
  • maps.Containsなし; _, ok = m[k] で対応しますが、提案 #67377 を参照してください。
  • maps.Lenなし: 組み込みの len(m) で対応
  • AbstractMaps.All = maps.All
  • maps.Getなし: m[k] で対応
  • maps.Deleteなし: delete(m, k) で対応
  • AbstractMaps.DeleteFunc = maps.DeleteFunc
  • maps.Lookupなし: v, ok = m[k] で対応
  • AbstractMaps.Keys = maps.Keys
  • maps.Setなし: prev, ok = m[k]; m[k] = newval で対応
  • AbstractMaps.Values = maps.Values

これらのうち5つ(Clone、DeleteFunc、All、Keys、Values)は完全に並列です。残りはすべて組み込み演算子で対応されます。
maps.Contains を追加提案することを検討するかもしれません。Contains は、式コンテキストでの _, ok = s[k] よりも便利です。