ordered

README

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))

Documentation

Overview

Package ordered is a zero dependency, generic ordered map implementation with iterator methods.

An ordered Map maintains insertion order using a doubly-linked list, providing O(1) time complexity for reads, writes, and deletes with O(n) space complexity. The map and linked list share value state to avoid data duplication and unnecessary allocations.

Map is not safe for concurrent access.

Index

• type Map
  • func NewMap[K comparable, V any](opts ...Option) *Map[K, V]
  • func (m *Map[K, V]) Clear()
  • func (m *Map[K, V]) Delete(key K)
  • func (m *Map[K, V]) Entries() iter.Seq2[K, V]
  • func (m *Map[K, V]) Get(key K) (value V, present bool)
  • func (m *Map[K, V]) Insert(key K, value V)
  • func (m *Map[K, V]) Keys() iter.Seq[K]
  • func (m *Map[K, V]) Len() int
  • func (m *Map[K, V]) Pop(key K) (value V, present bool)
  • func (m *Map[K, V]) Push(key K, value V)
  • func (m *Map[K, V]) Reverse() Reversed[K, V]
  • func (m *Map[K, V]) Set(key K, value V)
  • func (m *Map[K, V]) Values() iter.Seq[V]
• type Option
  • func WithCapacity(capacity int) Option
• type Reversed

Examples

• Map.Entries
• Map.Insert
• Map.Insert (NewKey)
• Map.Pop
• Map.Push
• Map.Reverse
• Map.Set
• NewMap
• NewMap (WithCapacity)

Types

type Map

type Map[K comparable, V any] struct {
	// contains filtered or unexported fields
}

Map is an ordered map backed by a doubly-linked list.

func NewMap

func NewMap[K comparable, V any](opts ...Option) *Map[K, V]

NewMap returns a new, empty ordered map. Options can be provided to configure the map during construction (see WithCapacity).

Example

package main

import (
	"fmt"

	"go.treyburn.dev/ordered"
)

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

	m.Set("a", 1)
	m.Set("b", 2)
	m.Set("c", 3)

	fmt.Println(m.Len())
	fmt.Println(m.Get("a"))
	fmt.Println(m.Get("missing"))

}

Output:
3
1 true
0 false

Example (WithCapacity)

package main

import (
	"fmt"

	"go.treyburn.dev/ordered"
)

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

	m.Set("a", 1)
	m.Set("b", 2)
	m.Set("c", 3)

	fmt.Println(m.Len())
	for k, v := range m.Entries() {
		fmt.Printf("%s:%d ", k, v)
	}
	fmt.Println()

}

Output:
3
a:1 b:2 c:3

func (*Map[K, V]) Clear

func (m *Map[K, V]) Clear()

Clear removes all entries in the map.

func (*Map[K, V]) Delete

func (m *Map[K, V]) Delete(key K)

Delete removes a given key from the map. If the key does not exist then this is a no-op. The Map order is updated to reflect the removal of this item.

func (*Map[K, V]) Entries

func (m *Map[K, V]) Entries() iter.Seq2[K, V]

Entries yields an iterator of key/value pair entries over the map's ordered keyspace.

Example

package main

import (
	"fmt"

	"go.treyburn.dev/ordered"
)

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

	m.Set("a", 1)
	m.Set("b", 2)
	m.Set("c", 3)

	for k, v := range m.Entries() {
		fmt.Printf("%s => %d\n", k, v)
	}

}

Output:
a => 1
b => 2
c => 3

func (*Map[K, V]) Get

func (m *Map[K, V]) Get(key K) (value V, present bool)

Get retrieves the value for a given key and a bool indicating whether the key was present.

func (*Map[K, V]) Insert

func (m *Map[K, V]) Insert(key K, value V)

Insert stores the value for the given key as the first entry in the map. If the key is already present, its value is updated, and it is moved to the front of the order.

Example

package main

import (
	"fmt"

	"go.treyburn.dev/ordered"
)

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

	m.Set("a", 1)
	m.Set("b", 2)
	m.Set("c", 3)

	// Insert on an existing key updates the value and moves it to the front
	m.Insert("c", 30)

	for k, v := range m.Entries() {
		fmt.Printf("%s:%d ", k, v)
	}
	fmt.Println()

}

Output:
c:30 a:1 b:2

Example (NewKey)

package main

import (
	"fmt"

	"go.treyburn.dev/ordered"
)

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

	m.Set("a", 1)
	m.Set("b", 2)

	// Insert a new key: added to the front
	m.Insert("c", 3)

	for k, v := range m.Entries() {
		fmt.Printf("%s:%d ", k, v)
	}
	fmt.Println()

}

Output:
c:3 a:1 b:2

func (*Map[K, V]) Keys

func (m *Map[K, V]) Keys() iter.Seq[K]

Keys yields an iterator of keys over the map's ordered keyspace.

func (*Map[K, V]) Len

func (m *Map[K, V]) Len() int

Len returns the number of items in the map.

func (*Map[K, V]) Pop

func (m *Map[K, V]) Pop(key K) (value V, present bool)

Pop returns the value for a given key and a bool indicating whether the key was present. Additionally, the key is removed from the map and the order updated to reflect this.

Example

package main

import (
	"fmt"

	"go.treyburn.dev/ordered"
)

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

	m.Set("a", 1)
	m.Set("b", 2)
	m.Set("c", 3)

	v, ok := m.Pop("b")
	fmt.Println(v, ok)

	v, ok = m.Pop("missing")
	fmt.Println(v, ok)

	for k, v := range m.Entries() {
		fmt.Printf("%s:%d ", k, v)
	}
	fmt.Println()

}

Output:
2 true
0 false
a:1 c:3

func (*Map[K, V]) Push

func (m *Map[K, V]) Push(key K, value V)

Push stores the value for the given key as the last entry in the map. If the key already exists, its value is updated, and it is moved to the back of the order.

Example

package main

import (
	"fmt"

	"go.treyburn.dev/ordered"
)

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

	m.Set("a", 1)
	m.Set("b", 2)
	m.Set("c", 3)

	// Push on an existing key updates the value and moves it to the back
	m.Push("a", 10)

	for k, v := range m.Entries() {
		fmt.Printf("%s:%d ", k, v)
	}
	fmt.Println()

}

Output:
b:2 c:3 a:10

func (*Map[K, V]) Reverse

func (m *Map[K, V]) Reverse() Reversed[K, V]

Reverse returns a Reversed view that yields iterators in reverse order over the Map keyspace.

Example

package main

import (
	"fmt"

	"go.treyburn.dev/ordered"
)

func main() {
	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)
	}

}

Output:
c => 3
b => 2
a => 1

func (*Map[K, V]) Set

func (m *Map[K, V]) Set(key K, value V)

Set stores a value for a given key. If the key already exists, then the associated value is updated. If the key is new to the map then it is added as the latest item in order.

Example

package main

import (
	"fmt"

	"go.treyburn.dev/ordered"
)

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

	m.Set("a", 1)
	m.Set("b", 2)
	m.Set("c", 3)

	// Set on an existing key updates the value but preserves order
	m.Set("a", 10)

	for k, v := range m.Entries() {
		fmt.Printf("%s:%d ", k, v)
	}
	fmt.Println()

}

Output:
a:10 b:2 c:3

func (*Map[K, V]) Values

func (m *Map[K, V]) Values() iter.Seq[V]

Values yields an iterator of values over the map's ordered keyspace.

type Option

type Option func(*config)

Option allows for additional configurations to be set during construction of the Map.

func WithCapacity

func WithCapacity(capacity int) Option

WithCapacity specifies an initial capacity for the backing store of the Map during construction. If the given capacity is less than or equal to 0, then it will be silently ignored.

type Reversed

type Reversed[K comparable, V any] interface {
	// Keys yields a reverse iterator of keys over the map's ordered keyspace.
	Keys() iter.Seq[K]
	// Values yields a reverse iterator of values over the map's ordered keyspace.
	Values() iter.Seq[V]
	// Entries yields a reverse iterator of key/value pair entries over the map's ordered keyspace.
	Entries() iter.Seq2[K, V]
	// contains filtered or unexported methods
}

Reversed is an interface that provides reverse iteration over an ordered keyspace.