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.Cloneof a nil map returns nil, hence the nil check inUnion.
More on Generics
- Q132Implement a generic stack and a generic FIFO queue. What are the gotchas?
- Q133Implement a generic binary search tree keyed by
cmp.Orderedwith an in-order iterator. - Q135Design a thread-safe generic cache with a
GetOrLoadmethod. What concurrency pitfalls exist? - Q136Write generic
Map,FilterandReducefor slices. Why aren't they in the standard library'sslicespackage? - Q137What is
golang.org/x/exp/constraints, how does it relate tocmp.Ordered, and how do you define your own numeric constraint? - Q138Explain the
cmppackage:Compare,Less,Or. How do you do a multi-key sort, and how is NaN handled?