Containers in the Go Standard Library

In this blog post, we will explore the various collection types available in the Go standard library.

Collections or containers are data structures that can hold multiple values. They are used to group related data together and provide various operations to manipulate that data.

Go provides collections as built-in types and in the standard library. First, we'll take a quick look at the built-in types, and then we'll explore the collections provided in the standard library.

Built-in Collections ¶

Go provides three primary built-in collection types: arrays, slices, and maps. These types are deeply integrated into the language and are optimized for performance.

• Arrays: Fixed-size collections of elements of the same type. The size of an array is part of its type, which means that [3]int and [4]int are different types. Arrays are value types, so when you assign an array to a new variable or pass it to a function, a copy of the array is made.

  var arr = [3]int{1, 2, 3}
  fmt.Println(arr) // Output: [1 2 3]

• Slices: Dynamic, flexible views into arrays. Slices are reference types and consist of a pointer to an underlying array, a length, and a capacity. They can grow as needed using the built-in append function.

  slice := []int{1, 2, 3}
  slice = append(slice, 4, 5)
  fmt.Println(slice) // Output: [1 2 3 4 5]

• Maps: Unordered collections of key-value pairs. Maps are reference types and must be initialized using the make function or a map literal before use. The keys in a map must be of a type that is comparable (e.g., strings, integers).

  m := map[string]int{"one": 1, "two": 2}
  m["three"] = 3
  fmt.Println(m) // Output: map[one:1 three:3 two:2]

You can use these types as a base for implementing your own collections. A common use case is to use a map as a set by using the keys of the map to represent the items in the set. A common pattern is to use an empty struct (struct{}) as the value type, since it occupies zero bytes of storage.

  set := make(map[string]struct{})
  set["item1"] = struct{}{}
  set["item2"] = struct{}{}

  if _, exists := set["item1"]; exists {
    fmt.Println("item1 is in the set")
  }

A bag or multiset can be implemented by using a map where the keys are the items and the values are the counts of each item.

  bag := make(map[string]int)
  bag["apples"]++
  bag["pears"]++
  bag["apples"]++
  fmt.Println(bag) // Output: map[apples:2 pears:1]

Containers in the Standard Library ¶

In this section, we will explore the container implementations provided by the Go standard library.

container/list ¶

The container/list package provides an implementation of a doubly linked list. Each element in the list contains a value and pointers to both the next and previous elements. This allows for efficient insertions and deletions from both ends of the list and from the middle, given a pointer to the element.

Here is a simple example of how to use container/list:

package main

import (
  "container/list"
  "fmt"
)

func main() {
  l := list.New()

  // Add at the front
  l.PushFront(3)

  // Add at the back
  l.PushBack(4)

  // Add in the middle
  secondElement := l.Front().Next() // 4
  l.InsertAfter(5, secondElement)

  // Move an element to the front
  l.MoveToFront(secondElement)

  for e := l.Front(); e != nil; e = e.Next() {
    fmt.Println(e.Value)
  }
  // Output: 4 3 5
}

While a doubly linked list performs well when you need to frequently insert and delete elements from the middle or ends of the list, it is not a good choice when you need to frequently access elements by index. Accessing an element by index requires traversing the list from the front or back.

Real-world use cases for a doubly linked list include implementing a Least Recently Used (LRU) cache, where you need to quickly move elements to the front of the list when they are accessed and remove the least recently used elements from the back of the list. Another use case is in certain graph algorithms that require frequent insertions and deletions of nodes.

container/ring ¶

The container/ring package provides an implementation of a circular linked list, or ring. In a ring, the last element points back to the first, creating a continuous loop. This structure is useful for scenarios where you need to cycle through a fixed-size collection of elements.

Here is a simple example of how to use container/ring:

package main

import (
  "container/ring"
  "fmt"
)

func main() {
  // Create a new ring with 5 elements.
  r := ring.New(5)

  // Populate the ring with values.
  for i := 0; i < r.Len(); i++ {
    r.Value = i + 1
    r = r.Next()
  }

  // Print all elements in the ring.
  r.Do(func(value any) {
    fmt.Println(value)
  })
  // Output 1 2 3 4 5

  // Move forward and backward.
  fmt.Printf("Current: %v\n", r.Value) // Current: 1
  fmt.Printf("Next: %v\n", r.Next().Value) // Next: 2
  fmt.Printf("Previous: %v\n", r.Prev().Value) // Previous: 5

  // Add a new ring to the existing one.
  newRing := ring.New(2)
  newRing.Value = 100
  newRing.Next().Value = 200
  r.Link(newRing)
  
  r.Do(func(value any) {
    fmt.Println(value)
  })
  // Output: 1 100 200 2 3 4 5

  // Unlink elements.
  unlinked := r.Unlink(2)
  r.Do(func(value any) {
    fmt.Println(value)
  })
  // Output: 1 2 3 4 5
  
  unlinked.Do(func(value any) {
    fmt.Println(value)
  })
  // Output: 100 200
}

What's special about container/ring is that a reference to the entire ring also serves as a reference to any element in the ring. There is no designated start or end, so you can start iterating from any element.

Here is an example of using container/ring to implement a simple round-robin scheduler that cycles through a list of players, giving each player a turn in a game:

package main

import (
  "container/ring"
  "fmt"
)

func main() {
  players := []string{"Alice", "Bob", "Charlie", "Diana"}
  playerRing := ring.New(len(players))

  for _, player := range players {
    playerRing.Value = player
    playerRing = playerRing.Next()
  }

  totalTurns := 10
  for i := 0; i < totalTurns; i++ {
    fmt.Printf("Turn %d: %s\n", i+1, playerRing.Value)
    playerRing = playerRing.Next()
  }
}

Real-world use cases for container/ring include implementing fixed-size circular buffers, where new data overwrites the oldest data once the buffer is full. This is useful in scenarios like logging, where you want to maintain a history of recent events without continuously allocating more memory. A ring can also be used in task scheduling, where tasks are processed in a round-robin fashion, ensuring that each task gets a fair share of processing time. Other use cases include games or simulations that require cyclic turns or repeating patterns, and event handling systems that need to rotate through a sequence of handlers or listeners in a loop.

container/heap ¶

The container/heap package is a bit different from the other container packages because it does not provide a concrete data structure. Instead, it provides heap operations that can be applied to any type that implements the heap.Interface. This means you have to write your own type and implement the required methods to use it as a heap. The interface requires methods for getting the length (Len) of the collection, comparing elements (Less), swapping elements (Swap), and adding/removing elements (Push and Pop).

Here is a simple example of how to use container/heap to implement a max-int-heap. A max-int-heap sorts the elements from largest to smallest, so the largest element is always at the root of the heap.

package main

import (
  "container/heap"
  "fmt"
)

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x any) {
  *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() any {
  old := *h
  n := len(old)
  removedElement := old[n-1]
  *h = old[0 : n-1]
  return removedElement
}

func main() {
  h := &IntHeap{2, 1, 5}
  heap.Init(h)
  heap.Push(h, 3)
  for h.Len() > 0 {
    fmt.Printf("%d ", heap.Pop(h))
  }
  // Output: 5 3 2 1
}

After instantiating the heap, you need to call heap.Init to set up the heap invariants. The heap.Push and heap.Pop functions are used to add and remove elements, while the heap calls the user-defined methods to maintain the heap property. In this example, whenever the code calls heap.Pop, it will always remove and return the largest element because of the way the Less method is implemented.

Using a slice as the underlying data structure is a common choice because it provides dynamic resizing and efficient access.

Here is another example that does the opposite of the previous one: a min-int-heap. The elements in the heap are ordered from smallest to largest.

package main

type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x any) {
  *h = append(*h, x.(int))
}

func (h *MinHeap) Pop() any {
  old := *h
  n := len(old)
  item := old[n-1]
  *h = old[0 : n-1]
  return item
}

We can now take this heap implementation to implement a function that finds the k-th largest element in a slice of integers. While pushing every element onto the heap, the algorithm checks if the heap size exceeds k. If it does, it calls heap.Pop to remove the minimum element (based on the Less method), which is the smallest element in this min-heap implementation. After processing all elements, the top of the heap will be the k-th largest element in the original slice.

func FindKthLargest(nums []int, k int) (int, error) {
  if k <= 0 || k > len(nums) {
    return 0, fmt.Errorf("k must be between 1 and the length of the slice")
  }

  h := &MinHeap{}
  heap.Init(h)

  for _, num := range nums {
    heap.Push(h, num)
    if h.Len() > k {
      heap.Pop(h)
    }
  }
  return (*h)[0], nil
}

func main() {
  numbers := []int{3, 2, 3, 1, 2, 4, 5, 5, 6}
  k2 := 4

  kthLargest2, err := FindKthLargest(numbers, k2)
  if err != nil {
    fmt.Println("Error:", err)
    return
  }

  fmt.Printf("The %d-th largest element is: %d\n", k2, kthLargest2) // Output: The 4-th largest element is: 4
}

Real-world use cases for heaps include implementing priority queues, where elements are processed based on their priority rather than their insertion order. Heaps are also used in various algorithms, such as Dijkstra's shortest path algorithm and the A* search algorithm.

sync.Map ¶

The sync.Map type is a concurrent-safe map designed for use in multi-goroutine environments. Unlike the built-in map, which requires explicit synchronization (e.g., using sync.Mutex or sync.RWMutex) to be safely accessed by multiple goroutines, sync.Map handles synchronization internally.

Here is a simple example of how to use sync.Map:

package main

import (
  "fmt"
  "sync"
)

func main() {
  var m sync.Map
  var wg sync.WaitGroup

  for i := range 5 {
    wg.Go(func() {
      m.Store(fmt.Sprintf("key%d", i), i)
    })
  }
  wg.Wait()

  for i := range 5 {
    if value, ok := m.Load(fmt.Sprintf("key%d", i)); ok {
      fmt.Printf("key%d: %d\n", i, value)
    }
  }
  // Output: 
  // key0: 0
  // key1: 1
  // key2: 2
  // key3: 3
  // key4: 4
}

According to the documentation, sync.Map is optimized for two common use cases: (1) when the entry for a given key is only ever written once but read many times, as in caches that only grow, or (2) when multiple goroutines read, write, and overwrite entries for disjoint sets of keys. In these two cases, use of a sync.Map may significantly reduce lock contention compared to a Go map paired with a separate Mutex or RWMutex.

Do not use sync.Map in a single-threaded context, because the lock overhead will make it significantly slower than the built-in map.

Conclusion ¶

This concludes our tour of the various collection types available in Go. Go does not have a large number of collection types, but you can build most data structures on top of the built-in types. The collections provided in the standard library are specialized tools for specific problems, and you should only use them when you have a specific need that cannot be easily solved with arrays, slices, or maps.

Before implementing your own data structure, check the Internet for third-party libraries that might already have what you need. The awesome-go list is a good place to start looking.