Golang Set: map[T]struct{}, İşlemler ve Generic bir Set

Kalıp: değerleri boş olan bir map

Go'da set anahtar kelimesi ve standart kütüphanede set yoktur. Anahtarları elemanlar olan ve değerleri hiçbir şey taşımayan bir map bu işi görür.

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{} boş struct tipidir ve struct{}{} onun tek değeridir. Sıfır bayt kaplar, bu yüzden map yalnızca anahtarları saklar.

Tüm map kuralları geçerlidir: anahtarlar karşılaştırılabilir olmalıdır, dolaşma sırası rastgeledir, nil bir map yazmada panic olur ve eşzamanlı yazmalar kilit gerektirir. Map'ler sayfası her birini anlatıyor.

map[T]struct{} mi, map[T]bool mu

Diğer yaygın yazım map[T]bool'dur. Eksik bir anahtar false döndürdüğü için daha iyi okunur:

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

Ödünleşimler:

Birçok kod tabanının boş struct'ı tercih etmesinin asıl nedeni üçüncü satırdır: bool ile biri eninde sonunda s[k] = false yazar ve len(s) üye sayısı olmaktan çıkar. Küçük set'ler için bellek farkı önemli değildir.

Bir slice'tan tekrarları kaldırmak

Bir set'in en yaygın kullanımı tekrar ayıklamaktır. Bu, her değerin ilk görüldüğü yeri tutar ve sırayı korur:

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

Çıktı:

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

Birleşim, kesişim, fark

Küme cebiri birkaç döngüden ibarettir. Diğerinde üyelik test ederken küçük olan set'i dolaşın, çünkü her arama ortalamada sabit zamanlıdır.

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 yalnızca çıktıyı kararlı yapmak için var. Bir set'i üzerinde range yaparak yazdırmak her çalıştırmada farklı bir sıra verir. maps.Keys ve slices.Sorted Go 1.23 gerektirir.

type set map[string]struct{} gibi adlandırılmış bir tip yine bir map'tir: ona aynı şekilde indeksler, üzerinde range yapar ve delete ile silersiniz; ayrıca ona metotlar ekleyebilirsiniz.

Küçük bir generic Set

Generics (Go 1.18) ile tek bir tip karşılaştırılabilir her eleman tipini karşılar. Çoğu program için bu yeterlidir:

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

Map'i bir struct içine sarmak struct{}{} gürültüsünü gizler ve map'in kurucu tarafından oluşturulmasını garanti eder; bu da nil map panic'ini ortadan kaldırır. Sorted bir metot olamaz: bir metot kendi tip parametrelerini tanımlayamaz ya da tipin comparable kısıtını daraltamaz, sıralama ise cmp.Ordered gerektirir. Kısıtları generics sayfası açıklıyor.

Tam özellikli bir set'e (thread-safe çeşitler, çok sayıda işlem) ihtiyacınız varsa github.com/deckarep/golang-set gibi üçüncü taraf paketler var. Çoğu kod için Go programcılarının kullandığı şey map kalıbı ya da bunun gibi 30 satırlık bir tiptir.

Struct set'leri

Karşılaştırılabilir alanlara sahip struct'lar dahil, karşılaştırılabilir her tip bir eleman olabilir. Bu, "bu çifti gördüm mü" kontrollerini doğrudan yapar:

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

Slice'lar ve map'ler set elemanı olamaz. Benzersiz slice'ları takip etmek için önce her birini karşılaştırılabilir bir anahtara dönüştürün; örneğin sabit boyutlu bir diziye ya da fmt.Sprint ile oluşturulmuş bir string'e.

Sık yapılan hatalar

• Başlatmayı unutmak. var s map[string]struct{} nil'dir; ilk ekleme panic olur.
• Bir set'i yazdırıp kararlı çıktı beklemek. Önce üyeleri sıralayın.
• map[T]bool kullanıp false saklamak. O zaman len artık üyeleri saymaz. Kaldırmak için delete kullanın.