Sets in Go

Go doesn’t offer a native set type, and the standard library doesn’t provide one either. So, how do you create sets in Go?

You use a map.

First, we’ll explore how maps can be used to implement sets.

However, if your program relies heavily on sets, maps can quickly become tedious. That’s why, in the second part, we’ll introduce an open-source package that offers two convenient set implementations.

Finally, since these solutions only work with comparable types, we’ll wrap up by exploring how to handle non-comparable types in sets.

Let’s dive in!

Sets using maps

Maps in Go consist of key-value pairs. Both the key and value have specific types.

For example, in map x:

var x map[string]bool

All keys are of type string and all values are of type bool.

Every key is unique, a map cannot contain duplicate keys. This means the keys in a map effectively form a set.

So, x already provides us with a set of strings since its keys are of type string.

Empty struct as values

In map x, we’re also storing a bool value for each element in the map.

Since we only care about the keys in a set, we can use the empty struct struct{} instead.

The empty struct takes up no memory and clearly communicates to other developers that the values are placeholders without meaning.

Our set of strings would look like this:

var set map[string]struct{}

While it may seem a bit verbose, it’s both efficient and functional.

Let’s see it in action and go over some common use-cases.

Initializing a set

It can be useful to create a set with some initial elements.

To do this, initialize the map with keys and provide empty structs as values.

For example, the code below initializes a set with the "foo" and "bar" elements.

package main

import "fmt"

func main() {
	set := map[string]struct{}{
		"foo": {},
		"bar": {},
	}

	fmt.Println(set)
}

Note the {}, these are the empty struct values.

Adding elements to set

Elements can be added to a set by setting the appropriate key to an empty struct.

For example, below we add the "foo" element to a set.

package main

import "fmt"

func main() {
	set := make(map[string]struct{})

	set["foo"] = struct{}{}

	fmt.Println(set)
}

Note the struct{}{}, this is the empty struct value.

Removing elements of set

Remove elements from the set using the built-in delete function.

For example, below we remove "bar" element from the set.

package main

import "fmt"

func main() {
	set := map[string]struct{}{
		"foo": {},
		"bar": {},
	}

	delete(set, "bar")

	fmt.Println(set)
}

Checking for existing element

To check if an element is present in the set, we can use an index expression that returns two values:

_, ok := set[key]

The ok variable will be true if the key exists in the set and false if it doesn’t.

package main

import "fmt"

func main() {
	set := map[string]struct{}{
		"foo": {},
		"bar": {},
	}

	_, ok := set["foo"]
	fmt.Printf("is foo in the set? %v\n", ok)

	val, ok := set["baz"]
	fmt.Printf("is baz in the set? %v\n", ok)
	fmt.Printf("is baz empty struct? %v\n", val == struct{}{})
}

The blank identifier _ is used to discard the first value, as we are only interested in whether the element exists.

As you can see in the example above, the first value will always be equal to the empty struct, even if ok is false.

This is because index expressions on maps returns the zero value for non-existing keys. The zero value for the empty struct type, is an empty struct.

Using sets in comparisons

Using the empty struct as a value for your map has one downside: You will always require a variable when checking if an element exists in the set.

This will lead to more verbose code when doing a lot of comparisons.

If you’re concerned about readability and memory use is not an issue, you might still want to use a bool as a value.

See the below example that compares the two approaches.

package main

import "fmt"

func main() {
	// elaborate comparison using the empty struct
	set1 := map[string]struct{}{
		"foo": {},
		"bar": {},
	}

	_, okFoo := set1["foo"]
	_, okBar := set1["bar"]
	_, okBaz := set1["baz"]

	if okFoo && okBar && !okBaz {
		fmt.Println("empty struct")
	}

	// the same logic using bool as value
	set2 := map[string]bool{
		"foo": true,
		"bar": true,
	}

	if set2["foo"] && set2["bar"] && !set2["baz"] {
		fmt.Println("bool")
	}
}

The second comparison works because the zero value for bool values is false. So even if "baz" is not part of set2, accessing it will result in a false value being returned.

It’s a bit of an indirection, but it can lead to more concise code.

(Thanks to /u/Responsible-Hold8587 on Reddit for this suggestion)

Size of set (cardinality)

Use the len built-in function to get the length of the map and the size of the set.

package main

import "fmt"

func main() {
	set := map[string]struct{}{
		"foo": {},
		"bar": {},
	}

	size := len(set)

	fmt.Println(size)
}

Listing elements in a set

Use a for statement with a range clause to list the elements in a set.

package main

import "fmt"

func main() {
	set := map[string]struct{}{
		"foo": {},
		"bar": {},
		"baz": {},
	}

	for el := range set {
		fmt.Println(el)
	}
}

Concurrency

It’s important to know that maps in Go (and sets implemented using them) are not safe for concurrent use.

If you want to use your map across multiple goroutines, you will need to use a mutex or channels to coordinate access.

Prefer not implementing this yourself? Consider using the package we’ll explore next.

More functionality

So far we have seen the fundamentals of a set type. You can usually implement more advanced functionality by building on top of these fundamentals.

Things like:

• Difference between two sets.
• Intersection of two sets.
• Checking for subsets/supersets.

These operations can be implemented with just a few loops.

However, this can become repetitive, and you might consider building a generic set type.

Before you do that, I would suggest you look at deckarep/golang-set.

This is an open source package that provides generic sets, implementing a lot of the typical set functionality.

The implementations use a map behind the scenes.

For example, below we find the intersection of two sets:

package main

import (
	"fmt"

	mapset "github.com/deckarep/golang-set/v2"
)

func main() {
	water := mapset.NewSet[string]()
	water.Add("🐟")
	water.Add("🐠")
	water.Add("🐊")

	land := mapset.NewSet[string]()
	land.Add("🐈")
	land.Add("🐊")

	both := water.Intersect(land)

	fmt.Println(both)
}

JSON Conversion

The set types provided by deckarep/golang-set implement the marshaling interfaces from the encoding/json package.

This means that they can be encoded and decoded to JSON arrays by using the standard library functions.

Very useful if you’re building a typical web application or API.

package main

import (
	"fmt"

	"encoding/json"
	"log"

	mapset "github.com/deckarep/golang-set/v2"
)

func main() {
	set := mapset.NewSet[string]()
	set.Add("foo")
	set.Add("bar")
	set.Add("baz")

	result, err := json.Marshal(set)
	if err != nil {
		log.Fatalf("unexpected error: %v", err)
	}

	fmt.Printf("to JSON: %s\n", result)
}

Concurrency

The sets returned by NewSet* are all safe for concurrent use, these sets use a read-write mutex to coordinate access.

If for some reason the overhead of this mutex is too much and the set is only used sequentially, you can take a look at the NewThreadUnsafe* constructors.

These return a set that’s unsafe for concurrent use and don’t use a mutex.

Note on performance

The Iter and Iterator methods on the set return a channel that is fed from a separate goroutine.

While the iteration is going on, no writes can take place.

If you run a ton of iterations, this will also have an impact on performance as each new iterator will spawn a new goroutine. Keep this in mind.

Non-comparable types

To build a set you need a way to compare values for equality. Without such comparisons, you won’t be able to guarantee the uniqueness of elements and you can’t create a set.

Some types can’t be compared conventionally using == and won’t work as set elements.

The Go language limits comparisons of some types: Functions, maps and slices can only be compared to nil for example.

In other cases the semantics of your type’s equality might be different from what the Go == operator uses.

An example from the standard library is the time.Time type, which has a custom Equals method. The == operator works, but it doesn’t compare for the same instant in time.

If we were to use the time.Time type as set element, the results might be very different from what we intended.

Storing such types requires choosing a key that is a comparable type. You will then need to be able to convert or trace this key back to your non-comparable type.

For example, in case of our time.Time type, we could consider using an UTC formatted string or UNIX timestamp and converting it back to time.Time types when needed.

Summary

A short recap:

• Go doesn’t have a native set data type, but you can implement them using maps.
• Use the empty struct as a value to save memory.
• Keep concurrency in mind when using maps.
• deckarep/golang-set offers a more comprehensive set implementation with features like differences, intersections and JSON marshaling.
• Consider how types are compared when using them as set elements.

That’s it for this article, I hope you learned something :)

Consider subscribing to my newsletter if you liked this, there’s more to come.