Go has no built-in set type. The idiomatic stand-in is a map with an empty struct value, since struct takes no memory and the map already gives O(1) lookup.
The shape
Map with zero-size values
A map from the element to an empty struct, so the key is the whole story.
- Add: write the key with an empty struct as its value.
- Contains: read the key with the two-value form and take the ok.
- Remove: delete the key.
Add a value, add one that is already there, and remove the last. The count only moves when the membership does.
Purpose
Track which values are present, with no duplicates.
Input
Values added one at a time, of any comparable type.
Output
Whether a value is present, and how many values are held.
Constraints
- Elements have to be comparable, since they are map keys.
- Iteration order is random, so sort the elements when the order has to be stable.
- An empty
struct{}takes no space, so the set costs only its keys.
comparable restricts T to types that work as map keys. Add writes the same empty struct every time, so adding a value that's already present is a safe no-op.
type Set[T comparable] map[T]struct{}
func (s Set[T]) Add(v T) {
s[v] = struct{}{}
}The two-value map lookup v, ok := s[v] is exactly how Contains checks membership. ok is true only if the key exists, regardless of what it maps to.
func (s Set[T]) Contains(v T) bool {
_, ok := s[v]
return ok
}delete is Go's built-in for removing a map key. Deleting a key that isn't present does nothing and never panics.
func (s Set[T]) Remove(v T) {
delete(s, v)
}The whole program main.go Show
package main
import "fmt"
type Set[T comparable] map[T]struct{}
func (s Set[T]) Add(v T) { s[v] = struct{}{} }
func (s Set[T]) Contains(v T) bool {
_, ok := s[v]
return ok
}
func (s Set[T]) Remove(v T) { delete(s, v) }
func main() {
langs := Set[string]{}
langs.Add("go")
langs.Add("rust")
fmt.Println(len(langs), langs.Contains("go"))
langs.Remove("rust")
fmt.Println(len(langs), langs.Contains("rust"))
}Iteration order over a set is never guaranteed, since it's backed by a map. Ranging over the same set twice can print elements in a different order each time.
$ go run set.go
2 true
1 false