I needed a set datastructure for a Go program, after a quick search on the interweb I saw this reddit thread about sets, queues, etc…

Short answer: for sets use maps, specifically map[<element>]struct{}. My first intuition was to use map[<element>]interface{}, but it turns out that an empty interface takes 8 bytes: 4 bytes for the type, and 4 bytes for the value which is always nil, while an empty structure doesn’t use any space.

There weren’t many details on how to do to it. So I just gave it a try, it was pretty easy to figure out the implementation, as long as operations like union, intersection arent’ needed.

That’s how I would implement an integer set:

type set map[int]struct{}

var myset = make(set)  // Allocate the map

// Add an element to the set by adding an empty structure for the key 1
myset[1] = struct{}{}

// Check if we have 1 in our set
if _, ok := myset[1]; ok {
    println("1 in myset")
} else {
    println("1 not in myset")
}

// Remove the element from the set
delete(myset, 1)