Utilizing Sets With Golang Generics

Build your own fully-functional Set type in Go

One of the more frustrating things I found when first learning Go (coming from mostly Python) was the lack of collection types such as Sets and their common operations. In this article, we will show how the introduction of Generics in Go 1.18 can allow us to build our own fully functioning Set type. All code below can also be found at my GitHub go-collections.

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

1. Union (A ⋃ B) — is the Set that contains all the elements in Set A and B.
2. Intersection (A ∩ B)— is the Set that contains all the elements that are in Set A and B.
3. Complement (Ac) — is the Set of elements that are in the universal set S but are not in A. We will ignore complement since it is handled by Difference.
4. Difference (A − B) — is the Set of the elements that are in A but are not in B.

Let’s get started with defining our Set type in Go. First, we want to define what a Set is and with Generics we can utilize constraints to easily extend the Set type to handle lots of 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 created our Set type which utilizes the built-in map type. We restrict the key of the map to be of type Comparable. From the documentation, we know Comparable types include

(booleans, numbers, strings…