container

README

Go containers

This module contains minimal type-safe Ordered Map, Queue and Stack implementations using Go generics.

The Ordered Map supports both stable (in-place) updates and recency-based ordering, making it suitable both for highest performance (in-place), and for LRU caches (recency).

Contents

See the available types by underlying storage

Type	Slice	List	List+sync.Pool	List+int. pool	Recommended
OrderedMap	Y				Slice with size hint
Queue	Y	Y	Y	Y	Slice with size hint
Stack	Y	Y	Y	Y	Slice with size hint

CAVEAT: All of these implementations are unsafe for concurrent execution, so they need protection in concurrency situations.

Generally speaking, in terms of performance:

• Slice > list+internal pool > plain List > list+sync.Pool
• Preallocated > not preallocated

See BENCHARKS.md for details.

Usage

See complete listings in:

• cmd/orderedmap/example.go
• cmd/queuestack/example.go

Ordered Map

stable := true
om := orderedmap.NewSlice[Key,Value](sizeHint, stable)
om.Store(k, v)
om.Range(func(k K, v V) bool { fmt.Println(k, v); return true })
v, loaded := om.Load(k)
if !loaded { fmt.Printf("No entry for key %v\n", k)}
om.Delete(k) // Idempotent: does not fail on nonexistent keys.

Queues

q := queue.NewSliceQueue[Element](sizeHint)
q.Enqueue(e)
if lq, ok := q.(container.Countable); ok {
    fmt.Printf("elements in queue: %d\n", lq.Len())
}
for i := 0; i < 2; i++ {
    e, ok := q.Dequeue()
    fmt.Printf("Element: %v, ok: %t\n", e, ok)
}

Stacks

s := stack.NewSliceStack[Element](sizeHint)
s.Push(e)
if ls, ok := s.(container.Countable); ok {
    fmt.Printf("elements in stack: %d\n", ls.Len())
}
for i := 0; i < 2; i++ {
    e, ok := s.Pop()
    fmt.Printf("Element: %v, ok: %t\n", e, ok)
}

Running tests

The complete test coverage requires running not only the unit tests, but also the benchmarks, like:

    go test -race -run=. -bench=. -coverprofile=cover.out -covermode=atomic ./...

Documentation

Index

• type Countable
• type OrderedMap
• type Queue
• type Stack

Types

type Countable

type Countable interface {
	Len() int
}

Countable MAY be provided by some implementations.

type OrderedMap

type OrderedMap[K comparable, V any] interface {
	Delete(key K)
	Load(key K) (value V, loaded bool)
	Range(func(key K, value V) bool)
	Store(key K, value V)
}

type Queue

type Queue[E any] interface {
	Enqueue(E)
	// Dequeue removes the first element from the queue. If the queue is empty,
	// it returns the zero value of the element type, and ok is false.
	Dequeue() (e E, ok bool)
}

Queue is a generic queue with no concurrency guarantees. Instantiate by queue.New<implementation>Queue(sizeHint). The size hint MAY be used by some implementations to optimize storage.

type Stack

type Stack[E any] interface {
	Push(E)
	// Pop removes the top element from the stack. If the stack is empty,
	// it returns the zero value of the element type, and ok is false.
	Pop() (e E, ok bool)
}

Stack is a generic queue with no concurrency guarantees. Instantiate by stack.New<implementation>Stack(sizeHint). The size hint MAY be used by some implementations to optimize storage.