Idiomatic Go Set

@ Go

Introduction

Notes on implementing the Set data structure while recently migrating from JavaScript to Go. The previous code used JavaScript Set🔗 to enforce unique items, but Go doesn’t have a built-in Set; we can implement it by adapting maps.

Set Definition

A data structure where elements are unique, used to represent a collection of non-duplicate values
  • Elements are unique
  • Typically allows fast membership checks (e.g.,: set.has('foobar'), O(1))
  • Typically does not emphasize order or indexing

Implementing a Set with Maps

The simplest way to deduplicate data is to put everything into a map; repeated inserts are harmless:

s := map[int]bool{5: true, 2: true}
_, ok := s[6] // Check is exist
s[8] = true   // Add
delete(s, 2)  // Delete

Using an empty struct that occupies no space

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

The reason is struct occupies no memory, while bool still requires 1 byte. When a Set stores many elements, using struct can save memory effectively.

Generic version

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


func NewSet[T comparable]() *Set[T] {
    return &Set[T]{m: make(map[T]struct{})}
}


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


func (s *Set[T]) Has(v T) bool {
    _, ok := s.m[v]
    return ok
}


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


func (s *Set[T]) Len() int {
    return len(s.m)
}

Further reading