Create Set in Go using Map

Getting Started #

If you have been programming in Go for a while or have just picked it up, you might know that Go doesn't have any native Set type, if you didn't knew, now you know 😀.

In this article you are going to learn how to create a Set using the native Map type.

Defining Operations #

A Set mainly has three functions:

Add: add a new value to the set.
Remove: remove a value from the set.
Contains: check if a value exists in the set.

Writing Set #

Let's create a set that can holds string values.

type StringSet struct {
	m map[string]struct{}
}

func NewStringSet() StringSet {
	return StringSet{
		m: make(map[string]struct{}),
	}
}

func (s StringSet) Add(value string) {
	s.m[value] = struct{}{}
}

func (s StringSet) Contains(value string) bool {
	_, ok := s.m[value]
    return ok
}

func (s StringSet) Remove(value string) {
	delete(s.m, value)
}

We choose a map of type map[string]struct{}, the key of the map is your actual value. Additionally we use the value, ok := idiom to check the existance of key in the map.

Let's write some sample code that uses this StringSet.

package main

import "fmt"

func main() {
	set := NewStringSet()

	set.Add("1")
	set.Add("2")

	fmt.Println(set.Contains("1")) // Prints 'true'
	fmt.Println(set.Contains("3")) // Prints 'false'

	set.Remove("1")

	fmt.Println(set.Contains("1")) // Prints 'false'
}
main.go

Go only allows types to be used as keys that are comparable. These comparable types include bool, int, string, array (not slices), interface, struct.

Some types that cannot be used as keys of a map include slice, functions, map. If you try to use these types as keys of map as below:

But what about Set for other types?

This is all great but what about IntSet, FloatSet and set for various other types, do you have to write all this repetitive code 😰? this is where generics comes to rescue. If you have not already, learn about generics.

Generic Set #

Most of the code stays the same as before, we only add generic type T to the struct and all the functions.

// generics only allows types that are comparable
type AllowedKeys interface {
	~string |
	~int | ~int8 | ~int16 | ~int32 | ~int64 |
	~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr |
	~float32 | ~float64
}

type Set[T AllowedKeys] struct {
	m map[T]struct{}
}

func NewSet[T AllowedKeys]() Set[T] {
	return Set[T]{
		m: make(map[T]struct{}),
	}
}

func (s Set[T]) Add(data T) {
	s.m[data] = struct{}{}
}

func (s Set[T]) Remove(data T) {
	delete(s.m, data)
}

func (s Set[T]) Contains(data T) bool {
	_, ok := s.m[data]
	return ok
}

Let's use the above Set to create an integer set.

func main() {
	s := NewSet[int]()

	s.Add(10)

	fmt.Println(s.Contains(10))
	fmt.Println(s.Contains(11))

	s.Remove(10)

	fmt.Println(s.Contains(10))
}
main.go

We can simplify the generic Set code a little bit more by using the constraints package from google.

Install the package:

 go get golang.org/x/exp/constraints

And update the generic Set code:

type Set[T constraints.Ordered] struct {
	m map[T]struct{}
}

func NewSet[T constraints.Ordered]() Set[T] {
	return Set[T]{
		m: make(map[T]struct{}),
	}
}

func (s Set[T]) Add(data T) {
	s.m[data] = struct{}{}
}

func (s Set[T]) Remove(data T) {
	delete(s.m, data)
}

func (s Set[T]) Contains(data T) bool {
	_, ok := s.m[data]
	return ok
}