go-ordmap

Persistent generic ordered maps for Go.

This is v2 which utilizes Go 1.23+ iterators (iter.Seq2) for efficient and idiomatic collection traversal. If you can't (or don't want to) use generics or Go 1.23, there is still v1 which uses code generation. See v1 branch.

Rationale

Standard library does not provide a key-value store data structure that would also allow quick access to minimum/maximum and in-order iteration.

This package provides such data structure (called OrdMap for "ordered map") and implements it on top of AVL trees (self balancing binary trees). This allows us O(log n) read/write access to arbitrary key as well as to the min & max while still supporting O(n) iteration over elements - just that it's now in order.

One detail that may not be idiomatic for Go is that these OrdMaps are persistent data structures - meaning that each operation gives you back a new map while keeping the old intact. This is beneficial when you have many concurrent readers - your writer can advance while the readers still traverse the old versions (kind of similar to MVCC)

In order to facilitate safe API and efficient internalization this module uses type parameters and thus requires go 1.23+.

Usage

go get github.com/edofic/go-ordmap/v2@latest

You only need to remember to always assign the returned value of all operations; the original object is never updated in-place:

package main

import (
	"fmt"

	"github.com/edofic/go-ordmap/v2"
)

func main() {
	m1 := ordmap.NewBuiltin[int, string]()

	m1 = m1.Insert(1, "foo") // adding entries
	m1 = m1.Insert(2, "baz")
	m1 = m1.Insert(2, "bar") // will override
	fmt.Println(m1.Get(2))   // access by key
	m1 = m1.Insert(3, "baz")
	// this is how you can efficiently iterate in-order
	for k, v := range m1.All() {
		fmt.Println(k, v)
	}
	m1 = m1.Remove(1)         // can also remove entries
	fmt.Println(m1.Entries()) // or get a slice of all of them

	// can use another map of different type in the same package
	m2 := ordmap.NewBuiltin[int, int]()
	v, ok := m2.Get(0)
	fmt.Println("wat", v, ok)
	m2 = m2.Insert(1, 1) // this one has "raw" ints for keys
	m2 = m2.Insert(2, 3) // in order to support this you will also need to pass
	m2 = m2.Insert(2, 2) // `-less "<"` to the genreeator in order to use
	m2 = m2.Insert(3, 3) // native comparator
	// can iterate in reverse as well
	for k, v := range m2.Backward() {
		fmt.Println(k, v)
	}
	fmt.Println(m2.Min(), m2.Max()) // access the extremes

    // Range iteration: Start iterating from a specific key
    // This is useful for prefix scans or finding items >= K
    for k, v := range m2.From(2) {
        fmt.Println("From 2:", k, v)
    }
}

See examples for more.

Generational Map

For use cases with high churn (many short-lived items), the generational package provides an optimized wrapper. It uses a "Young" and "Old" generation approach (inspired by Generational GC and LSM-trees).

• Writes: Extremely fast (only affects the small Young generation).
• Reads: Slightly slower (checks both generations).
• Iteration: Performed via a live merge of both generations.

Usage

import "github.com/edofic/go-ordmap/v2/generational"

// Create a map with a young generation limit of 1000
m := generational.New[MyKey, MyValue](1000)

m = m.Insert(k, v)
m = m.Remove(k)
val, ok := m.Get(k)

// Iterators work just like the standard OrdMap
for k, v := range m.All() {
    // ...
}

You will need to provide the Less method on your key type so the map knows how to order itself. Or if you want to use one of the builtin types (e.g. int) you can use NewBuiltin which only takes supported types.

func (k MyKey) Less(k2 MyKey) bool {
    ...
}

func (k MyKey) Less(k2 MyKey) bool {
    ...
}

Development

Go 1.23+ required.

Testing

Standard testing

go test ./...

100% test coverage expected on the core implementation (avl.go)