orderedmap

README

Goland 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
• takes and returns generic interface{}s
• idiomatic API, akin to that of container/list

Installation

go get -u github.com/wk8/go-ordered-map

Or use your favorite golang vendoring tool!

Supported go versions

All go versions >= 1.13 are supported. There's no reason for older versions to not also work, but they're not part of the build matrix.

Documentation

The full documentation is available on godoc.org.

Example / usage

package main

import (
	"fmt"

	"github.com/wk8/go-ordered-map"
)

func main() {
	om := orderedmap.New()

	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")) // => <nil>, 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
}

All of OrderedMap's methods accept and return interface{}s, so you can use any type of keys that regular maps accept, as well pack/unpack arbitrary values, e.g.:

type myStruct struct {
	payload string
}

func main() {
	om := orderedmap.New()

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

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

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

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

om := orderedmap.New()

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("## 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
	}
}

Output:

## Get operations: ##
bar true
<nil> false
## Iterating over pairs from oldest to newest: ##
foo => bar
bar => baz
coucou => toi
## Iterating over the 2 newest pairs: ##
coucou => toi
bar => baz

Index

• type KeyNotFoundError
  • func (e *KeyNotFoundError) Error() string
• type OrderedMap
  • func New() *OrderedMap
  • func (om *OrderedMap) Delete(key interface{}) (interface{}, bool)
  • func (om *OrderedMap) Get(key interface{}) (interface{}, bool)
  • func (om *OrderedMap) GetPair(key interface{}) *Pair
  • func (om *OrderedMap) Len() int
  • func (om *OrderedMap) Load(key interface{}) (interface{}, bool)
  • func (om *OrderedMap) MoveAfter(key, markKey interface{}) error
  • func (om *OrderedMap) MoveBefore(key, markKey interface{}) error
  • func (om *OrderedMap) MoveToBack(key interface{}) error
  • func (om *OrderedMap) MoveToFront(key interface{}) error
  • func (om *OrderedMap) Newest() *Pair
  • func (om *OrderedMap) Oldest() *Pair
  • func (om *OrderedMap) Set(key interface{}, value interface{}) (interface{}, bool)
  • func (om *OrderedMap) Store(key interface{}, value interface{}) (interface{}, bool)
• type Pair
  • func (p *Pair) Next() *Pair
  • func (p *Pair) Prev() *Pair

Examples

• Package

Types

type KeyNotFoundError

type KeyNotFoundError struct {
	MissingKey interface{}
}

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

func (*KeyNotFoundError) Error

func (e *KeyNotFoundError) Error() string

type OrderedMap

type OrderedMap struct {
	// contains filtered or unexported fields
}

func New

func New() *OrderedMap

New creates a new OrderedMap.

func (*OrderedMap) Delete

func (om *OrderedMap) Delete(key interface{}) (interface{}, 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) Get

func (om *OrderedMap) Get(key interface{}) (interface{}, bool)

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

func (*OrderedMap) GetPair

func (om *OrderedMap) GetPair(key interface{}) *Pair

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

func (om *OrderedMap) Len() int

Len returns the length of the ordered map.

func (*OrderedMap) Load

func (om *OrderedMap) Load(key interface{}) (interface{}, bool)

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

func (*OrderedMap) MoveAfter

func (om *OrderedMap) MoveAfter(key, markKey interface{}) 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.

func (*OrderedMap) MoveBefore

func (om *OrderedMap) MoveBefore(key, markKey interface{}) 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.

func (*OrderedMap) MoveToBack

func (om *OrderedMap) MoveToBack(key interface{}) error

MoveToBack moves the value associated with key to the back of the ordered map. Returns an error iff key is not present in the map.

func (*OrderedMap) MoveToFront

func (om *OrderedMap) MoveToFront(key interface{}) error

MoveToFront moves the value associated with key to the front of the ordered map. Returns an error iff key is not present in the map.

func (*OrderedMap) Newest

func (om *OrderedMap) Newest() *Pair

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.Oldest(); pair != nil; pair = pair.Next() { fmt.Printf("%v => %v\n", pair.Key, pair.Value) }

func (*OrderedMap) Oldest

func (om *OrderedMap) Oldest() *Pair

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

func (om *OrderedMap) Set(key interface{}, value interface{}) (interface{}, 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) Store

func (om *OrderedMap) Store(key interface{}, value interface{}) (interface{}, bool)

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

type Pair

type Pair struct {
	Key   interface{}
	Value interface{}
	// contains filtered or unexported fields
}

func (*Pair) Next

func (p *Pair) Next() *Pair

Next returns a pointer to the next pair.

func (*Pair) Prev

func (p *Pair) Prev() *Pair

Previous returns a pointer to the previous pair.