Utilizing Sets With Golang Generics | by Noah Schumacher | Nov, 2022

Build your own fully-functional set type in Go

One of the things that frustrated me most when first learning Go (coming mostly from Python) was the lack of collection types like sets and their general operations. In this article, we will show how the introduction of generics in Go 1.18 allows us to create our own fully functional set types. all the code below my github go-archive,

You may be familiar with the incredibly useful data collection type that is a Set. A set is an unordered collection of unique items. Usually sets are implemented using hashmaps which make look-ups of values ​​O(1) (assuming no hash collisions). Sets have 4 main operations that make them particularly useful:

  1. Federation (a b) – is the set that contains all the elements in sets A and B.
  2. Crossroad (a b)— is the set that contains all the elements that are in the sets A and B.
  3. Supplement (ac) – is the set of elements that are in the universal set S but not in A. We’ll ignore the complement since it’s handled by the difference.
  4. gap (a , b, , is the set of elements present in a but not in b,

Let’s start with defining our set type in Go. First, we want to define what a set is and with generics we can use constraints to easily extend the set type to handle lots of different data types.

package collections

// A collection of unique comparable items. Uses a map with only true values
// to accomplish set functionality.
type Set[T comparable] map[T]bool

// Create a new empty set with the specified initial size.
func NewSet[T comparable](size int) Set[T]
return make(Set[T], size)

// Add a new key to the set
func (s Set[T]) Add(key T)
s[key] = true

// Remove a key from the set. If the key is not in the set then noop
func (s Set[T]) Remove(key T)
delete(s, key)

// Check if Set s contains key
func (s Set[T]) Contains(key T) bool
return s[key]

In this first section, we’ve created our own Set type that uses the built-in Map type. We restrict the keys of the map to be of comparable type. From the documentation, we know that Comparable types include

(Booleans, numbers, strings, pointers, channels, arrays of comparable types, structures whose fields are all comparable types)

We also add some basic methods on our types to add, remove and check for existence. With this, we are not ready to implement our set operations defined above. let’s start with Difference,

// A difference B | NOTE: A-B != B-A
func (a Set[T]) Difference(b Set[T]) Set[T]
resultSet := NewSet[T](0)
for key := range a
if !b.Contains(key)

return resultSet

Simple enough example. we just create a new set with 0 capacity (because we don’t know how big the new set will be) and then iterate over the set A adding only those elements that are not included in B,

next two operations Union And Intersection Follow a similar pattern – but this time we add a little (or potentially huge) customization.

// A union B
func (a Set[T]) Union(b Set[T]) Set[T]
small, large := smallLarge(a, b)

for key := range small

return large

// A intersect B
func (a Set[T]) Intersection(b Set[T]) Set[T]
small, large := smallLarge(a, b)

resultSet := NewSet[T](0)
for key := range small
if large.Contains(key)

return resultSet

// returns the small and large sets according to their len
func smallLarge[T comparable](a, b Set[T]) (Set[T], Set[T])
small, large := b, a
if len(b) > len(a)
small, large = a, b

return small, large

Both these methods are quite simple. In Union We are just iterating over one set and adding values ​​to the other set. In Intersection We are checking if the values ​​are in A are also in B and returning a set that only contains elements from both.

optimization comes from identifying which set is smaller smallLarge(a, b) Call. By doing this we allow the loop to iterate only over the smaller of the two sets. This could potentially save a lot of iterations if one set is very large and the other small.

However, in Federation we’re overwriting the larger set which can be either a either b, If we want to preserve the original set while doing union then we have to loop over both the sets.

Now we have a fully working set package. With a little more work we could add helpers for slices and more utility methods like a check for equality.

// A == B (all elements of A are in B and vice versa)
func (a Set[T]) Equals(b Set[T]) bool
return len(a.Difference(b)) == 0 && len(b.Difference(a)) == 0

// Create a Set from a slice.
func SliceToSet[T comparable](s []T) Set[T]
set := NewSet[T](len(s))
for _, item := range s

return set

// Union two slices. The provided slices do not need to be unique. Order not guaranteed.
func SliceUnion[T comparable](a, b []T) []T
aSet, bSet := SliceToSet(a), SliceToSet(b)
union := aSet.Union(bSet)
return union.ToSlice()

// Intersection of two slices. The provided slices do not need to be unique. Order not guaranteed.
func SliceIntersection[T comparable](a, b []T) []T
aSet, bSet := SliceToSet(a), SliceToSet(b)
intersection := aSet.Intersection(bSet)
return intersection.ToSlice()

With all of the above working we are able to do tasks like shown below:

func TestSets(t *testing.T) 
A := SliceToSet([]int1, 3, 5)
B := SliceToSet([]int0, 1, 2, 3, 4)

union := A.Union(B)
fmt.Println(union) // map[0:true 1:true 2:true 3:true 4:true 5:true]

C := SliceToSet([]string"a", "b", "noah")
D := SliceToSet([]string"a", "noah")
intersection := C.Intersection(D)
fmt.Println(intersection) // map[a:true noah:true]

fmt.Println(C.Equals(D)) // false

Leave a Reply