Docs Go exécutables : Ensembles

Q: Faut-il utiliser map[T]bool ou map[T]struct{} pour un ensemble en Go ?

map[T]struct{} rend l'intention explicite et ses valeurs occupent zéro octet. map[T]bool se lit plus naturellement (if seen[x]) parce qu'une clé absente renvoie false. Les deux sont corrects ; la différence de mémoire ne compte que pour de très grands ensembles. Choisissez-en un et restez cohérent.

L'idiome : une map aux valeurs vides

Go n'a pas de mot-clé set ni d'ensemble dans la bibliothèque standard. Une map dont les clés sont les éléments et dont les valeurs ne portent rien fait l'affaire.

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{} est le type struct vide et struct{}{} sa seule valeur. Elle occupe zéro octet, donc la map ne stocke que les clés.

Toutes les règles des maps s'appliquent : les clés doivent être comparables, l'ordre d'itération est aléatoire, une map nil provoque un panic à l'écriture, et les écritures concurrentes demandent un verrou. La page sur les maps traite chacune d'elles.

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

L'autre écriture courante est map[T]bool. Elle se lit mieux parce qu'une clé absente renvoie false :

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

Les compromis :

	`map[T]struct{}`	`map[T]bool`
Taille de la valeur	0 octet	1 octet (plus l'alignement)
Test d'appartenance	`_, ok := s[k]`	`s[k]`
Ambiguïté	aucune	`s[k] = false` est un troisième état

La troisième ligne est la vraie raison pour laquelle beaucoup de bases de code préfèrent la struct vide : avec bool, quelqu'un finit par écrire s[k] = false et len(s) cesse d'être le nombre de membres. Pour de petits ensembles, la différence de mémoire n'a pas d'importance.

Supprimer les doublons d'une slice

L'usage le plus courant d'un ensemble est la déduplication. Ce code garde la première occurrence de chaque valeur et préserve l'ordre :

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

Sortie :

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

Union, intersection, différence

L'algèbre des ensembles tient en quelques boucles. Parcourez le plus petit ensemble quand vous testez l'appartenance à l'autre, puisque chaque recherche prend en moyenne un temps constant.

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 n'existe que pour rendre la sortie stable. Afficher un ensemble en le parcourant donne un ordre différent à chaque exécution. maps.Keys et slices.Sorted demandent Go 1.23.

Un type nommé comme type set map[string]struct{} reste une map : vous l'indexez, faites un range dessus et un delete de la même façon, et vous pouvez lui ajouter des méthodes.

Un petit Set générique

Avec les génériques (Go 1.18), un seul type couvre tous les types d'éléments comparables. C'est suffisant pour la plupart des programmes :

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

Envelopper la map dans une struct masque le bruit de struct{}{} et garantit que la map est créée par le constructeur, ce qui supprime le panic de la map nil. Sorted ne peut pas être une méthode : une méthode ne peut ni déclarer ses propres paramètres de type ni resserrer la contrainte comparable du type, et le tri demande cmp.Ordered. La page sur les génériques explique les contraintes.

Si vous avez besoin d'un ensemble complet (variantes sûres en concurrence, nombreuses opérations), des packages tiers comme github.com/deckarep/golang-set existent. Pour la plupart du code, l'idiome de la map ou un type de 30 lignes comme celui-ci est ce qu'utilisent les développeurs Go.

Ensembles de structs

Tout type comparable peut être un élément, y compris les structs aux champs comparables. Les tests du genre « ai-je déjà vu cette paire » deviennent directs :

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

Les slices et les maps ne peuvent pas être des éléments d'ensemble. Pour suivre des slices uniques, convertissez d'abord chacune en clé comparable, par exemple un tableau de taille fixe, ou une chaîne construite avec fmt.Sprint.

Erreurs courantes

Oublier d'initialiser. var s map[string]struct{} vaut nil ; le premier ajout provoque un panic.
Afficher un ensemble et s'attendre à une sortie stable. Triez d'abord les membres.
Utiliser map[T]bool et stocker false. len ne compte alors plus les membres. Utilisez delete pour retirer.

Questions fréquentes

Go a-t-il un type ensemble ?

Non. La bibliothèque standard n'a pas de set. L'idiome est une map dont les valeurs ne portent aucune information : map[string]struct{}. Ajouter s'écrit s[k] = struct{}{}, tester l'appartenance _, ok := s[k], supprimer delete(s, k), et la taille vaut len(s).

Faut-il utiliser map[T]bool ou map[T]struct{} pour un ensemble en Go ?

map[T]struct{} rend l'intention explicite et ses valeurs occupent zéro octet. map[T]bool se lit plus naturellement (if seen[x]) parce qu'une clé absente renvoie false. Les deux sont corrects ; la différence de mémoire ne compte que pour de très grands ensembles. Choisissez-en un et restez cohérent.

Comment supprimer les doublons d'une slice en Go ?

Pour garder la première occurrence dans l'ordre, bouclez et notez les valeurs déjà vues dans une map[T]struct{}, en n'ajoutant que celles qui n'ont pas été vues. Si l'ordre n'a pas d'importance, triez et retirez les doublons adjacents : slices.Sort(s); s = slices.Compact(s).

Concepts liés