orderedmap

README

🔃 github.com/elliotchance/orderedmap/v3

Basic Usage

An *OrderedMap is a high performance ordered map that maintains amortized O(1) for Set, Get, Delete and Len:

import "github.com/elliotchance/orderedmap/v3"

func main() {
	m := orderedmap.NewOrderedMap[string, any]()

	m.Set("foo", "bar")
	m.Set("qux", 1.23)
	m.Set("123", true)

	m.Delete("qux")
}

[!NOTE]

• v3 requires Go v1.23 - If you need to support Go 1.18-1.22, you can use v2.
• v2 requires Go v1.18 for generics - If you need to support Go 1.17 or below, you can use v1.

Internally an *OrderedMap uses the composite type map combined with a trimmed down linked list to maintain the order.

Iterating

The following methods all return iterators that can be used to loop over elements in an ordered map:

• AllFromFront()
• AllFromBack()
• Keys()
• Values()

// Iterate through all elements from oldest to newest:
for key, value := range m.AllFromFront() {
	fmt.Println(key, value)
}

Iterators are safe to use bidirectionally, and will return nil once it goes beyond the first or last item. If the map is changing while the iteration is in-flight it may produce unexpected behavior.

If you want to get a slice of the map keys or values, you can use the standard slices.Collect method with the iterator returned from Keys() or Values():

fmt.Println(slices.Collect(m.Keys())
// [A B C]

Likewise, calling maps.Collect on the iterator returned from AllFromFront() will create a regular unordered map from the ordered one:

fmt.Println(maps.Collect(m.AllFromFront())
// [A:1 B:2 C:3]

If you don't want to use iterators, you can also manually loop over the elements using Front() or Back() with Next():

// Iterate through all elements from oldest to newest:
for el := m.Front(); el != nil; el = el.Next() {
    fmt.Println(el.Key, el.Value)
}

// You can also use Back and Prev to iterate in reverse:
for el := m.Back(); el != nil; el = el.Prev() {
    fmt.Println(el.Key, el.Value)
}

Documentation

Index

• type Element
  • func (e *Element) Next() *Element
  • func (e *Element) Prev() *Element
• type OrderedMap
  • func NewOrderedMap() *OrderedMap
  • func NewOrderedMapWithCapacity(capacity int) *OrderedMap
  • func (m *OrderedMap) Back() *Element
  • func (m *OrderedMap) Copy() *OrderedMap
  • func (m *OrderedMap) Delete(key interface{}) (didDelete bool)
  • func (m *OrderedMap) Front() *Element
  • func (m *OrderedMap) Get(key interface{}) (interface{}, bool)
  • func (m *OrderedMap) GetElement(key interface{}) *Element
  • func (m *OrderedMap) GetOrDefault(key, defaultValue interface{}) interface{}
  • func (m *OrderedMap) Has(key interface{}) bool
  • func (m *OrderedMap) Keys() (keys []interface{})
  • func (m *OrderedMap) Len() int
  • func (m *OrderedMap) Set(key, value interface{}) bool

Examples

• NewOrderedMap
• OrderedMap.Front

Types

type Element

type Element struct {

	// The key that corresponds to this element in the ordered map.
	Key interface{}

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

Element is an element of a null terminated (non circular) intrusive doubly linked list that contains the key of the correspondent element in the ordered map too.

func (*Element) Next

func (e *Element) Next() *Element

Next returns the next list element or nil.

func (*Element) Prev

func (e *Element) Prev() *Element

Prev returns the previous list element or nil.

type OrderedMap

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

func NewOrderedMap

func NewOrderedMap() *OrderedMap

Example

package main

import (
	"fmt"

	"github.com/elliotchance/orderedmap"
)

func main() {
	m := orderedmap.NewOrderedMap()

	m.Set("foo", "bar")
	m.Set("qux", 1.23)
	m.Set(123, true)

	m.Delete("qux")

	for _, key := range m.Keys() {
		value, _ := m.Get(key)
		fmt.Println(key, value)
	}
}

func NewOrderedMapWithCapacity

func NewOrderedMapWithCapacity(capacity int) *OrderedMap

NewOrderedMapWithCapacity creates a map with enough pre-allocated space to hold the specified number of elements.

func (*OrderedMap) Back

func (m *OrderedMap) Back() *Element

Back will return the element that is the last (most recent Set element). If there are no elements this will return nil.

func (*OrderedMap) Copy

func (m *OrderedMap) Copy() *OrderedMap

Copy returns a new OrderedMap with the same elements. Using Copy while there are concurrent writes may mangle the result.

func (*OrderedMap) Delete

func (m *OrderedMap) Delete(key interface{}) (didDelete bool)

Delete will remove a key from the map. It will return true if the key was removed (the key did exist).

func (*OrderedMap) Front

func (m *OrderedMap) Front() *Element

Front will return the element that is the first (oldest Set element). If there are no elements this will return nil.

Example

package main

import (
	"fmt"

	"github.com/elliotchance/orderedmap"
)

func main() {
	m := orderedmap.NewOrderedMap()
	m.Set(1, true)
	m.Set(2, true)

	for el := m.Front(); el != nil; el = el.Next() {
		fmt.Println(el)
	}
}

func (*OrderedMap) Get

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

Get returns the value for a key. If the key does not exist, the second return parameter will be false and the value will be nil.

func (*OrderedMap) GetElement

func (m *OrderedMap) GetElement(key interface{}) *Element

GetElement returns the element for a key. If the key does not exist, the pointer will be nil.

func (*OrderedMap) GetOrDefault

func (m *OrderedMap) GetOrDefault(key, defaultValue interface{}) interface{}

GetOrDefault returns the value for a key. If the key does not exist, returns the default value instead.

func (*OrderedMap) Has

func (m *OrderedMap) Has(key interface{}) bool

Has checks if a key exists in the map.

func (*OrderedMap) Keys

func (m *OrderedMap) Keys() (keys []interface{})

Keys returns all of the keys in the order they were inserted. If a key was replaced it will retain the same position. To ensure most recently set keys are always at the end you must always Delete before Set.

func (*OrderedMap) Len

func (m *OrderedMap) Len() int

Len returns the number of elements in the map.

func (*OrderedMap) Set

func (m *OrderedMap) Set(key, value interface{}) bool

Set will set (or replace) a value for a key. If the key was new, then true will be returned. The returned value will be false if the value was replaced (even if the value was the same).