go-set

The go-set repository provides a set package containing a few generic Set implementations for Go.

---

PSA October 2023 - The v2 version of this package has been published, starting at tag version v2.1.0. A description of the changes including backwards incompatibilities can be found in #73

---

Each implementation is optimal for a particular use case.

Set[T] is ideal for comparable types.

• backed by map builtin
• commonly used with string, int, simple struct types, etc.

HashSet[T] is useful for types that implement a Hash() function.

• backed by map builtin
• commonly used with complex structs
• also works with custom HashFunc[T] implementations

TreeSet[T] is useful for comparable data (via CompareFunc[T])

• backed by Red-Black Binary Search Tree
• commonly used with complex structs with extrinsic order
• efficient iteration in sort order
• additional methods Min / Max / TopK / BottomK

This package is not thread-safe.

---

Documentation

The full go-set package reference is available on pkg.go.dev.

Install

go get github.com/hashicorp/go-set/v2@latest

import "github.com/hashicorp/go-set/v2"

Motivation

Package set helps reduce the boiler plate of using a map[<type>]struct{} as a set.

Say we want to de-duplicate a slice of strings

items := []string{"mitchell", "armon", "jack", "dave", "armon", "dave"}

A typical example of the classic way using map built-in:

m := make(map[string]struct{})
for _, item := range items {
  m[item] = struct{}{}
}
list := make([]string, 0, len(items))
for k := range m {
  list = append(list, k)
}

The same result, but in one line using package go-set.

list := set.From[string](items).Slice()

Set

The go-set package includes Set for types that satisfy the comparable constraint. Uniqueness of a set elements is guaranteed via shallow comparison (result of == operator).

Note: if pointers or structs with pointer fields are stored in the Set, they will be compared in the sense of pointer addresses, not in the sense of referenced values. Due to this fact the Set type is recommended to be used with builtin types like string, int, or simple struct types with no pointers. Set usage with pointers or structs with pointer is also possible if shallow equality is acceptable.

HashSet

The go-set package includes HashSet for types that implement a Hash() function. The custom type must satisfy HashFunc[H Hash] - essentially any Hash() function that returns a string or integer. This enables types to use string-y hash functions like md5, sha1, or even GoString(), but also enables types to implement an efficient hash function using a hash code based on prime multiples.

TreeSet

The go-set package includes TreeSet for creating sorted sets. A TreeSet may be used with any type T as the comparison between elements is provided by implementing CompareFunc[T]. The Compare[GoType] helper provides a convenient implementation of CompareFunc for builtin types like string or int. A TreeSet is backed by an underlying balanced binary search tree, making operations like in-order traversal efficient, in addition to enabling functions like Min(), Max(), TopK(), and BottomK().

Collection[T]

The Collection[T] interface is implemented by each of Set, HashSet, and TreeSet.

It serves as a useful abstraction over the common methods implemented by each set type.

Iteration

Go still has no support for using range over user defined types. Until that becomes possible, each of Set, HashSet, and TreeSet implements a ForEach method for iterating each element in a set. The argument is a function that accepts an item from the set and returns a boolean, indicating whether iteration should be halted.

// e.g. print each item in the set
s.ForEach(func(item T) bool {
  fmt.Println(item)
  return true
})

Set Examples

Below are simple example usages of Set

s := set.New[int](10)
s.Insert(1)
s.InsertSlice([]int{2, 3, 4})
s.Size()

s := set.From[string]([]string{"one", "two", "three"})
s.Contains("three")
s.Remove("one")

a := set.From[int]([]int{2, 4, 6, 8})
b := set.From[int]([]int{4, 5, 6})
a.Intersect(b)

HashSet Examples

Below are simple example usages of HashSet

(using a hash code)

type inventory struct {
    item   int
    serial int
}

func (i *inventory) Hash() int {
    code := 3 * item * 5 * serial
    return code
}

i1 := &inventory{item: 42, serial: 101}

s := set.NewHashSet[*inventory, int](10)
s.Insert(i1)

(using a string hash)

type employee struct {
    name string
    id   int
}

func (e *employee) Hash() string {
    return fmt.Sprintf("%s:%d", e.name, e.id)
}

e1 := &employee{name: "armon", id: 2}

s := set.NewHashSet[*employee, string](10)
s.Insert(e1)

TreeSet Examples

Below are simple example usages of TreeSet

(using the Compare helper to compare a built in GoType)

ts := NewTreeSet[int](Compare[int])
ts.Insert(5)

(using a custom CompareFunc)

type waypoint struct {
    distance int
    name     string
}

cmp := func(w1, w2 *waypoint) int {
    return w1.distance - w2.distance
}

ts := NewTreeSet[*waypoint](cmp)
ts.Insert(&waypoint{distance: 42, name: "tango"})
ts.Insert(&waypoint{distance: 13, name: "alpha"})
ts.Insert(&waypoint{distance: 71, name: "xray"})