Множество (set) в Golang: map[T]struct{} и обобщённый Set

Идиома: мапа с пустыми значениями

Ключевого слова set в Go нет, и в стандартной библиотеке множества тоже нет. С задачей справляется мапа, ключи которой это элементы, а значения ничего не несут.

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{}{} его единственное значение. Оно занимает ноль байт, так что мапа хранит только ключи.

Действуют все правила мап: ключи должны быть сравнимыми, порядок обхода случайный, запись в nil-мапу вызывает панику, а конкурентная запись требует блокировки. Каждое правило разобрано на странице о мапах.

map[T]struct{} или map[T]bool

Другой распространённый вариант записи это map[T]bool. Он читается лучше, потому что отсутствующий ключ возвращает false:

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

Компромиссы:

Третья строка и есть настоящая причина, по которой многие кодовые базы предпочитают пустую структуру: с 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) один тип покрывает любой сравнимый тип элементов. Для большинства программ этого достаточно:

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-мапы. 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; первое же добавление вызовет панику.
• Печать множества в расчёте на стабильный вывод. Сначала отсортируйте элементы.
• map[T]bool с сохранённым false. Тогда len больше не считает элементы. Для удаления используйте delete.