Leon Mika

In the various Go projects that I work on, there have been times when I have needed to store items in a set. Many languages have a set implementation that is usable right out of the box. Unfortunately, Go is not one of them; but a set can be created quite easily using Go’s map type. Here is the technique I use to do so.

In this example, we’ll build a type that uses a “backing map” to hold a set of strings. The set elements will actually be stored in the map as keys. This means that string will be used as the key type in this example, but given that maps in Go can accept almost any type¹, this technique will work for most other types you may need sets for.

The approach we will be using is one based on key presence, namely that an element is a member of the set if it is also a key in the map. This means that we’re only interested in the map keys; we’re not interested in what the associated value of those key are. Because of this, the value type shouldn’t matter, and one way to indicate this is to use the empty struct as the value type.

With our types decided upon, we can defined our set type as the following:

type StringSet map[string]struct{}

We can now implement the operations for our set. For the use cases I tend to encounter, I’m usually only interested in the following operations:

• Adding an element to the set,
• Testing the presence of an element within the set, and,
• Remove an element from the set.

These can be implemented as methods on our set type. For example, adding a string element to the set can be done by adding it as a key to the map, with an empty struct value:

func (s StringSet) Put(val string) {
	s[val] = struct{}{}
}

Similarly, for testing whether the set contains an element, we can simply check that the backing map has that element as a key:

func (s StringSet) Has(val string) bool {
	_, hasVal := s[val]
	return hasVal
}

Finally, to remove an element from the set, we simply delete the key from the backing map:

func (s StringSet) Remove(val string) {
	delete(s, val)
}

Adding additional operations, like iterating over the elements of the set or returning the set cardinality, is quite trivial. These have been left as an exercise to the reader.

Using bool as the value type

A slight variant of this technique that I have used a few times is to use bool as the value type. This has some nice features, like using the single-result index operator to determine set membership (so long as the map value for a key is always set to true):

func (s StringSetWithBoolValueType) Put(val string) {
	s[val] = true
}

func (s StringSetWithBoolValueType) Has(val string) bool {
	return s[val]
}

The only downside of this approach is that it does not convey the use of key presences to determine set membership as clearly as the empty struct. It may also allow the set to grow without bounds if an element is “removed” by simply setting the value to false. These can all be mitigated through the use of comments thought, so the choice of which technique to use will probably boil down to taste.

I’ve found that this technique works pretty well in most cases where I’ve needed a set. It also works well in other languages that don’t have native set implementations, like JavaScript and Lua (in fact, Lua was the language that I’ve first encountered this technique).

I’m hopeful that when generics are finally added to Go, this technique would work even better, especially when you consider that it would no longer be necessary to implement completely new types for each set you need.

This technique will not work in all circumstances, such as cases when the elements need to be preserved in a particular order; but it’s one that I find useful, and I tend to consider it first when I need to use a set.