Dokumentacja Go z przykładami: Zbiory

Q: Czego użyć jako zbioru w Go: map[T]bool czy map[T]struct{}?

map[T]struct{} jasno pokazuje intencję, a jej wartości zajmują zero bajtów. map[T]bool czyta się naturalniej (if seen[x]), bo brakujący klucz zwraca false. Oba podejścia są poprawne; różnica w pamięci ma znaczenie tylko przy bardzo dużych zbiorach. Wybierz jedno i trzymaj się go konsekwentnie.

Idiom: mapa z pustymi wartościami

Go nie ma słowa kluczowego set ani zbioru w bibliotece standardowej. Wystarczy mapa, której kluczami są elementy, a wartości nic nie niosą.

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{} to typ pustej struktury, a struct{}{} to jego jedyna wartość. Zajmuje zero bajtów, więc mapa przechowuje tylko klucze.

Obowiązują wszystkie zasady map: klucze muszą być porównywalne, kolejność iteracji jest losowa, zapis do mapy nil wywołuje panic, a współbieżne zapisy wymagają blokady. Każdą z nich omawia strona o mapach.

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

Druga popularna forma to map[T]bool. Czyta się ją lepiej, bo brakujący klucz zwraca false:

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

Porównanie:

	`map[T]struct{}`	`map[T]bool`
Rozmiar wartości	0 bajtów	1 bajt (plus wyrównanie)
Test przynależności	`_, ok := s[k]`	`s[k]`
Niejednoznaczność	brak	`s[k] = false` to trzeci stan

Trzeci wiersz to prawdziwy powód, dla którego wiele projektów woli pustą strukturę: przy bool ktoś w końcu napisze s[k] = false i len(s) przestanie być liczbą elementów. Przy małych zbiorach różnica w pamięci nie ma znaczenia.

Usuwanie duplikatów ze slice'a

Najczęstsze zastosowanie zbioru to deduplikacja. Ten kod zachowuje pierwsze wystąpienie każdej wartości i kolejność:

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

Wynik:

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

Suma, iloczyn, różnica

Algebra zbiorów to kilka pętli. Przechodź po mniejszym zbiorze, sprawdzając przynależność w drugim, bo każde wyszukiwanie zajmuje średnio stały czas.

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 istnieje tylko po to, żeby wynik był stabilny. Wypisanie zbioru przez przejście po nim range daje przy każdym uruchomieniu inną kolejność. maps.Keys i slices.Sorted wymagają Go 1.23.

Nazwany typ, taki jak type set map[string]struct{}, nadal jest mapą: indeksujesz go, przechodzisz po nim range i usuwasz z niego przez delete tak samo, a do tego możesz dodać do niego metody.

Mały generyczny Set

Dzięki generykom (Go 1.18) jeden typ obsługuje każdy porównywalny typ elementu. Większości programów to wystarczy:

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

Opakowanie mapy w strukturę ukrywa szum struct{}{} i gwarantuje, że mapę tworzy konstruktor, co eliminuje panic przy mapie nil. Sorted nie może być metodą: metoda nie może deklarować własnych parametrów typu ani zawężać ograniczenia comparable typu, a sortowanie wymaga cmp.Ordered. Ograniczenia wyjaśnia strona o generykach.

Jeśli potrzebujesz zbioru z pełnym zestawem funkcji (warianty bezpieczne wątkowo, wiele operacji), istnieją pakiety zewnętrzne, takie jak github.com/deckarep/golang-set. W większości kodu programiści Go używają idiomu z mapą albo 30-linijkowego typu takiego jak ten.

Zbiory struktur

Elementem może być dowolny porównywalny typ, także struktury z porównywalnymi polami. Dzięki temu sprawdzenie „czy widziałem już tę parę” jest proste:

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

Slice'y i mapy nie mogą być elementami zbioru. Aby śledzić unikalne slice'y, najpierw zamień każdy z nich na porównywalny klucz, na przykład tablicę o stałym rozmiarze albo string zbudowany przez fmt.Sprint.

Typowe błędy

Brak inicjalizacji. var s map[string]struct{} to nil; pierwsze dodanie wywołuje panic.
Wypisywanie zbioru z oczekiwaniem stabilnego wyniku. Najpierw posortuj elementy.
Używanie map[T]bool i zapisywanie false. Wtedy len przestaje liczyć elementy. Do usuwania używaj delete.

Najczęściej zadawane pytania

Czy Go ma typ zbioru (set)?

Nie. Biblioteka standardowa nie ma zbioru. Idiomem jest mapa, której wartości nie niosą żadnej informacji: map[string]struct{}. Dodanie to s[k] = struct{}{}, sprawdzenie przynależności to _, ok := s[k], usunięcie to delete(s, k), a rozmiar to len(s).

Czego użyć jako zbioru w Go: map[T]bool czy map[T]struct{}?

map[T]struct{} jasno pokazuje intencję, a jej wartości zajmują zero bajtów. map[T]bool czyta się naturalniej (if seen[x]), bo brakujący klucz zwraca false. Oba podejścia są poprawne; różnica w pamięci ma znaczenie tylko przy bardzo dużych zbiorach. Wybierz jedno i trzymaj się go konsekwentnie.

Jak usunąć duplikaty ze slice'a w Go?

Aby zachować pierwsze wystąpienie i kolejność, przejdź pętlą po elementach, zapamiętuj widziane wartości w map[T]struct{} i dopisuj tylko te niewidziane. Jeśli kolejność nie ma znaczenia, posortuj i usuń sąsiadujące duplikaty: slices.Sort(s); s = slices.Compact(s).

Powiązane zagadnienia