orderedmap

package module
v1.0.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Dec 20, 2025 License: Apache-2.0 Imports: 10 Imported by: 0

README

Golang Ordered Maps

Same as regular maps, but also remembers the order in which keys were inserted, akin to Python's collections.OrderedDicts.

It offers the following features:

  • optimal runtime performance (all operations are constant time)
  • optimal memory usage (only one copy of values, no unnecessary memory allocation)
  • allows iterating from newest or oldest keys indifferently, without memory copy, allowing to break the iteration, and in time linear to the number of keys iterated over rather than the total length of the ordered map
  • idiomatic API, akin to that of container/list
  • supports any generic types for both keys and values.
  • support for JSON and YAML marshalling

Documentation

The full documentation is available on pkg.go.dev.

Installation

go get -u github.com/gnuos/omap

Or use your favorite golang vendoring tool!

Supported go versions

Go >= 1.23

Example / usage

package main

import (
	"fmt"
	"strings"

	orderedmap "github.com/gnuos/omap"
)

func main() {
	om := orderedmap.New[string, string]()

	om.Set("foo", "bar")
	om.Set("bar", "baz")
	om.Set("coucou", "toi")

	fmt.Println(om.Get("foo"))          // => "bar", true
	fmt.Println(om.Get("i dont exist")) // => "", false

	// iterating pairs from oldest to newest:
	for pair := om.Oldest(); pair != nil; pair = pair.Next() {
		fmt.Printf("%s => %s\n", pair.Key, pair.Value)
	} // prints:
	// foo => bar
	// bar => baz
	// coucou => toi

	// iterating over the 2 newest pairs:
	i := 0
	for pair := om.Newest(); pair != nil; pair = pair.Prev() {
		fmt.Printf("%s => %s\n", pair.Key, pair.Value)
		i++
		if i >= 2 {
			break
		}
	} // prints:
	// coucou => toi
	// bar => baz
	
	// removing all pairs which do not have an "o" in their key
	om.Filter(func(key, value string) bool { return strings.Contains(key, "o") })
	
	// new iteration syntax
	for key, value := range om.FromOldest() {
		fmt.Printf("%s => %s\n", key, value)
	}// prints:
	// foo => bar
	// coucou => toi
}

An OrderedMap's keys must implement comparable, and its values can be anything, for example:

type myStruct struct {
	payload string
}

func main() {
	om := orderedmap.New[int, *myStruct]()

	om.Set(12, &myStruct{"foo"})
	om.Set(1, &myStruct{"bar"})

	value, present := om.Get(12)
	if !present {
		panic("should be there!")
	}
	fmt.Println(value.payload) // => foo

	for pair := om.Oldest(); pair != nil; pair = pair.Next() {
		fmt.Printf("%d => %s\n", pair.Key, pair.Value.payload)
	} // prints:
	// 12 => foo
	// 1 => bar
}

Also worth noting that you can provision ordered maps with a capacity hint, as you would do by passing an optional hint to make(map[K]V, capacity):

om := orderedmap.New[int, *myStruct](28)

You can also pass in some initial data to store in the map:

om := orderedmap.New[int, string](orderedmap.WithInitialData[int, string](
	orderedmap.Pair[int, string]{
		Key:   12,
		Value: "foo",
	},
	orderedmap.Pair[int, string]{
		Key:   28,
		Value: "bar",
	},
))

OrderedMaps also support JSON serialization/deserialization, and preserves order:

// serialization
data, err := json.Marshal(om)
...

// deserialization
om := orderedmap.New[string, string]() // or orderedmap.New[int, any](), or any type you expect
err := json.Unmarshal(data, &om)
...

Similarly, it also supports YAML serialization/deserialization using the yaml.v3 package, which also preserves order:

// serialization
data, err := yaml.Marshal(om)
...

// deserialization
om := orderedmap.New[string, string]() // or orderedmap.New[int, any](), or any type you expect
err := yaml.Unmarshal(data, &om)
...

Iterator support (go >= 1.23)

The FromOldest, FromNewest, KeysFromOldest, KeysFromNewest, ValuesFromOldest and ValuesFromNewest methods return iterators over the map's pairs, starting from the oldest or newest pair, respectively.

For example:

om := orderedmap.New[int, string]()
om.Set(1, "foo")
om.Set(2, "bar")
om.Set(3, "baz")

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

// prints:
// 1 => foo
// 2 => bar
// 3 => baz

for k := range om.KeysNewest() {
	fmt.Printf("%d\n", k)
}

// prints:
// 3
// 2
// 1

From is a convenience function that creates a new OrderedMap from an iterator over key-value pairs.

om := orderedmap.New[int, string]()
om.Set(1, "foo")
om.Set(2, "bar")
om.Set(3, "baz")

om2 := orderedmap.From(om.FromOldest())

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

// prints:
// 1 => foo
// 2 => bar
// 3 => baz

Alternatives

There are several other ordered map golang implementations out there, but I believe that at the time of writing none of them offer the same functionality as this library; more specifically:

  • iancoleman/orderedmap only accepts string keys, its Delete operations are linear
  • cevaris/ordered_map uses a channel for iterations, and leaks goroutines if the iteration is interrupted before fully traversing the map
  • mantyr/iterator also uses a channel for iterations, and its Delete operations are linear
  • samdolan/go-ordered-map adds unnecessary locking (users should add their own locking instead if they need it), its Delete and Get operations are linear, iterations trigger a linear memory allocation

Documentation

Overview

Package list implements a doubly linked list.

To iterate over a list (where l is a *List): 

for e := l.Front(); e != nil; e = e.Next() {
	// do something with e.Value
}

Package orderedmap implements an ordered map, i.e. a map that also keeps track of the order in which keys were inserted.

All operations are constant-time.

Github repo: https://github.com/wk8/go-ordered-map

Example 
package main

import (
	"encoding/json"
	"fmt"

	orderedmap "github.com/gnuos/omap"
)

func main() {
	om := orderedmap.New[string, string](3)

	om.Set("foo", "bar")
	om.Set("bar", "baz")
	om.Set("coucou", "toi")

	fmt.Println("## Get operations: ##")
	fmt.Println(om.Get("foo"))
	fmt.Println(om.Get("i dont exist"))
	fmt.Println(om.Value("coucou"))

	fmt.Println("## Iterating over pairs from oldest to newest: ##")
	for pair := om.Oldest(); pair != nil; pair = pair.Next() {
		fmt.Printf("%s => %s\n", pair.Key, pair.Value)
	}

	fmt.Println("## Iterating over the 2 newest pairs: ##")
	i := 0
	for pair := om.Newest(); pair != nil; pair = pair.Prev() {
		fmt.Printf("%s => %s\n", pair.Key, pair.Value)
		i++
		if i >= 2 {
			break
		}
	}

	fmt.Println("## JSON serialization: ##")
	data, err := json.Marshal(om)
	if err != nil {
		panic(err)
	}
	fmt.Println(string(data))

	fmt.Println("## JSON deserialization: ##")
	om2 := orderedmap.New[string, string]()
	if err := json.Unmarshal(data, &om2); err != nil {
		panic(err)
	}
	fmt.Println(om2.Oldest().Key)

}

Output:

## Get operations: ##
bar true
 false
toi
## Iterating over pairs from oldest to newest: ##
foo => bar
bar => baz
coucou => toi
## Iterating over the 2 newest pairs: ##
coucou => toi
bar => baz
## JSON serialization: ##
{"foo":"bar","bar":"baz","coucou":"toi"}
## JSON deserialization: ##
foo

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Element 

type Element[T any] struct {

	// The value stored with this element.
	Value T
	// contains filtered or unexported fields
}

Element is an element of a linked list.

func (*Element[T]) NextItem 

func (e *Element[T]) NextItem() *Element[T]

Next returns the next list element or nil.

func (*Element[T]) PrevItem 

func (e *Element[T]) PrevItem() *Element[T]

Prev returns the previous list element or nil.

type InitOption 

type InitOption[K comparable, V any] func(config *initConfig[K, V])

func WithCapacity 

func WithCapacity[K comparable, V any](capacity int) InitOption[K, V]

WithCapacity allows giving a capacity hint for the map, akin to the standard make(map[K]V, capacity).

func WithDisableHTMLEscape 

func WithDisableHTMLEscape[K comparable, V any]() InitOption[K, V]

WithDisableHTMLEscape disables HTMl escaping when marshalling to JSON

func WithInitialData 

func WithInitialData[K comparable, V any](initialData ...Pair[K, V]) InitOption[K, V]

WithInitialData allows passing in initial data for the map.

type KeyNotFoundError 

type KeyNotFoundError[K comparable] struct {
	MissingKey K
}

KeyNotFoundError may be returned by functions in this package when they're called with keys that are not present in the map.

func (*KeyNotFoundError[K]) Error 

func (e *KeyNotFoundError[K]) Error() string

type List 

type List[T any] struct {
	// contains filtered or unexported fields
}

List represents a doubly linked list. The zero value for List is an empty list ready to use.

func NewList 

func NewList[T any]() *List[T]

New returns an initialized list.

func (*List[T]) Append 

func (l *List[T]) Append(other *List[T])

PushBackList inserts a copy of another list at the back of list l. The lists l and other may be the same. They must not be nil.

func (*List[T]) First 

func (l *List[T]) First() *Element[T]

Front returns the first element of list l or nil if the list is empty.

func (*List[T]) Init 

func (l *List[T]) Init() *List[T]

Init initializes or clears list l.

func (*List[T]) InsertAfter 

func (l *List[T]) InsertAfter(v T, mark *Element[T]) *Element[T]

InsertAfter inserts a new element e with value v immediately after mark and returns e. If mark is not an element of l, the list is not modified. The mark must not be nil.

func (*List[T]) InsertBefore 

func (l *List[T]) InsertBefore(v T, mark *Element[T]) *Element[T]

InsertBefore inserts a new element e with value v immediately before mark and returns e. If mark is not an element of l, the list is not modified. The mark must not be nil.

func (*List[T]) Last 

func (l *List[T]) Last() *Element[T]

Back returns the last element of list l or nil if the list is empty.

func (*List[T]) Len 

func (l *List[T]) Len() int

Len returns the number of elements of list l. The complexity is O(1).

func (*List[T]) MoveAfter 

func (l *List[T]) MoveAfter(e, mark *Element[T])

MoveAfter moves element e to its new position after mark. If e or mark is not an element of l, or e == mark, the list is not modified. The element and mark must not be nil.

func (*List[T]) MoveBefore 

func (l *List[T]) MoveBefore(e, mark *Element[T])

MoveBefore moves element e to its new position before mark. If e or mark is not an element of l, or e == mark, the list is not modified. The element and mark must not be nil.

func (*List[T]) MoveToBack 

func (l *List[T]) MoveToBack(e *Element[T])

MoveToBack moves element e to the back of list l. If e is not an element of l, the list is not modified. The element must not be nil.

func (*List[T]) MoveToFront 

func (l *List[T]) MoveToFront(e *Element[T])

MoveToFront moves element e to the front of list l. If e is not an element of l, the list is not modified. The element must not be nil.

func (*List[T]) Pop 

func (l *List[T]) Pop(e *Element[T]) T

Remove removes e from l if e is an element of list l. It returns the element value e.Value. The element must not be nil.

func (*List[T]) Push 

func (l *List[T]) Push(v T) *Element[T]

PushBack inserts a new element e with value v at the back of list l and returns e.

func (*List[T]) PushFrontList 

func (l *List[T]) PushFrontList(other *List[T])

PushFrontList inserts a copy of another list at the front of list l. The lists l and other may be the same. They must not be nil.

func (*List[T]) Shift 

func (l *List[T]) Shift(v T) *Element[T]

PushFront inserts a new element e with value v at the front of list l and returns e.

type OrderedMap 

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

func From 

func From[K comparable, V any](i iter.Seq2[K, V]) *OrderedMap[K, V]

From creates a new OrderedMap from an iterator over key-value pairs.

func New 

func New[K comparable, V any](options ...any) *OrderedMap[K, V]

New creates a new OrderedMap. options can either be one or several InitOption[K, V], or a single integer, which is then interpreted as a capacity hint, à la make(map[K]V, capacity).

func (*OrderedMap[K, V]) AddPairs 

func (om *OrderedMap[K, V]) AddPairs(pairs ...Pair[K, V])

AddPairs allows setting multiple pairs at a time. It's equivalent to calling Set on each pair sequentially.

func (*OrderedMap[K, V]) Delete 

func (om *OrderedMap[K, V]) Delete(key K) (val V, present bool)

Delete removes the key-value pair, and returns what `Get` would have returned on that key prior to the call to `Delete`.

func (*OrderedMap[K, V]) Filter 

func (om *OrderedMap[K, V]) Filter(predicate func(K, V) bool)

func (*OrderedMap[K, V]) FromNewest 

func (om *OrderedMap[K, V]) FromNewest() iter.Seq2[K, V]

FromNewest returns an iterator over all the key-value pairs in the map, starting from the newest pair.

func (*OrderedMap[K, V]) FromOldest 

func (om *OrderedMap[K, V]) FromOldest() iter.Seq2[K, V]

FromOldest returns an iterator over all the key-value pairs in the map, starting from the oldest pair.

func (*OrderedMap[K, V]) Get 

func (om *OrderedMap[K, V]) Get(key K) (val V, present bool)

Get looks for the given key, and returns the value associated with it, or V's nil value if not found. The boolean it returns says whether the key is present in the map.

func (*OrderedMap[K, V]) GetAndMoveToBack 

func (om *OrderedMap[K, V]) GetAndMoveToBack(key K) (val V, err error)

GetAndMoveToBack combines Get and MoveToBack in the same call. If an error is returned, it will be a KeyNotFoundError.

func (*OrderedMap[K, V]) GetAndMoveToFront 

func (om *OrderedMap[K, V]) GetAndMoveToFront(key K) (val V, err error)

GetAndMoveToFront combines Get and MoveToFront in the same call. If an error is returned, it will be a KeyNotFoundError.

func (*OrderedMap[K, V]) GetPair 

func (om *OrderedMap[K, V]) GetPair(key K) *Pair[K, V]

GetPair looks for the given key, and returns the pair associated with it, or nil if not found. The Pair struct can then be used to iterate over the ordered map from that point, either forward or backward.

func (*OrderedMap[K, V]) KeysFromNewest 

func (om *OrderedMap[K, V]) KeysFromNewest() iter.Seq[K]

KeysFromNewest returns an iterator over all the keys in the map, starting from the newest pair.

func (*OrderedMap[K, V]) KeysFromOldest 

func (om *OrderedMap[K, V]) KeysFromOldest() iter.Seq[K]

KeysFromOldest returns an iterator over all the keys in the map, starting from the oldest pair.

func (*OrderedMap[K, V]) Len 

func (om *OrderedMap[K, V]) Len() int

Len returns the length of the ordered map.

func (*OrderedMap[K, V]) Load 

func (om *OrderedMap[K, V]) Load(key K) (V, bool)

Load is an alias for Get, mostly to present an API similar to `sync.Map`'s.

func (*OrderedMap[K, V]) MarshalJSON 

func (om *OrderedMap[K, V]) MarshalJSON() ([]byte, error)

MarshalJSON implements the json.Marshaler interface.

func (*OrderedMap[K, V]) MarshalYAML 

func (om *OrderedMap[K, V]) MarshalYAML() (any, error)

MarshalYAML implements the yaml.Marshaler interface.

func (*OrderedMap[K, V]) MoveAfter 

func (om *OrderedMap[K, V]) MoveAfter(key, markKey K) error

MoveAfter moves the value associated with key to its new position after the one associated with markKey. Returns an error iff key or markKey are not present in the map. If an error is returned, it will be a KeyNotFoundError.

func (*OrderedMap[K, V]) MoveBefore 

func (om *OrderedMap[K, V]) MoveBefore(key, markKey K) error

MoveBefore moves the value associated with key to its new position before the one associated with markKey. Returns an error iff key or markKey are not present in the map. If an error is returned, it will be a KeyNotFoundError.

func (*OrderedMap[K, V]) MoveToBack 

func (om *OrderedMap[K, V]) MoveToBack(key K) error

MoveToBack moves the value associated with key to the back of the ordered map, i.e. makes it the newest pair in the map. Returns an error iff key is not present in the map. If an error is returned, it will be a KeyNotFoundError.

func (*OrderedMap[K, V]) MoveToFront 

func (om *OrderedMap[K, V]) MoveToFront(key K) error

MoveToFront moves the value associated with key to the front of the ordered map, i.e. makes it the oldest pair in the map. Returns an error iff key is not present in the map. If an error is returned, it will be a KeyNotFoundError.

func (*OrderedMap[K, V]) Newest 

func (om *OrderedMap[K, V]) Newest() *Pair[K, V]

Newest returns a pointer to the newest pair. It's meant to be used to iterate on the ordered map's pairs from the newest to the oldest, e.g.: for pair := orderedMap.Newest(); pair != nil; pair = pair.Prev() { fmt.Printf("%v => %v\n", pair.Key, pair.Value) }

func (*OrderedMap[K, V]) Oldest 

func (om *OrderedMap[K, V]) Oldest() *Pair[K, V]

Oldest returns a pointer to the oldest pair. It's meant to be used to iterate on the ordered map's pairs from the oldest to the newest, e.g.: for pair := orderedMap.Oldest(); pair != nil; pair = pair.Next() { fmt.Printf("%v => %v\n", pair.Key, pair.Value) }

func (*OrderedMap[K, V]) Set 

func (om *OrderedMap[K, V]) Set(key K, value V) (val V, present bool)

Set sets the key-value pair, and returns what `Get` would have returned on that key prior to the call to `Set`.

func (*OrderedMap[K, V]) Store 

func (om *OrderedMap[K, V]) Store(key K, value V) (V, bool)

Store is an alias for Set, mostly to present an API similar to `sync.Map`'s.

func (*OrderedMap[K, V]) UnmarshalJSON 

func (om *OrderedMap[K, V]) UnmarshalJSON(data []byte) error

UnmarshalJSON implements the json.Unmarshaler interface.

func (*OrderedMap[K, V]) UnmarshalYAML 

func (om *OrderedMap[K, V]) UnmarshalYAML(value *yaml.Node) error

UnmarshalYAML implements the yaml.Unmarshaler interface.

func (*OrderedMap[K, V]) Value 

func (om *OrderedMap[K, V]) Value(key K) (val V)

Value returns the value associated with the given key or the zero value.

func (*OrderedMap[K, V]) ValuesFromNewest 

func (om *OrderedMap[K, V]) ValuesFromNewest() iter.Seq[V]

ValuesFromNewest returns an iterator over all the values in the map, starting from the newest pair.

func (*OrderedMap[K, V]) ValuesFromOldest 

func (om *OrderedMap[K, V]) ValuesFromOldest() iter.Seq[V]

ValuesFromOldest returns an iterator over all the values in the map, starting from the oldest pair.

type Pair 

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

func (*Pair[K, V]) Next 

func (p *Pair[K, V]) Next() *Pair[K, V]

Next returns a pointer to the next pair.

func (*Pair[K, V]) Prev 

func (p *Pair[K, V]) Prev() *Pair[K, V]

Prev returns a pointer to the previous pair.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.