ordered map

A zero dependency, generic ordered map with iterator methods.

Installation

go get -u go.treyburn.dev/ordered

About

This is a minimal implementation of an ordered map with zero dependencies. It is backed by a doubly-linked list for optimal time and space complexity.

ordered.Map is not meant to be used for concurrent access and does not support it.

This package offers the following benefits:

• Zero dependencies and pure Go.
• Time complexity of O(1) for reads, writes, and deletes.
• Space complexity of O(n) with no unnecessary allocations or copying.
• Simple, ergonomic API with generics and iterator methods.

Usage

ordered.Map keys must satisfy the comparable constraint. Values can be any type.

package main

import (
	"fmt"

	"go.treyburn.dev/ordered"
)

func main() {
	m := ordered.NewMap[string, string]()

	// Set adds entries in order
	m.Set("foo", "bar")
	m.Set("bar", "baz")
	m.Set("zed", "toi")

	fmt.Println(m.Get("foo"))          // bar, true
	fmt.Println(m.Get("unknown"))      // "", false

	fmt.Println(m.Len()) // 3

	// Iterate over all entries in order
	for k, v := range m.Entries() {
		fmt.Printf("%s => %s\n", k, v)
	}
	// foo => bar
	// bar => baz
	// zed => toi
}

Set vs Push vs Insert

Set, Push, and Insert all store a value for a given key, but they differ in how they handle ordering:

• Set adds new keys to the back. For existing keys it updates the value in place and the key keeps its current order position.
• Push adds new keys to the back. For existing keys it updates the value and moves the key to the back.
• Insert adds new keys to the front. For existing keys it updates the value and moves the key to the front.

m := ordered.NewMap[string, int]()
m.Set("a", 1)
m.Set("b", 2)
m.Set("c", 3)
// order: a(1), b(2), c(3)

// Set on an existing key: value changes, order does not
m.Set("a", 10)
// order: a(10), b(2), c(3)

// Push on an existing key: value changes AND key moves to the back
m.Push("a", 100)
// order: b(2), c(3), a(100)

// Insert on an existing key: value changes AND key moves to the front
m.Insert("a", 1)
// order: a(1), b(2), c(3)

// Insert a new key: added to the front
m.Insert("d", 4)
// order: d(4), a(1), b(2), c(3)

Delete and Pop

Delete removes a key from the map. Pop does the same but also returns the value.

m := ordered.NewMap[string, int]()
m.Set("a", 1)
m.Set("b", 2)
m.Set("c", 3)

m.Delete("b")
// order: a(1), c(3)

value, ok := m.Pop("c")
fmt.Println(value, ok) // 3, true
// order: a(1)

// Delete and Pop are no-ops for missing keys
m.Delete("unknown")
_, ok = m.Pop("unknown")
fmt.Println(ok) // false

Iterators

Keys, Values, and Entries return Go 1.23+ iterators (iter.Seq and iter.Seq2) over the ordered keyspace.

m := ordered.NewMap[string, int]()
m.Set("a", 1)
m.Set("b", 2)
m.Set("c", 3)

for k := range m.Keys() {
	fmt.Println(k) // a, b, c
}

for v := range m.Values() {
	fmt.Println(v) // 1, 2, 3
}

for k, v := range m.Entries() {
	fmt.Printf("%s => %d\n", k, v)
}
// a => 1
// b => 2
// c => 3

Reverse Iteration

Reverse returns a Reversed view that provides Keys, Values, and Entries iterators in reverse order.

m := ordered.NewMap[string, int]()
m.Set("a", 1)
m.Set("b", 2)
m.Set("c", 3)

for k, v := range m.Reverse().Entries() {
	fmt.Printf("%s => %d\n", k, v)
}
// c => 3
// b => 2
// a => 1

Options

NewMap accepts optional configuration via functional options. For example, WithCapacity pre-allocates the backing store when the expected size is known:

m := ordered.NewMap[string, int](ordered.WithCapacity(1000))