Docs executáveis de Go: Sets

Q: Devo usar map[T]bool ou map[T]struct{} para um set em Go?

map[T]struct{} deixa a intenção explícita e os seus valores ocupam zero bytes. map[T]bool é mais natural de ler (if seen[x]), porque uma chave ausente devolve false. Os dois estão corretos; a diferença de memória só importa em sets muito grandes. Escolha um e mantenha a consistência.

O idioma: um map com valores vazios

Go não tem a palavra-chave set nem um set na biblioteca padrão. Um map cujas chaves são os elementos e cujos valores não carregam nada resolve.

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{} é o tipo struct vazia e struct{}{} é o seu único valor. Ele ocupa zero bytes, então o map guarda as chaves e mais nada.

Todas as regras de map valem: as chaves precisam ser comparáveis, a ordem de iteração é aleatória, um map nil causa panic na escrita e escritas concorrentes precisam de lock. A página de maps cobre cada uma delas.

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

A outra forma comum é map[T]bool. Ela é mais legível, porque uma chave ausente devolve false:

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

Os prós e contras:

	`map[T]struct{}`	`map[T]bool`
Tamanho do valor	0 bytes	1 byte (mais alinhamento)
Teste de pertinência	`_, ok := s[k]`	`s[k]`
Ambiguidade	nenhuma	`s[k] = false` é um terceiro estado

A terceira linha é o motivo real para muitos códigos preferirem a struct vazia: com bool, alguém acaba escrevendo s[k] = false e len(s) deixa de ser o número de membros. Em sets pequenos a diferença de memória não importa.

Removendo duplicados de um slice

O uso mais comum de um set é eliminar duplicados. Isto mantém a primeira ocorrência de cada valor e preserva a ordem:

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))
}

Saída:

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

União, interseção, diferença

Álgebra de conjuntos são alguns laços. Percorra o set menor ao testar a pertinência no outro, já que cada busca leva tempo constante em média.

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 existe só para deixar a saída estável. Imprimir um set percorrendo-o com range dá uma ordem diferente a cada execução. maps.Keys e slices.Sorted exigem o Go 1.23.

Um tipo nomeado como type set map[string]struct{} continua sendo um map: você o indexa, percorre com range e usa delete do mesmo jeito, e pode pendurar métodos nele.

Um pequeno Set genérico

Com generics (Go 1.18), um único tipo cobre todo tipo de elemento comparável. Isto é suficiente para a maioria dos programas:

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))
}

Envolver o map em uma struct esconde o ruído do struct{}{} e garante que o map seja criado pelo construtor, o que elimina o panic do map nil. Sorted não pode ser um método: um método não pode declarar os próprios parâmetros de tipo nem restringir mais a restrição comparable do tipo, e ordenar exige cmp.Ordered. A página de generics explica as restrições.

Se você precisar de um set completo (variantes seguras para concorrência, muitas operações), existem pacotes de terceiros como github.com/deckarep/golang-set. Para a maior parte do código, o idioma do map ou um tipo de 30 linhas como este é o que programadores Go usam.

Sets de structs

Qualquer tipo comparável pode ser um elemento, inclusive structs com campos comparáveis. Isso torna direta a verificação "já vi este par?":

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

Slices e maps não podem ser elementos de set. Para registrar slices únicos, converta cada um antes para uma chave comparável, por exemplo um array de tamanho fixo ou uma string montada com fmt.Sprint.

Erros comuns

Esquecer de inicializar. var s map[string]struct{} é nil; a primeira adição causa panic.
Imprimir um set esperando saída estável. Ordene os membros antes.
Usar map[T]bool e guardar false. Aí o len deixa de contar os membros. Use delete para remover.

Perguntas frequentes

Go tem um tipo set?

Não. A biblioteca padrão não tem set. O idioma é um map cujos valores não carregam informação: map[string]struct{}. Adicionar é s[k] = struct{}{}, verificar pertinência é _, ok := s[k], remover é delete(s, k) e o tamanho é len(s).

Devo usar map[T]bool ou map[T]struct{} para um set em Go?

map[T]struct{} deixa a intenção explícita e os seus valores ocupam zero bytes. map[T]bool é mais natural de ler (if seen[x]), porque uma chave ausente devolve false. Os dois estão corretos; a diferença de memória só importa em sets muito grandes. Escolha um e mantenha a consistência.

Como remover duplicados de um slice em Go?

Para manter a primeira ocorrência na ordem original, faça um laço e registre os valores vistos em um map[T]struct{}, acrescentando só os ainda não vistos. Se a ordem não importar, ordene e descarte os duplicados adjacentes: slices.Sort(s); s = slices.Compact(s).

Conceitos relacionados