orderedmap

README

🔃 github.com/elliotchance/orderedmap/v2

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/v2"

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

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

	m.Delete("qux")
}

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

Be careful using Keys() as it will create a copy of all of the keys so it's only suitable for a small number of items:

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

For larger maps you should use Front() or Back() to iterate per element:

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

The iterator is 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.

Documentation

Index

• type Element
  • func (e *Element) Next() *Element
  • func (e *Element) Prev() *Element
• type OrderedMap
  • func NewOrderedMap() *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) 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 (*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) 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).