المجموعات Set في Golang: map[T]struct{} والعمليات ومجموعة عامة

الأسلوب المعتاد: خريطة بقيم فارغة

لا تملك Go كلمة set ولا مجموعة في المكتبة القياسية. الخريطة التي مفاتيحها العناصر وقيمها لا تحمل شيئًا تؤدّي المهمة.

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{}{} قيمته الوحيدة. يشغل صفر بايت، فتخزّن الخريطة المفاتيح ولا شيء غيرها.

كل قواعد الخرائط تنطبق: يجب أن تكون المفاتيح قابلة للمقارنة، وترتيب المرور عشوائي، والخريطة nil تسبّب panic عند الكتابة، والكتابات المتزامنة تحتاج قفلًا. تشرح صفحة الخرائط كلًا منها.

map[T]struct{} أم map[T]bool

الكتابة الشائعة الأخرى هي map[T]bool. تُقرأ أفضل لأن المفتاح المفقود يعيد false:

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

المقابل:

الصف الثالث هو السبب الحقيقي لتفضيل كثير من قواعد الشيفرة البنية الفارغة: مع bool سيكتب أحدهم يومًا s[k] = false فيتوقّف len(s) عن أن يكون عدد الأعضاء. وللمجموعات الصغيرة لا يهمّ فرق الذاكرة.

إزالة التكرار من شريحة

أشيع استخدام للمجموعة هو إزالة التكرار. يحتفظ هذا بأول ظهور لكل قيمة ويحافظ على الترتيب:

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]

الاتحاد والتقاطع والفرق

جبر المجموعات بضع حلقات. مرّ على المجموعة الأصغر عند فحص العضوية في الأخرى، لأن كل بحث يستغرق وقتًا ثابتًا في المتوسّط.

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 موجودة فقط لجعل المخرجات ثابتة. طباعة مجموعة بالمرور عليها تعطي ترتيبًا مختلفًا في كل تشغيل. تحتاج maps.Keys وslices.Sorted إلى Go 1.23.

النوع المسمّى مثل type set map[string]struct{} يبقى خريطة: تفهرسه وتمرّ عليه بـ range وتحذف منه بـ delete بالطريقة نفسها، ويمكنك تعليق توابع عليه.

نوع Set عام صغير

مع الأنواع العامة (Go 1.18) يغطّي نوع واحد كل أنواع العناصر القابلة للمقارنة. وهذا يكفي معظم البرامج:

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

تغليف الخريطة في بنية يخفي ضجيج struct{}{} ويضمن أن دالة البناء تنشئ الخريطة، فيزول panic الخريطة nil. لا يمكن أن تكون Sorted تابعًا: لا يستطيع التابع تعريف معاملات نوع خاصة به أو تشديد قيد comparable الخاص بالنوع، والترتيب يحتاج cmp.Ordered. تشرح صفحة الأنواع العامة القيود.

إذا احتجت مجموعة كاملة الميزات (صيغ آمنة للخيوط، وعمليات كثيرة)، توجد حزم خارجية مثل github.com/deckarep/golang-set. لكن في معظم الشيفرات يستخدم مبرمجو Go أسلوب الخريطة أو نوعًا من 30 سطرًا مثل هذا.

مجموعات من البنى

أي نوع قابل للمقارنة يمكن أن يكون عنصرًا، بما في ذلك البنى ذات الحقول القابلة للمقارنة. وهذا يجعل فحوص "هل رأيت هذا الزوج" مباشرة:

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

لا يمكن أن تكون الشرائح والخرائط عناصر مجموعة. لتتبّع الشرائح الفريدة، حوّل كلًا منها إلى مفتاح قابل للمقارنة أولًا، مثل مصفوفة ثابتة الحجم، أو نص مبني بـ fmt.Sprint.

أخطاء شائعة

• نسيان التهيئة. var s map[string]struct{} قيمتها nil؛ وأول إضافة تسبّب panic.
• طباعة مجموعة وتوقّع مخرجات ثابتة. رتّب الأعضاء أولًا.
• استخدام map[T]bool وتخزين false. عندها لا يعدّ len الأعضاء. استخدم delete للحذف.