orderedmap

README

🔃 github.com/elliotchance/orderedmap

Installation

go get -u github.com/elliotchance/orderedmap

Basic Usage

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

m := orderedmap.NewOrderedMap()

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

m.Delete("qux")

Internally an *OrderedMap uses a combination of a map and linked list.

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.

Performance

CPU: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz

RAM: 8GB

System: Windows 10

$go test -benchmem -run=^$ github.com/elliotchance/orderedmap -bench BenchmarkAll

map[int]bool

	map	orderedmap
set	198 ns/op, 44 B/op	722 ns/op, 211 B/op
get	18 ns/op, 0 B/op	37.3 ns/op, 0 B/op
delete	888 ns/op, 211 B/op	280 ns/op, 44 B/op
Iterate	206 ns/op, 44 B/op	693 ns/op, 259 B/op

map[string]bool(PS : Use strconv.Itoa())

	map	orderedmap
set	421 ns/op, 86 B/op	1048 ns/op, 243 B/op
get	81.1 ns/op, 2 B/op	97.8 ns/op, 2 B/op
delete	737 ns/op, 122 B/op	1188 ns/op, 251 B/op
Iterate all	14706 ns/op, 1 B/op	52671 ns/op, 16391 B/op

Big map[int]bool (10000000 keys)

	map	orderedmap
set all	1.834559 s/op, 423.9470291 MB/op	7.5564667 s/op, 1784.1483 MB/op
get all	2.6367878 s/op, 423.9698 MB/op	9.0232475 s/op, 1784.1086 MB/op
Iterate all	1.9526784 s/op, 423.9042 MB/op	8.2495265 s/op, 1936.7619 MB/op

Big map[string]bool (10000000 keys)

	map	orderedmap
set all	4.8893923 s/op, 921.33435 MB/op	10.4405527 s/op, 2089.0144 MB/op
get all	7.122791 s/op, 997.3802643 MB/op	13.2613692 s/op, 2165.09521 MB/op
Iterate all	5.1688922 s/op, 921.4619293 MB/op	12.6623711 s/op, 2241.5272064 MB/op

Documentation

Index

• type Element
  • func (e *Element) Next() *Element
  • func (e *Element) Prev() *Element
• type Elementer
• type Lister
• 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 {
	Key, Value interface{}
	// contains filtered or unexported fields
}

func (*Element) Next

func (e *Element) Next() *Element

Next returns the next element, or nil if it finished.

func (*Element) Prev

func (e *Element) Prev() *Element

Prev returns the previous element, or nil if it finished.

type Elementer

type Elementer interface {
	Next() Elementer
	Prev() Elementer
}

type Lister

type Lister interface {
	Init() Lister
	Len() int
	Front() Elementer
	Back() Elementer
	Remove(e Elementer) interface{}
	PushFront(v interface{}) Elementer
	PushBack(v interface{}) Elementer
	InsertBefore(v interface{}, mark Elementer) Elementer
	InsertAfter(v interface{}, mark Elementer) Elementer
	MoveToFront(e Elementer)
	MoveToBack(e Elementer)
	MoveBefore(e, mark Elementer)
	MoveAfter(e, mark Elementer)
	PushBackList(other Lister)
	PushFrontList(other Lister)
}

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