preface

When you use Go, will you feel that the containers (sets) of Go are very small? It seems that there are only two types of containers (Map and slice). In fact, Go also comes with three container types: List, heap, and ring are still few, but it is convenient to use the library directly when you encounter a suitable scenario.

These three containers are located under the container package:

This article uses Go 1.18 Beta 1 and will cover some generics. To learn more about generics, read the Go Generics Quickstart and Go Generics In action: Implementing a Generic Slice Library

The usage, implementation, and application of each container are described below.

List – A bidirectional linked list

Bidirectional lists are used in scenarios where the heap head and tail are frequently added and deleted, and they do not require initial initialization of their capacity, which dynamically changes with usage (expanding or shrinking).

The data structure

Go’s bidirectional linked list mainly contains two data structures:

// An element of the list
type Element struct {
   next, prev *Element // Before and after Pointers
   list *List // Belongs to the linked list
   Value any / / value
}
Copy the code

/ / list
type List struct {
   root Element // Sentry element
   len  int     // Number of list elements
}
Copy the code

The addition of sentinels makes it easier and more consistent

Initialize the

Lists support lazy initialization, so it works whether you use list.new () to create an already initialized List or just use list.list {} to create an uninitialized List.

LazyInit () is called when PushFront(), PushBack(), PushFrontList(), and PushBackList() are called to check if they are initialized, and Init() is called if they are not.

package main

import (
   "container/list"
   "fmt"
)

func main(a) 
   // Initialize directly with list.new ()
   l1 := list.New()
   l1.PushFront(1)
   fmt.Println(l1.Front().Value) / / 1

   // Use list.list {} to delay initialization
   l2 := list.List{}
   l2.PushFront(2)
   fmt.Println(l2.Front().Value) / / 2
}
Copy the code

PushFront(), PushBack(), PushFrontList(), PushBackList()

PushFront() and PushBack() add elements to the head or tail of the list, respectively. PushFrontList() and PushBackList() insert elements to the head or tail of the list, respectively

package main

import (
   "container/list"
   "fmt"
)

func main(a) {
   // Create three lists with only one node
   l1 := list.New()
   l1.PushFront(1)
   l2 := list.New()
   l2.PushBack(2)
   l3 := list.New()
   l3.PushBack(3)

   // Link L1 and L3 to L2 respectively
   l2.PushFrontList(l1)
   l2.PushBackList(l3)

   / / print
   PrintlnList(l2)
   / / 1
   / / 2
   / / 3
}

func PrintlnList(l *list.List) {
   if l.Front() == nil {
      return
   }
   forcur := l.Front(); cur ! = l.Front().Prev(); cur = cur.Next() { fmt.Println(cur.Value) } }Copy the code

Front(), Back(), Len()

Get the header element, get the tail element, and get the length, respectively

package main

import (
   "container/list"
   "fmt"
)

func main(a) {
   // Create a new list with three nodes
   l := list.New()
   l.PushBack(1)
   l.PushBack(2)
   l.PushBack(3)
   fmt.Println(l.Front().Value) / / 1
   fmt.Println(l.Back().Value)  / / 3
   fmt.Println(l.Len())         / / 3
}
Copy the code

The InsertBefore (), InsertAfter ()

Insert before an element, insert after an element.

package main

import (
   "container/list"
   "fmt"
)

func main(a) {
   // Create a new list with three nodes
   l := list.New()
   l.PushBack(1)
   e3 := l.PushBack(3) // the node 3 is intentionally saved here
   l.PushBack(5)

   PrintlnList(l)
   / / 1
   / / 3
   / / 5

   l.InsertBefore(2, e3) // Insert 2 before e3
   l.InsertAfter(4, e3)  // Insert 4 after e3
   PrintlnList(l)
   / / 1
   / / 2
   / / 3
   / / 4
   / / 5
}

func PrintlnList(l *list.List) {
   if l.Front() == nil {
      return
   }
   forcur := l.Front(); cur ! = l.Front().Prev(); cur = cur.Next() { fmt.Println(cur.Value) } }Copy the code

MoveBefore(), MoveAfter(), MoveToFront(), MoveToBack()

Move an element to the front of an element, move it to the back of an element, move it to the head, and move it to the tail

package main

import (
   "container/list"
   "fmt"
)

func main(a) {
   // Create a new list with three nodes
   l := list.New()
   e5 := l.PushBack(5)
   e3 := l.PushBack(3)
   e1 := l.PushBack(1)

   PrintlnList(l)
   / / 5
   / / 3
   / / 1

   l.MoveAfter(e5, e3)  // Move e5 behind E3
   l.MoveBefore(e1, e3) // Move e1 before e3
   PrintlnList(l)
   / / 1
   / / 3
   / / 5

   l.MoveToFront(e5) // Move e5 to the head
   l.MoveToBack(e1)  // Move e1 to the tail
   PrintlnList(l)
   / / 5
   / / 3
   / / 1
}

func PrintlnList(l *list.List) {
   if l.Front() == nil {
      return
   }
   forcur := l.Front(); cur ! = l.Front().Prev(); cur = cur.Next() { fmt.Println(cur.Value) } }Copy the code

Remove()

Remove elements

package main

import (
   "container/list"
   "fmt"
)

func main(a) {
   // Create a new list with five nodes
   l := list.New()
   l.PushBack(1)
   l.PushBack(2)
   e3 := l.PushBack(3)
   l.PushBack(4)
   l.PushBack(5)
   PrintlnList(l)
   / / 1
   / / 2
   / / 3
   / / 4
   / / 5

   // Remove the E3 node
   l.Remove(e3)
   PrintlnList(l)
   / / 1
   / / 2
   / / 4
   / / 5
}

func PrintlnList(l *list.List) {
   if l.Front() == nil {
      return
   }
   forcur := l.Front(); cur ! = l.Front().Prev(); cur = cur.Next() { fmt.Println(cur.Value) } }Copy the code

application

deque

package deque

import "container/list"

type Deque[T any] struct {
   l *list.List
}

func New[T any](a) *Deque[T] {
   return &Deque[T]{l: list.New()}
}

// AddFirst joins the team from the head
func (d *Deque[T]) AddFirst(elem T) {
   d.l.PushFront(elem)
}

// AddLast joins the team from the back
func (d *Deque[T]) AddLast(elem T) {
   d.l.PushBack(elem)
}

// RemoveFirst is removed from the team head
func (d *Deque[T]) RemoveFirst(a) T {
   return d.l.Remove(d.l.Front()).(T)
}

// RemoveLast from the end of the queue
func (d *Deque[T]) RemoveLast(a) T {
   return d.l.Remove(d.l.Back()).(T)
}

// Len Number of queue elements
func (d *Deque[T]) Len(a) int {
   return d.l.Len()
}

// Empty Indicates whether the queue is Empty
func (d *Deque[T]) Empty(a) bool {
   return d.Len() == 0
}
Copy the code

The stack

package deque

import "container/list"

type Stack[T any] struct {
   l *list.List
}

func New[T any](a) *Stack[T] {
   return &Stack[T]{l: list.New()}
}

/ / Push into stack
func (s *Stack[T]) Push(elem T) {
   s.l.PushBack(elem)
}

/ / Pop out of the stack
func (s *Stack[T]) Pop(a) T {
   return s.l.Remove(s.l.Back()).(T)
}

// Peek top stack element
func (s *Stack[T]) Peek(a) T {
   return s.l.Back().Value.(T)
}

// Len number of stack elements
func (s *Stack[T]) Len(a) int {
   return s.l.Len()
}

// Empty Whether the stack is Empty
func (s *Stack[T]) Empty(a) bool {
   return s.Len() == 0
}
Copy the code

LRU

package lru

import "container/list"

type kv[K comparable, V any] struct {
   k K
   v V
}

type LRU[K comparable, V any] struct {
   l    *list.List
   m    map[K]*list.Element
   size int
}

func New[K comparable.V any](size int) *LRU[K.V] {
   return &LRU[K, V]{
      l:    list.New(),
      m:    make(map[K]*list.Element, size),
      size: size,
   }
}

// Put adds or updates elements
func (l *LRU[K, V]) Put(k K, v V) {
   // If k already exists, move it to the end and set the new value
   if elem, ok := l.m[k]; ok {
      l.l.MoveToBack(elem)
      keyValue := elem.Value.(kv[K, V])
      keyValue.v = v
      return
   }

   // If the maximum size is reached, remove an element first
   if l.l.Len() == l.size {
      front := l.l.Front()
      l.l.Remove(front)
      delete(l.m, front.Value.(kv[K, V]).k)
   }

   // Add elements
   elem := l.l.PushBack(kv[K, V]{
      k: k,
      v: v,
   })
   l.m[k] = elem
}

// Get gets the element
func (l *LRU[K, V]) Get(k K) (V, bool) {
   // Move to tail if there is one, then return
   if elem, ok := l.m[k]; ok {
      l.l.MoveToBack(elem)
      return elem.Value.(kv[K, V]).v, true
   }

   // There is no return null and false
   var v V
   return v, false
}
Copy the code

Heap heap –

The heap is suitable for scenarios where the data needs to be ordered and elements need to be added or removed at any time, preferably with the ability to take the largest or smallest element at a time.

Here is the unadjusted heap:

Adjusted heap: You can see that the top of the heap is the largest

The data structure

The heap under the container package is structured as an interface that defines only five methods:

Heap. Interface Interface:

type Interface interface {
   sort.Interface / / sort. Interface Interface
   Push(x any) // Add element x to Len()
   Pop() any   // Remove and return the element at Len() -1
}
Copy the code

Sort. Interface Interface

type Interface interface {
   Len() int // Number of elements
   Less(i, j int) bool / / to compare
   Swap(i, j int) / / exchange
}
Copy the code

As you can see, it inherits the sort.Interface, which is the three operations needed for sorting.

It also added Push() and Pop() operations to add an element to and remove an element from the end of the list.

The use of the five operations of the heap.Interface Interface is analyzed below in the case of the functions provided by the heap package, because the first parameter of each of the five functions provided by the heap package needs to implement the heap.Interface Interface.

Init()

Initializing the heap, which is the classic heap initialization process, is just three (or two) comparisons, moving the big one up and operating from the middle of a tree (usually the bottom is a list, but think of it as a tree).

You can see that all three operations of sort.Interface are used.

func Init(h Interface) {
   n := h.Len()
   for i := n/2 - 1; i >= 0; i-- {
      down(h, i, n)
   }
}

func down(h Interface, i0, n int) bool {
   i := i0
   for {
      j1 := 2*i + 1
      if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
         break
      }
      j := j1 // left child
      if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
         j = j2 // = 2*i + 2 // right child
      }
      if! h.Less(j, i) {break
      }
      h.Swap(i, j)
      i = j
   }
   return i > i0
}
Copy the code

Push()

Add an element to the heap. You can see that this operation adds elements to the end of the list using the Push() method of the heap.interface Interface, and then adjusts them up from the last element.

func Push(h Interface, x any) {
   h.Push(x)
   up(h, h.Len()- 1)}Copy the code

Pop()

Pull out the top of the heap element, the largest or smallest element. You can see that the top of the heap is swapped with the last element, and then readjusted from the top down. Finally, we pull out the last element of the list, the Pop() method through the heap.interface Interface.

func Pop(h Interface) any {
   n := h.Len() - 1
   h.Swap(0, n)
   down(h, 0, n)
   return h.Pop()
}
Copy the code

Remove()

Removes an element with an index. This operation is similar to Pop, except that the number it removes is in the middle.

func Remove(h Interface, i int) any {
   n := h.Len() - 1
   ifn ! = i { h.Swap(i, n)if! down(h, i, n) { up(h, i) } }return h.Pop()
}
Copy the code

Fix()

Adjust from some subscript. This operation is used when you change the value of an element in a list directly from the index.

func Fix(h Interface, i int) {
   if! down(h, i, h.Len()) { up(h, i) } }Copy the code

Use the heap package directly

Using the heap package directly is cumbersome because there are five methods to implement for the data:

package main

import (
   "container/heap"
   "fmt"
)

type IntHeap []int

func (h *IntHeap) Len(a) 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(a) any {
   elem := (*h)[len(*h)- 1]
   *h = (*h)[:len(*h)- 1]
   return elem
}

func main(a) {
   var intHeap IntHeap
   heap.Init(&intHeap)
   heap.Push(&intHeap, 5)
   heap.Push(&intHeap, 3)
   heap.Push(&intHeap, 4)
   heap.Push(&intHeap, 2)
   heap.Push(&intHeap, 1)

   fmt.Println(heap.Pop(&intHeap)) / / 1
   fmt.Println(heap.Pop(&intHeap)) / / 2
   fmt.Println(heap.Pop(&intHeap)) / / 3
   fmt.Println(heap.Pop(&intHeap)) / / 4
   fmt.Println(heap.Pop(&intHeap)) / / 5
}
Copy the code

Use generic wrapping

As long as the default underlying data structure is slice, we don’t need to write Len(), Swap(), Push(), Pop(), just know how elements compare (Less()).

You can see that we first implemented internalHeap, which implements the heap.interface () Interface. The Heap class combines internalHeap directly so that only Push() and Pop() operations are exposed.

package main

import (
   "container/heap"
   "fmt"
)

type Heap[T any] struct {
   h *internalHeap[T]
}

func New[T any](less func(e1 T, e2 T) bool) *Heap[T] {
   return &Heap[T]{h: newInternalHeap[T](less)}
}

func (h *Heap[T]) Len(a) int {
   return h.h.Len()
}

func (h *Heap[T]) Push(x T) {
   heap.Push(h.h, x)
}

func (h *Heap[T]) Pop(a) T {
   return heap.Pop(h.h).(T)
}

type internalHeap[T any] struct {
   l    []T
   less func(e1 T, e2 T) bool
}

func (h *internalHeap[T]) Len(a) int {
   return len(h.l)
}

func (h *internalHeap[T]) Less(i, j int) bool {
   return h.less(h.l[i], h.l[j])
}

func (h *internalHeap[T]) Swap(i, j int) {
   h.l[i], h.l[j] = h.l[j], h.l[i]
}

func (h *internalHeap[T]) Push(x any) {
   h.l = append(h.l, x.(T))
}

func (h *internalHeap[T]) Pop(a) any {
   elem := h.l[len(h.l)- 1]
   h.l = h.l[:len(h.l)- 1]
   return elem
}

func newInternalHeap[T any](less func(e1 T, e2 T) bool) *internalHeap[T] {
   h := &internalHeap[T]{
      less: less,
   }
   heap.Init(h)
   return h
}

func main(a) {
   // Create a heap
   h := New(func(e1 int, e2 int) bool {
      return e1 > e2
   })
   
   // Push the element
   h.Push(5)
   h.Push(6)
   h.Push(3)
   h.Push(7)
   h.Push(2)
   h.Push(4)
   h.Push(8)
   h.Push(9)
   h.Push(1)

   // Fetch the element
   fmt.Println(h.Pop()) / / 9
   fmt.Println(h.Pop()) / / 8
   fmt.Println(h.Pop()) / / 7
   fmt.Println(h.Pop()) / / 6
   fmt.Println(h.Pop()) / / 5
   fmt.Println(h.Pop()) / / 4
   fmt.Println(h.Pop()) / / 3
   fmt.Println(h.Pop()) / / 2
   fmt.Println(h.Pop()) / / 1
}
Copy the code

application

Priority queue

package priority_queue

import "github.com/jiaxwu/container/heap"

// PriorityQueue specifies the PriorityQueue
type PriorityQueue[T any] struct {
   h *heap.Heap[T]
}

func New[T any](less func(e1 T, e2 T) bool) *PriorityQueue[T] {
   return &PriorityQueue[T]{
      h: heap.New(less),
   }
}

/ / Add up
func (p *PriorityQueue[T]) Add(elem T) {
   p.h.Push(elem)
}

/ / Remove out of the team
func (p *PriorityQueue[T]) Remove(a) T {
   return p.h.Pop()
}

// Len Number of queue elements
func (p *PriorityQueue[T]) Len(a) int {
   return p.h.Len()
}

// Empty Indicates whether the queue is Empty
func (p *PriorityQueue[T]) Empty(a) bool {
   return p.Len() == 0
}
Copy the code

Strives for the Top K

For a heap of size K, such as the small top heap, if it encounters an element larger than the top of the heap, the top element is removed and then added to the heap, so that the heap ends up with the largest number of elements in K.

Circle of ring –

A Ring is an element in a circular list that has no head or tail.

An empty Ring must be nil.

A zero-valued Ring is the Ring of an element.

The data structure

You can see the structure of a node in a classic bidirectional linked list

type Ring struct {
   next, prev *Ring // Before and after Pointers
   Value      any   // Set by the user
}
Copy the code

Create a Ring

Directly to create

We can create the Ring directly, specifying only the values we need to store, and do not need to do initialization of the pointer before and after the Ring, because all Ring methods check to see if the Ring is initialized before executing and initialize it first if it is not.

package main

import (
   "container/ring"
   "fmt"
)

func main(a) {
   // Create two circles
   r1 := ring.Ring{Value: 1}
   r2 := ring.Ring{Value: 2}
   // Link two loops
   r1.Link(&r2)
   // Walk through the circle
   r1.Do(func(a any) {
      fmt.Println(a) 
   })
   / / 1
   / / 2
}
Copy the code

Use the New ()

Circles can also be created using New(), which takes the number of elements to create the circle, and the pointer before and after New() is initialized.

package main

import (
   "container/ring"
   "fmt"
)

func main(a) {
   r1 := ring.New(1) // Create a circle of elements
   r2 := ring.New(2) // Create a circle of two elements
   r1.Value = 1
   r2.Value = 2
   // Link two loops
   r1.Link(r2)
   // Walk through the circle
   r1.Do(func(a any) {
      fmt.Println(a)
   })
   / / 1
   / / 2
   //<nil>
}
Copy the code

New () the source code:

func New(n int) *Ring {
   if n <= 0 {
      return nil
   }
   r := new(Ring)
   p := r
   for i := 1; i < n; i++ {
      p.next = &Ring{prev: p}
      p = p.next
   }
   p.next = r
   r.prev = p
   return r
}
Copy the code

Link () and Unlink ()

Link(); Link(); Unlink() is a link to the NTH + 1 node after the current node, so that the middle n nodes are unlinked.

package main

import (
   "container/ring"
   "fmt"
)

func main(a) {
   r1 := ring.New(1) // Create a circle of elements
   r2 := ring.New(1) // Create a circle of elements
   r3 := ring.New(1) // Create a circle of elements
   r1.Value = 1
   r2.Value = 2
   r3.Value = 3
   r1.Link(r2) // Link two loops
   r2.Link(r3) // Link two loops
   // Walk through the circle
   r1.Do(func(a any) {
      fmt.Println(a)
   })
   / / 1
   / / 2
   / / 3

   // Unlink deletes the last node
   r1.Unlink(1)
   // Walk through the circle
   r1.Do(func(a any) {
      fmt.Println(a)
   })
   / / 1
   / / 3
}
Copy the code

Unlink() source: link with the n + 1 node after the current node.

func (r *Ring) Unlink(n int) *Ring {
   if n <= 0 {
      return nil
   }
   return r.Link(r.Move(n + 1))}Copy the code

Prev(), Next(), Move()

Move(1)==Next(), Move(-1)==Prev())

package main

import (
   "container/ring"
   "fmt"
)

func main(a) {
   r1 := ring.New(1) // Create a circle of elements
   r2 := ring.New(1) // Create a circle of elements
   r3 := ring.New(1) // Create a circle of elements
   r1.Value = 1
   r2.Value = 2
   r3.Value = 3
   r1.Link(r2) // Link two loops
   r2.Link(r3) // Link two loops
   // Walk through the circle
   r1.Do(func(a any) {
      fmt.Println(a)
   })
   / / 1
   / / 2
   / / 3

   cur := r1
   fmt.Println(cur.Value) / / 1
   cur = cur.Prev()
   fmt.Println(cur.Value) / / 3
   cur = cur.Next()
   fmt.Println(cur.Value) / / 1
   cur = cur.Move(3)
   fmt.Println(cur.Value) / / 1
   cur = cur.Move(2)
   fmt.Println(cur.Value) / / 3
}
Copy the code

Len (), Do ()

The number of circle elements and the number of operations performed by each element in the heap circle.

application

Ring Buffer

A producer-consumer structure, and if there is only one reader thread and one writer thread, and no modified control variable is shared between them, it can be demonstrated that concurrency control is not required in this case

Consistency of the Hash

Consistent hashing algorithm was proposed by MIT in 1997. It is a special hashing algorithm to solve the problem of distributed cache. When removing or adding a server, the mapping between existing service requests and the server that processes them can be changed as little as possible. Consistent Hash solves the dynamic scaling problems of simple Hash algorithms in Distributed Hash tables (DHT). (From Baidu Encyclopedia)

conclusion

The three data structures in the Go standard library are very flexible and may be relatively easy to use, but as long as they are encapsulated according to their own scenarios, together with the support of generics, as well as the usual map and slice, they are basically enough for daily development.

Here is a Github repository of generic data structures implemented above, if necessary, you can refer to: github.com/jiaxwu/cont…

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Go library containers: List, heap, ring

preface

List – A bidirectional linked list

The data structure

Initialize the

PushFront(), PushBack(), PushFrontList(), PushBackList()

Front(), Back(), Len()

The InsertBefore (), InsertAfter ()

MoveBefore(), MoveAfter(), MoveToFront(), MoveToBack()

Remove()

application

deque

The stack

LRU

Heap heap –

The data structure

Init()

Push()

Pop()

Remove()

Fix()

Use the heap package directly

Use generic wrapping

application

Priority queue

Strives for the Top K

Circle of ring –

The data structure

Create a Ring

Directly to create

Use the New ()

Link () and Unlink ()

Prev(), Next(), Move()

Len (), Do ()

application

Ring Buffer

Consistency of the Hash

conclusion

Go library containers: List, heap, ring

preface

List – A bidirectional linked list

The data structure

Initialize the

PushFront(), PushBack(), PushFrontList(), PushBackList()

Front(), Back(), Len()

The InsertBefore (), InsertAfter ()

MoveBefore(), MoveAfter(), MoveToFront(), MoveToBack()

Remove()

application

deque

The stack

LRU

Heap heap –

The data structure

Init()

Push()

Pop()

Remove()

Fix()

Use the heap package directly

Use generic wrapping

application

Priority queue

Strives for the Top K

Circle of ring –

The data structure

Create a Ring

Directly to create

Use the New ()

Link () and Unlink ()

Prev(), Next(), Move()

Len (), Do ()

application

Ring Buffer

Consistency of the Hash

conclusion

Related Posts

[CI/CD Technical Topic] “Jenkins Actual Combat Series” summarizes the installation, use and configuration process of Jenkins

Stream computing

Ant Group | Rust data memory layout