Welcome to our Simulating Sets in Go lesson! In Go, there's no built-in type specifically called a "set." However, the concept of a set — a collection that stores unique elements — can be emulated using other data structures provided by the language, such as maps. Sets are incredibly useful when you need to ensure that elements in a collection are unique. In this lesson, you'll explore how to create and manage set-like collections in Go by implementing a Set custom struct.

In Go, we can simulate a set by leveraging maps. A map's keys naturally represent unique elements due to their uniqueness within the context of the map. Below, we'll demonstrate how to create and manipulate a set-like structure using a custom Set struct.

Go
Copy to clipboard
1package main
2
3import "fmt"
4
5// Set is a custom struct to simulate a set using a map.
6type Set struct {
7    elements map[int]struct{}
8}
9
10// NewSet initializes and returns a new set.
11func NewSet() *Set {
12    return &Set{elements: make(map[int]struct{})}
13}
14
15func main() {
16    mySet := NewSet()
17    elements := []int{1, 2, 3, 4, 5, 5, 5}
18
19    for _, elem := range elements {
20        mySet.Add(elem) // Add element to the set, ensuring uniqueness.
21    }
22
23    // Print each unique element in the set.
24    for key := range mySet.elements {
25        fmt.Println(key) // Output: 1 2 3 4 5
26    }
27}

In this example, the Set struct encapsulates the map, ensuring element uniqueness. The choice of using struct{} as the map's value type is intentional—it occupies no memory (0 bytes), unlike other types such as bool. This design decision leverages memory efficiency.

To simulate basic set operations, we define receiver functions (methods) for the Set struct:

• Inserting an Element: The Add() method updates the map with the key being the element and value as an empty struct, ensuring the element's existence in the set.
• Deleting an Element: The Remove() method removes the element by deleting its key from the map.
• Checking for Membership: The Has() method checks for the presence of a key in the map, hence confirming an element's membership in the set.

Go
Copy to clipboard
1func (s *Set) Add(v int) {
2    s.elements[v] = struct{}{}
3}
4
5func (s *Set) Has(v int) bool {
6    _, exists := s.elements[v]
7    return exists
8}
9
10func (s *Set) Remove(v int) {
11    delete(s.elements, v)
12}
13
14func main() {
15    mySet := NewSet()
16    mySet.Add(1)
17    mySet.Add(2)
18    mySet.Add(3)
19
20    if mySet.Has(1) {
21        fmt.Println("Element 1 exists")
22    }
23
24    mySet.Remove(1)
25
26    if !mySet.Has(1) {
27        fmt.Println("Element 1 no longer exists")
28    }
29}

We can simulate common set operations such as union, intersection, and difference by implementing additional methods for the Set struct.

The union of two sets involves combining the elements of both sets into a new set.

Go
Copy to clipboard
1func (s *Set) Union(s2 *Set) *Set {
2    result := NewSet()
3    for v := range s.elements {
4        result.Add(v)
5    }
6    for v := range s2.elements {
7        result.Add(v)
8    }
9    return result
10}

In the Union method, we iterate over the elements of both sets and add them to a new Set. This ensures that all unique elements from both sets are collected into the result, providing a union of the two sets.

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

Go
Copy to clipboard
1func (s *Set) Intersect(s2 *Set) *Set {
2    result := NewSet()
3    for v := range s.elements {
4        if s2.Has(v) {
5            result.Add(v)
6        }
7    }
8    return result
9}

The Intersect method works by iterating over the elements of the first set and checking if each element is present in the second set. If an element exists in both, it is added to the result set, yielding the intersection.

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

Go
Copy to clipboard
1func (s *Set) Difference(s2 *Set) *Set {
2    result := NewSet()
3    for v := range s.elements {
4        if !s2.Has(v) {
5            result.Add(v)
6        }
7    }
8    return result
9}

For the Difference method, we check each element from the first set to see if it does not exist in the second set. Those elements which are exclusive to the first set are added to the result, forming the difference.

Although Go doesn't have an explicit mechanism for immutability, we can use techniques such as returning read-only views of the set or encapsulating the set in a function that only provides read access.

Go
Copy to clipboard
1type ImmutableSet struct {
2    elements map[int]struct{}
3}
4
5func NewImmutableSet(elements []int) *ImmutableSet {
6    set := make(map[int]struct{})
7    for _, e := range elements {
8        set[e] = struct{}{}
9    }
10    return &ImmutableSet{elements: set}
11}
12
13func (s *ImmutableSet) Contains(e int) bool {
14    _, exists := s.elements[e]
15    return exists
16}
17
18// Usage
19func main() {
20    mySet := NewImmutableSet([]int{1, 2, 3, 4, 5})
21    fmt.Println(mySet.Contains(3)) // Output: true
22}

In the immutable set implementation, we construct a ImmutableSet struct that encapsulates a map, similar to the mutable set. However, the operations provided only allow read access, such as checking if an element is contained in the set through the Contains method. This design encapsulates the data and does not allow modifications, providing a layer of immutability by restricting operations.

Creating set-like structures using maps offers efficient membership tests. Maps in Go provide constant time complexity on average (O(1)) for membership checks compared to slices, which require a linear search (O(n)). Let's benchmark the execution time for both data structures using Go's testing module:

Go
Copy to clipboard
1import (
2    "testing"
3)
4
5// Benchmark functions
6func BenchmarkSetHas(b *testing.B) {
7    mySet := NewSet()
8    for i := 0; i < 1000000; i++ {
9        mySet.Add(i)
10    }
11    
12    b.ResetTimer() // Reset the timer to exclude setup time
13    for i := 0; i < b.N; i++ {
14        mySet.Has(999999)
15    }
16}
17
18func BenchmarkSliceContains(b *testing.B) {
19    mySlice := []int{}
20    for i := 0; i < 1000000; i++ {
21        mySlice = append(mySlice, i)
22    }
23
24    b.ResetTimer() // Reset the timer to exclude setup time
25    for i := 0; i < b.N; i++ {
26        containsSlice := false
27        for _, val := range mySlice {
28            if val == 999999 {
29                containsSlice = true
30                break
31            }
32        }
33        _ = containsSlice // Avoid compiler optimizations
34    }
35}
36

Running the above benchmark with go test -bench . produces a result similar to the following, highlighting the huge difference in terms of efficiency (ns/op represents the time taken in nanoseconds for that operation):

Plain text
Copy to clipboard
1BenchmarkSetHas-32              11474556               166.0 ns/op
2BenchmarkSliceContains-32            100               16011476 ns/op

Congratulations! You've learned how to create and manipulate set-like structures in Go by implementing a custom Set struct, perform set operations, and understand the performance benefits. Practice these concepts to reinforce your understanding. Happy coding!