A set is a collection of distinct elements that allows you to easily check for membership, add elements, and remove them without worrying about duplicates. While Go doesn’t have a built-in set type like Python or other languages, we can implement one using Go’s map type.

What is a set?

A set is a data structure that:

• Stores unique elements.
• Allows quick membership checks (i.e., whether an element exists in the set).
• Typically supports operations like union, intersection, difference, and adding/removing elements.

Implementing a set in Go

In Go, the closest thing to a set is a map with keys of the type you want in your set, and the values are just placeholders (often struct{} since it takes no memory).

Here’s how you can implement a simple set:

package main

import "fmt"

// Set is a collection of unique elements
type Set struct {
    elements map[string]struct{}
}

// NewSet creates a new set
func NewSet() *Set {
    return &Set{
        elements: make(map[string]struct{}),
    }
}

// Add inserts an element into the set
func (s *Set) Add(value string) {
    s.elements[value] = struct{}{}
}

// Remove deletes an element from the set
func (s *Set) Remove(value string) {
    delete(s.elements, value)
}

// Contains checks if an element is in the set
func (s *Set) Contains(value string) bool {
    _, found := s.elements[value]
    return found
}

// Size returns the number of elements in the set
func (s *Set) Size() int {
    return len(s.elements)
}

// List returns all elements in the set as a slice
func (s *Set) List() []string {
    keys := make([]string, 0, len(s.elements))
    for key := range s.elements {
        keys = append(keys, key)
    }
    return keys
}

// Example usage of the Set
func main() {
    set := NewSet()

    // Add elements to the set
    set.Add("apple")
    set.Add("banana")
    set.Add("orange")

    // Check if elements exist in the set
    fmt.Println("Contains 'apple':", set.Contains("apple"))  // true
    fmt.Println("Contains 'grape':", set.Contains("grape"))  // false

    // List elements
    fmt.Println("Set elements:", set.List())  // ["apple", "banana", "orange"]

    // Remove an element
    set.Remove("banana")
    fmt.Println("Set after removal:", set.List())  // ["apple", "orange"]

    // Get the size of the set
    fmt.Println("Set size:", set.Size())  // 2
}

Let’s walk through it:

• Set Struct: The set is implemented as a struct containing a map[string]struct{}. The keys of the map represent the elements of the set, and the value is an empty struct (struct{}) because it takes up no memory and we don’t need to store additional data.
• Add Method: The Add method adds an element to the set by setting a key in the map. Since maps don’t allow duplicate keys, this ensures that the set only contains unique elements.
• Remove Method: The Remove method deletes an element from the set by removing the key from the map.
• Contains Method: The Contains method checks whether an element is in the set by looking up the key in the map.
• Size and List Methods: The Size method returns the number of unique elements, and the List method returns all the elements in the set as a slice.

Common Set Operations

Union

The union of two sets is a set containing all elements from both sets.

func (s *Set) Union(other *Set) *Set {
    result := NewSet()
    for key := range s.elements {
        result.Add(key)
    }
    for key := range other.elements {
        result.Add(key)
    }
    return result
}

// Example usage of Union
set1 := NewSet()
set1.Add("apple")
set1.Add("banana")

set2 := NewSet()
set2.Add("banana")
set2.Add("orange")

unionSet := set1.Union(set2)
fmt.Println("Union:", unionSet.List())  // ["apple", "banana", "orange"]

Intersection

The intersection of two sets is a set containing only the elements present in both sets.

func (s *Set) Intersection(other *Set) *Set {
    result := NewSet()
    for key := range s.elements {
        if other.Contains(key) {
            result.Add(key)
        }
    }
    return result
}

// Example usage of Intersection
intersectionSet := set1.Intersection(set2)
fmt.Println("Intersection:", intersectionSet.List())  // ["banana"]

Difference

The difference of two sets is a set containing elements that are in the first set but not in the second.

func (s *Set) Difference(other *Set) *Set {
    result := NewSet()
    for key := range s.elements {
        if !other.Contains(key) {
            result.Add(key)
        }
    }
    return result
}

// Example usage of Difference
differenceSet := set1.Difference(set2)
fmt.Println("Difference:", differenceSet.List())  // ["apple"]

Performance

The time complexity for most operations (insertion, deletion, membership check) on the set is O(1), as they are backed by a map. This means they are a great choice if they match your use case!

Wrapping up

Hope you found this useful! You may also enjoy our other blogs here with plenty more Go tips!