Set ב-Golang: map[T]struct{}, פעולות ו-Set גנרי

הניב: map עם ערכים ריקים

ל-Go אין מילת מפתח set ואין set בספרייה הסטנדרטית. map שהמפתחות שלו הם האיברים והערכים שלו לא נושאים כלום עושה את העבודה.

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{} הוא טיפוס ה-struct הריק ו-struct{}{} הוא הערך היחיד שלו. הוא תופס אפס בתים, כך שה-map שומר רק מפתחות.

כל הכללים של map חלים כאן: המפתחות חייבים להיות comparable, סדר המעבר אקראי, map שהוא nil גורם ל-panic בכתיבה, וכתיבות מקבילות דורשות נעילה. הדף על maps מכסה כל אחד מהם.

map[T]struct{} או map[T]bool

הכתיב הנפוץ השני הוא map[T]bool. הוא נקרא טוב יותר כי מפתח חסר מחזיר false:

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

השיקולים:

השורה השלישית היא הסיבה האמיתית שבהרבה בסיסי קוד מעדיפים את ה-struct הריק: עם bool, מישהו בסוף כותב s[k] = false ו-len(s) מפסיק להיות מספר האיברים. ב-sets קטנים ההבדל בזיכרון לא משנה.

הסרת כפילויות מ-slice

השימוש הנפוץ ביותר ב-set הוא הסרת כפילויות. הקוד הזה שומר את ההופעה הראשונה של כל ערך ומשמר את הסדר:

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

פלט:

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

איחוד, חיתוך, הפרש

אלגברה של sets היא כמה לולאות. עברו על ה-set הקטן יותר כשבודקים שייכות בשני, כי כל חיפוש לוקח בממוצע זמן קבוע.

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 קיימת רק כדי שהפלט יהיה יציב. הדפסת set באמצעות מעבר עליו עם range נותנת סדר שונה בכל הרצה. maps.Keys ו-slices.Sorted דורשות Go 1.23.

טיפוס עם שם כמו type set map[string]struct{} הוא עדיין map: ניגשים אליו לפי מפתח, עוברים עליו עם range ומוחקים ממנו עם delete באותה צורה, ואפשר להצמיד לו מתודות.

Set גנרי קטן

עם generics (Go 1.18), טיפוס אחד מכסה כל טיפוס איבר שהוא comparable. זה מספיק לרוב התוכניות:

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 ב-struct מסתירה את הרעש של struct{}{} ומבטיחה שה-map נוצר בבנאי, וזה מבטל את ה-panic של map שהוא nil. Sorted לא יכולה להיות מתודה: מתודה לא יכולה להצהיר על פרמטרי טיפוס משלה או להדק את האילוץ comparable של הטיפוס, ומיון דורש cmp.Ordered. הדף על generics מסביר אילוצים.

אם צריך set עם כל היכולות (גרסאות בטוחות ל-threads, הרבה פעולות), יש חבילות צד שלישי כמו github.com/deckarep/golang-set. ברוב הקוד, מתכנתי Go משתמשים בניב של map או בטיפוס של 30 שורות כמו זה.

Sets של structs

כל טיפוס comparable יכול להיות איבר, כולל structs עם שדות comparable. זה הופך בדיקות של "האם כבר ראיתי את הזוג הזה" לישירות:

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

slices ו-maps לא יכולים להיות איברים של set. כדי לעקוב אחרי slices ייחודיים, המירו קודם כל אחד למפתח comparable, למשל מערך בגודל קבוע, או מחרוזת שנבנתה עם fmt.Sprint.

טעויות נפוצות

• שכחה לאתחל. var s map[string]struct{} הוא nil; ההוספה הראשונה גורמת ל-panic.
• הדפסת set וציפייה לפלט יציב. מיינו את האיברים קודם.
• שימוש ב-map[T]bool ושמירת false. אז len כבר לא סופרת איברים. השתמשו ב-delete כדי להסיר.