Guida Go interattiva: Set

Q: Per un set in Go conviene map[T]bool o map[T]struct{}?

map[T]struct{} rende esplicita l'intenzione e i suoi valori occupano zero byte. map[T]bool si legge in modo più naturale (if seen[x]) perché una chiave assente restituisce false. Sono corretti entrambi; la differenza di memoria conta solo per set molto grandi. Scegline uno e resta coerente.

L'idioma: una mappa con valori vuoti

Go non ha una parola chiave set né un set nella libreria standard. Fa il lavoro una mappa le cui chiavi sono gli elementi e i cui valori non contengono niente.

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{} è il tipo struct vuoto e struct{}{} è il suo unico valore. Occupa zero byte, quindi la mappa memorizza le chiavi e nient'altro.

Valgono tutte le regole delle mappe: le chiavi devono essere confrontabili, l'ordine di iterazione è casuale, una mappa nil va in panic in scrittura e le scritture concorrenti richiedono un lock. La pagina sulle mappe le tratta una per una.

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

L'altra forma comune è map[T]bool. Si legge meglio perché una chiave assente restituisce false:

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

I compromessi:

	`map[T]struct{}`	`map[T]bool`
Dimensione del valore	0 byte	1 byte (più l'allineamento)
Test di appartenenza	`_, ok := s[k]`	`s[k]`
Ambiguità	nessuna	`s[k] = false` è un terzo stato

La terza riga è il vero motivo per cui molte codebase preferiscono la struct vuota: con bool, prima o poi qualcuno scrive s[k] = false e len(s) smette di essere il numero di elementi. Per i set piccoli la differenza di memoria non conta.

Rimuovere i duplicati da uno slice

L'uso più comune di un set è la deduplicazione. Questo codice tiene la prima occorrenza di ogni valore e mantiene l'ordine:

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

Output:

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

Unione, intersezione, differenza

L'algebra dei set si riduce a pochi cicli. Scorri il set più piccolo quando verifichi l'appartenenza all'altro, dato che ogni ricerca richiede in media un tempo costante.

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 serve solo a rendere stabile l'output. Stampare un set scorrendolo con range dà un ordine diverso a ogni esecuzione. maps.Keys e slices.Sorted richiedono Go 1.23.

Un tipo con nome come type set map[string]struct{} resta una mappa: lo indicizzi, lo scorri con range e ci usi delete allo stesso modo, e puoi aggiungergli dei metodi.

Un piccolo Set generico

Con i generics (Go 1.18) un solo tipo copre ogni tipo di elemento confrontabile. Basta per la maggior parte dei programmi:

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

Racchiudere la mappa in una struct nasconde il rumore di struct{}{} e garantisce che la mappa venga creata dal costruttore, eliminando il panic da mappa nil. Sorted non può essere un metodo: un metodo non può dichiarare parametri di tipo propri né restringere il vincolo comparable del tipo, e l'ordinamento richiede cmp.Ordered. La pagina sui generics spiega i vincoli.

Se ti serve un set completo (varianti thread-safe, molte operazioni), esistono pacchetti di terze parti come github.com/deckarep/golang-set. Per la maggior parte del codice, i programmatori Go usano l'idioma della mappa o un tipo di 30 righe come questo.

Set di struct

Qualsiasi tipo confrontabile può essere un elemento, comprese le struct con campi confrontabili. Questo rende diretti i controlli del tipo "ho già visto questa coppia":

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

Slice e mappe non possono essere elementi di un set. Per tenere traccia di slice unici, converti prima ognuno in una chiave confrontabile, per esempio un array di dimensione fissa o una stringa costruita con fmt.Sprint.

Errori comuni

Dimenticare l'inizializzazione. var s map[string]struct{} è nil; la prima aggiunta va in panic.
Stampare un set aspettandosi un output stabile. Ordina prima gli elementi.
Usare map[T]bool e memorizzare false. A quel punto len non conta più gli elementi. Usa delete per rimuovere.

Domande frequenti

Go ha un tipo set?

No. La libreria standard non ha un set. L'idioma è una mappa i cui valori non portano informazioni: map[string]struct{}. Aggiungere è s[k] = struct{}{}, verificare l'appartenenza è _, ok := s[k], rimuovere è delete(s, k) e la dimensione è len(s).

Per un set in Go conviene map[T]bool o map[T]struct{}?

map[T]struct{} rende esplicita l'intenzione e i suoi valori occupano zero byte. map[T]bool si legge in modo più naturale (if seen[x]) perché una chiave assente restituisce false. Sono corretti entrambi; la differenza di memoria conta solo per set molto grandi. Scegline uno e resta coerente.

Come rimuovo i duplicati da uno slice in Go?

Per tenere la prima occorrenza nell'ordine originale, scorri lo slice e tieni traccia dei valori visti in una map[T]struct{}, aggiungendo solo quelli non ancora visti. Se l'ordine non conta, ordina ed elimina i duplicati adiacenti: slices.Sort(s); s = slices.Compact(s).

Concetti correlati