Sets in Golang

Welcome to my first blog post! I will try to explain how to implement your own Set data type in Go lang

Set is an abstract data type that can store certain values, without any particular order, and no repeated values. It is a computer implementation of the mathematical concept of a finite set.

Go does not have Sets by default but there are ways of imitating a Set in Go. I will describe the method where map[interface{}]interface{} is used as container for our data since it is the closest to sets, because it can't contain repeated keys and it does not have particular order. So lets start with declaration. You can declare a set with

var InterfaceSet map[interface{}]struct{}
var IntSet       map[int]struct{} 
var StringSet    map[string]struct{}

or

var InterfaceSet map[interface{}]bool
var IntSet       map[int]bool
var StringSet    map[string]bool

However I prefer the first variant since struct{} takes 0 bytes (you can read more about 0 bytes sized structs in Dave Cheney's post). I will use the first variant in the rest of the post.

Let's say we have created our set with

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

and now we want to fill it with data. We will add data the same way as we would to map[interface{}]interface{} . We need a string key and struct{} value. So lets create our generic value for the map

var exists = struct{}{}

and fill the "set" (map) with data:

s["James"] = exists
s["David"] = exists
s["Peter"] = exists

Now when we have filled our set with data, we would like to iterate over our values in the set:

for v := range s {
    fmt.Println(v)
}

Next operation would be testing if the set contains specified values:

if _, ok := s["Peter"]; ok {
    fmt.Println("Peter is in the set.") // This will be printed
}

if _, ok := s["George"]; ok {
    fmt.Println("George is in the set.") // This won't be printed
}

Last important operation is deleting values from our set:

delete(s, "Peter")

if _, ok := s["Peter]; ok {
    fmt.Println("Peter is in the set") // Now this won't be printed
}

However all of these basic operations (adding, deleting, checking if the set contains our value, etc.) can transformed to more user-friendly form. Lets encapsulate our map in its own struct:

type set struct {
    m map[string]struct{}
}

As you may have noticed, we didn't export the set type. The reason behind is that we want to create a function, which will initialise the map and return pointer to our struct (small set factory):

func NewSet() *set {
    s := &set{}
    s.m = make(map[string]struct{})
}

Now when we have function for creating sets, we can implement rest of the basic operations on set:

func (s *set) Add(value string) {
    s[value] = exists
}

func (s *set) Remove(value string) {
    delete(s.m, value)
}

func (s *set) Contains(value string) bool {
    _, c := s.m[value]
    return c
}

Here you can find fully working example:

package main

import "fmt"

var exists = struct{}{}

type set struct {
    m map[string]struct{}
}

func NewSet() *set {
    s := &set{}
    s.m = make(map[string]struct{})
    return s
}

func (s *set) Add(value string) {
    s.m[value] = exists
}

func (s *set) Remove(value string) {
    delete(s.m, value)
}

func (s *set) Contains(value string) bool {
    _, c := s.m[value]
    return c
}

func main() {
    s := NewSet()

    s.Add("Peter")
    s.Add("David")

    fmt.Println(s.Contains("Peter"))  // True
    fmt.Println(s.Contains("George")) // False

    s.Remove("David")
    fmt.Println(s.Contains("David")) // False
}

Set implementation packages:

fatih/set

deckarep/golang-set