実行できるGoドキュメント: 集合（Set）

Q: Goに集合（Set）型はありますか？

ありません。標準ライブラリに集合はありません。イディオムは、値に情報を持たないマップ map[string]struct{} です。追加は s[k] = struct{}{}、存在確認は _, ok := s[k]、削除は delete(s, k)、サイズは len(s) です。

Q: Goの集合にはmap[T]boolとmap[T]struct{}のどちらを使うべきですか？

map[T]struct{} は意図が明確で、値は0バイトです。map[T]bool は存在しないキーが false を返すので、if seen[x] のように自然に読めます。どちらも正しく、メモリの差が問題になるのは非常に大きな集合だけです。どちらかを選んで一貫させましょう。

Q: Goでスライスから重複を取り除くには？

最初に現れたものを順序どおりに残すなら、ループしながら見た値を map[T]struct{} で記録し、まだ見ていないものだけを追加します。順序が重要でなければ、ソートして隣り合う重複を取り除きます：slices.Sort(s); s = slices.Compact(s)。

イディオム：値が空のマップ

Goに set キーワードはなく、標準ライブラリにも集合はありません。要素をキーにして、値に何も持たせないマップがその役目を果たします。

package main

import "fmt"

func main() {
	tags := map[string]struct{}{}

	// add
	tags["go"] = struct{}{}
	tags["backend"] = struct{}{}
	tags["go"] = struct{}{} // adding again changes nothing

	// has
	_, ok := tags["go"]
	fmt.Println("has go:", ok)

	// remove
	delete(tags, "backend")

	// size
	fmt.Println("size:", len(tags))

	for t := range tags {
		fmt.Println("member:", t)
	}
}

struct{} は空の構造体の型で、struct{}{} はその唯一の値です。0バイトしか使わないので、マップはキーだけを保存します。

マップのルールはすべて当てはまります。キーは比較可能でなければならず、反復順はランダムで、nilマップへの書き込みはpanicし、並行した書き込みにはロックが必要です。それぞれマップのページで扱っています。

map[T]struct{}かmap[T]boolか

もう1つよく使われる書き方は map[T]bool です。存在しないキーが false を返すので、こちらのほうが読みやすくなります。

seen := map[string]bool{}
seen["a"] = true
if seen["a"] { ... }

トレードオフは次のとおりです。

	`map[T]struct{}`	`map[T]bool`
値のサイズ	0バイト	1バイト（加えてアラインメント）
存在確認	`_, ok := s[k]`	`s[k]`
あいまいさ	なし	`s[k] = false` が3つ目の状態になる

多くのコードベースが空の構造体を好む本当の理由は3行目です。bool を使うと、いつか誰かが s[k] = false と書き、len(s) がメンバーの数ではなくなります。小さな集合ならメモリの差は問題になりません。

スライスから重複を取り除く

集合の最もよくある用途は重複の除去です。次のコードは各値の最初の出現を残し、順序を保ちます。

package main

import (
	"fmt"
	"slices"
)

func unique[T comparable](in []T) []T {
	seen := make(map[T]struct{}, len(in))
	out := make([]T, 0, len(in))
	for _, v := range in {
		if _, ok := seen[v]; ok {
			continue
		}
		seen[v] = struct{}{}
		out = append(out, v)
	}
	return out
}

func main() {
	fmt.Println(unique([]string{"b", "a", "b", "c", "a"}))
	fmt.Println(unique([]int{3, 1, 3, 3, 2}))

	// If order does not matter: sort, then drop adjacent duplicates.
	s := []int{3, 1, 3, 3, 2}
	slices.Sort(s)
	fmt.Println(slices.Compact(s))
}

出力：

[b a c]
[3 1 2]
[1 2 3]

和集合、積集合、差集合

集合の演算は数個のループで書けます。一方の集合での存在確認をするときは、小さいほうの集合を走査します。各検索は平均して定数時間だからです。

package main

import (
	"fmt"
	"maps"
	"slices"
)

type set map[string]struct{}

func of(items ...string) set {
	s := make(set, len(items))
	for _, it := range items {
		s[it] = struct{}{}
	}
	return s
}

func union(a, b set) set {
	out := maps.Clone(a)
	for k := range b {
		out[k] = struct{}{}
	}
	return out
}

func intersect(a, b set) set {
	if len(a) > len(b) {
		a, b = b, a
	}
	out := set{}
	for k := range a {
		if _, ok := b[k]; ok {
			out[k] = struct{}{}
		}
	}
	return out
}

func difference(a, b set) set {
	out := set{}
	for k := range a {
		if _, ok := b[k]; !ok {
			out[k] = struct{}{}
		}
	}
	return out
}

func sorted(s set) []string {
	return slices.Sorted(maps.Keys(s))
}

func main() {
	backend := of("go", "sql", "docker", "linux")
	devops := of("docker", "linux", "terraform")

	fmt.Println("union:     ", sorted(union(backend, devops)))
	fmt.Println("intersect: ", sorted(intersect(backend, devops)))
	fmt.Println("backend-only:", sorted(difference(backend, devops)))
}

sorted は出力を安定させるためだけにあります。集合をrangeして表示すると、実行するたびに順序が変わります。maps.Keys と slices.Sorted にはGo 1.23が必要です。

type set map[string]struct{} のような名前付きの型もマップであることに変わりはありません。同じようにインデックスを使い、range し、delete でき、メソッドを付けることもできます。

小さなジェネリックなSet

ジェネリクス（Go 1.18）を使えば、1つの型で比較可能なすべての要素の型をまかなえます。ほとんどのプログラムにはこれで十分です。

package main

import (
	"cmp"
	"fmt"
	"maps"
	"slices"
)

type Set[T comparable] struct {
	m map[T]struct{}
}

func NewSet[T comparable](items ...T) *Set[T] {
	s := &Set[T]{m: make(map[T]struct{}, len(items))}
	for _, it := range items {
		s.Add(it)
	}
	return s
}

func (s *Set[T]) Add(v T)    { s.m[v] = struct{}{} }
func (s *Set[T]) Remove(v T) { delete(s.m, v) }
func (s *Set[T]) Len() int   { return len(s.m) }
func (s *Set[T]) Has(v T) bool {
	_, ok := s.m[v]
	return ok
}

func (s *Set[T]) Union(o *Set[T]) *Set[T] {
	out := &Set[T]{m: maps.Clone(s.m)}
	for v := range o.m {
		out.Add(v)
	}
	return out
}

// Sorted is a free function because it needs a stricter constraint than the type.
func Sorted[T cmp.Ordered](s *Set[T]) []T {
	return slices.Sorted(maps.Keys(s.m))
}

func main() {
	a := NewSet(1, 2, 3)
	b := NewSet(3, 4)
	a.Add(2)
	fmt.Println(a.Len(), a.Has(2), a.Has(9))

	u := a.Union(b)
	fmt.Println(Sorted(u))

	words := NewSet("go", "rust")
	words.Remove("rust")
	fmt.Println(Sorted(words))
}

マップを構造体で包むと struct{}{} の雑音が隠れ、マップがコンストラクタで確実に作られるので、nilマップのpanicもなくなります。Sorted はメソッドにできません。メソッドは独自の型パラメータを宣言することも、型の comparable 制約を厳しくすることもできず、ソートには cmp.Ordered が必要だからです。制約についてはジェネリクスのページで説明しています。

多機能な集合（スレッドセーフな版、多数の操作）が必要なら、github.com/deckarep/golang-set のようなサードパーティのパッケージもあります。ほとんどのコードでは、Goプログラマーはマップのイディオムか、このような30行ほどの型を使っています。

構造体の集合

比較可能な型なら何でも要素になれ、比較可能なフィールドを持つ構造体も含まれます。これで「このペアを見たことがあるか」のチェックが直接書けます。

type edge struct{ from, to string }
visited := map[edge]struct{}{}
visited[edge{"a", "b"}] = struct{}{}

スライスとマップは集合の要素になれません。一意なスライスを記録するには、固定サイズの配列や fmt.Sprint で作った文字列など、先にそれぞれを比較可能なキーに変換します。

よくある間違い

初期化を忘れる。 var s map[string]struct{} はnilで、最初の追加でpanicします。
集合を表示して安定した出力を期待する。 先にメンバーをソートします。
map[T]bool を使って false を格納する。 すると len がメンバーの数を数えなくなります。削除には delete を使います。

よくある質問

Goに集合（Set）型はありますか？

ありません。標準ライブラリに集合はありません。イディオムは、値に情報を持たないマップ map[string]struct{} です。追加は s[k] = struct{}{}、存在確認は _, ok := s[k]、削除は delete(s, k)、サイズは len(s) です。

Goの集合にはmap[T]boolとmap[T]struct{}のどちらを使うべきですか？

map[T]struct{} は意図が明確で、値は0バイトです。map[T]bool は存在しないキーが false を返すので、if seen[x] のように自然に読めます。どちらも正しく、メモリの差が問題になるのは非常に大きな集合だけです。どちらかを選んで一貫させましょう。

Goでスライスから重複を取り除くには？

最初に現れたものを順序どおりに残すなら、ループしながら見た値を map[T]struct{} で記録し、まだ見ていないものだけを追加します。順序が重要でなければ、ソートして隣り合う重複を取り除きます：slices.Sort(s); s = slices.Compact(s)。