Golang Set: map[T]struct{}, Operations and a Generic Set

The idiom: a map with empty values

Go has no set keyword and no set in the standard library. A map whose keys are the elements and whose values carry nothing does the job.

package main

import "fmt"

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

	// add
	tags["go"] = struct{}{}
	tags["backend"] = struct{}{}
	tags["go"] = struct{}{} // adding again changes nothing

	// has
	_, ok := tags["go"]
	fmt.Println("has go:", ok)

	// remove
	delete(tags, "backend")

	// size
	fmt.Println("size:", len(tags))

	for t := range tags {
		fmt.Println("member:", t)
	}
}

struct{} is the empty struct type and struct{}{} is its only value. It occupies zero bytes, so the map stores keys and nothing else.

All the map rules apply: keys must be comparable, iteration order is random, a nil map panics on write, and concurrent writes need a lock. The maps page covers each one.

map[T]struct{} or map[T]bool

The other common spelling is map[T]bool. It reads better because a missing key returns false:

seen := map[string]bool{}
seen["a"] = true
if seen["a"] { ... }

The trade-offs:

The third row is the real reason many codebases prefer the empty struct: with bool, someone eventually writes s[k] = false and len(s) stops being the number of members. For small sets the memory difference does not matter.

Removing duplicates from a slice

The most common use of a set is deduplication. This keeps the first occurrence of each value and preserves order:

package main

import (
	"fmt"
	"slices"
)

func unique[T comparable](in []T) []T {
	seen := make(map[T]struct{}, len(in))
	out := make([]T, 0, len(in))
	for _, v := range in {
		if _, ok := seen[v]; ok {
			continue
		}
		seen[v] = struct{}{}
		out = append(out, v)
	}
	return out
}

func main() {
	fmt.Println(unique([]string{"b", "a", "b", "c", "a"}))
	fmt.Println(unique([]int{3, 1, 3, 3, 2}))

	// If order does not matter: sort, then drop adjacent duplicates.
	s := []int{3, 1, 3, 3, 2}
	slices.Sort(s)
	fmt.Println(slices.Compact(s))
}

Output:

[b a c]
[3 1 2]
[1 2 3]

Union, intersection, difference

Set algebra is a few loops. Iterate the smaller set when testing membership in the other, since each lookup is constant time on average.

package main

import (
	"fmt"
	"maps"
	"slices"
)

type set map[string]struct{}

func of(items ...string) set {
	s := make(set, len(items))
	for _, it := range items {
		s[it] = struct{}{}
	}
	return s
}

func union(a, b set) set {
	out := maps.Clone(a)
	for k := range b {
		out[k] = struct{}{}
	}
	return out
}

func intersect(a, b set) set {
	if len(a) > len(b) {
		a, b = b, a
	}
	out := set{}
	for k := range a {
		if _, ok := b[k]; ok {
			out[k] = struct{}{}
		}
	}
	return out
}

func difference(a, b set) set {
	out := set{}
	for k := range a {
		if _, ok := b[k]; !ok {
			out[k] = struct{}{}
		}
	}
	return out
}

func sorted(s set) []string {
	return slices.Sorted(maps.Keys(s))
}

func main() {
	backend := of("go", "sql", "docker", "linux")
	devops := of("docker", "linux", "terraform")

	fmt.Println("union:     ", sorted(union(backend, devops)))
	fmt.Println("intersect: ", sorted(intersect(backend, devops)))
	fmt.Println("backend-only:", sorted(difference(backend, devops)))
}

sorted exists only to make the output stable. Printing a set by ranging over it gives a different order on each run. maps.Keys and slices.Sorted need Go 1.23.

A named type like type set map[string]struct{} is still a map: you index it, range it and delete from it the same way, and you can hang methods on it.

A small generic Set

With generics (Go 1.18), one type covers every comparable element type. This is enough for most programs:

package main

import (
	"cmp"
	"fmt"
	"maps"
	"slices"
)

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

func NewSet[T comparable](items ...T) *Set[T] {
	s := &Set[T]{m: make(map[T]struct{}, len(items))}
	for _, it := range items {
		s.Add(it)
	}
	return s
}

func (s *Set[T]) Add(v T)    { s.m[v] = struct{}{} }
func (s *Set[T]) Remove(v T) { delete(s.m, v) }
func (s *Set[T]) Len() int   { return len(s.m) }
func (s *Set[T]) Has(v T) bool {
	_, ok := s.m[v]
	return ok
}

func (s *Set[T]) Union(o *Set[T]) *Set[T] {
	out := &Set[T]{m: maps.Clone(s.m)}
	for v := range o.m {
		out.Add(v)
	}
	return out
}

// Sorted is a free function because it needs a stricter constraint than the type.
func Sorted[T cmp.Ordered](s *Set[T]) []T {
	return slices.Sorted(maps.Keys(s.m))
}

func main() {
	a := NewSet(1, 2, 3)
	b := NewSet(3, 4)
	a.Add(2)
	fmt.Println(a.Len(), a.Has(2), a.Has(9))

	u := a.Union(b)
	fmt.Println(Sorted(u))

	words := NewSet("go", "rust")
	words.Remove("rust")
	fmt.Println(Sorted(words))
}

Wrapping the map in a struct hides the struct{}{} noise and guarantees the map is created by the constructor, which removes the nil map panic. Sorted cannot be a method: a method cannot declare its own type parameters or tighten the type's comparable constraint, and sorting needs cmp.Ordered. The generics page explains constraints.

If you need a full-featured set (thread-safe variants, many operations), third-party packages such as github.com/deckarep/golang-set exist. For most code, the map idiom or a 30-line type like this one is what Go programmers use.

Sets of structs

Any comparable type can be an element, including structs with comparable fields. That makes "have I seen this pair" checks direct:

type edge struct{ from, to string }
visited := map[edge]struct{}{}
visited[edge{"a", "b"}] = struct{}{}

Slices and maps cannot be set elements. To track unique slices, convert each one to a comparable key first, for example an array of fixed size, or a string built with fmt.Sprint.

Common mistakes

• Forgetting to initialize. var s map[string]struct{} is nil; the first add panics.
• Printing a set and expecting stable output. Sort the members first.
• Using map[T]bool and storing false. Then len no longer counts members. Use delete to remove.