Go

Implement a generic Set[T] with union, intersection and iteration.

Question 134MediumGo 1.22 to 1.25
type Set[T comparable] map[T]struct{}

func SetOf[T comparable](vs ...T) Set[T] {
    s := make(Set[T], len(vs))
    for _, v := range vs {
        s[v] = struct{}{}
    }
    return s
}

func (s Set[T]) Add(v T)           { s[v] = struct{}{} }
func (s Set[T]) Has(v T) bool      { _, ok := s[v]; return ok }
func (s Set[T]) All() iter.Seq[T]  { return maps.Keys(s) }

func (s Set[T]) Union(o Set[T]) Set[T] {
    r := maps.Clone(s)
    if r == nil {
        r = Set[T]{}
    }
    maps.Copy(r, o)
    return r
}

func (s Set[T]) Intersect(o Set[T]) Set[T] {
    if len(o) < len(s) {
        s, o = o, s // iterate the smaller set
    }
    r := Set[T]{}
    for v := range s {
        if o.Has(v) {
            r.Add(v)
        }
    }
    return r
}

// Deterministic output for tests:
a, b := SetOf(1, 2, 3), SetOf(2, 3, 4)
fmt.Println(slices.Sorted(a.Intersect(b).All())) // [2 3]

Points to mention:

  • struct{} values take zero bytes.
  • Map iteration order is randomized, so sort the result before asserting on it.
  • A map-based Set is a reference type. Methods mutate in place, and var s Set[int]; s.Add(1) panics on a nil map.
  • maps.Clone of a nil map returns nil, hence the nil check in Union.

More on Generics

All 36 Generics questions