README
¶
Go OrderedMap
An implementation of ordered map in Go. An ordered map preserves the original insertion order when iterating.
It's implemented by wrapping a map and a
doubly linked list.
The interface is intentionally kept the same with sync.Map to be used
interchangeably (except with added generics support).
Benchmark
This package comes with benchmark test to test against
builtin map and sync.Map:
$ go test -bench .
goos: linux
goarch: amd64
pkg: go.yhsif.com/orderedmap
cpu: Intel(R) Core(TM) i5-7260U CPU @ 2.20GHz
BenchmarkMap/DeleteEmpty/builtin-4 577845259 2.074 ns/op 0 B/op 0 allocs/op
BenchmarkMap/DeleteEmpty/sync-4 202597698 5.933 ns/op 0 B/op 0 allocs/op
BenchmarkMap/DeleteEmpty/ordered-4 20556426 58.21 ns/op 0 B/op 0 allocs/op
BenchmarkMap/LoadEmpty/builtin-4 540843502 2.219 ns/op 0 B/op 0 allocs/op
BenchmarkMap/LoadEmpty/sync-4 202360122 5.920 ns/op 0 B/op 0 allocs/op
BenchmarkMap/LoadEmpty/ordered-4 26017804 46.28 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Store1/builtin-4 100000000 10.48 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Store1/sync-4 6121250 196.4 ns/op 48 B/op 3 allocs/op
BenchmarkMap/Store1/ordered-4 12191223 97.90 ns/op 32 B/op 1 allocs/op
BenchmarkMap/Store2/builtin-4 100000000 11.28 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Store2/sync-4 6063440 197.1 ns/op 48 B/op 3 allocs/op
BenchmarkMap/Store2/ordered-4 11598100 102.0 ns/op 32 B/op 1 allocs/op
BenchmarkMap/Update1/builtin-4 100000000 10.46 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Update1/sync-4 6090291 196.7 ns/op 48 B/op 3 allocs/op
BenchmarkMap/Update1/ordered-4 12118083 98.08 ns/op 32 B/op 1 allocs/op
BenchmarkMap/Load1/builtin-4 289113676 4.144 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Load1/sync-4 100000000 11.25 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Load1/ordered-4 26038620 46.19 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Load3/builtin-4 90047526 12.65 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Load3/sync-4 149176874 8.037 ns/op 0 B/op 0 allocs/op
BenchmarkMap/Load3/ordered-4 26861779 44.67 ns/op 0 B/op 0 allocs/op
BenchmarkLoadOrStoreStore/builtin-4 49824517 20.92 ns/op 0 B/op 0 allocs/op
BenchmarkLoadOrStoreStore/sync-4 4937766 244.9 ns/op 376 B/op 8 allocs/op
BenchmarkLoadOrStoreStore/ordered-4 6684468 177.8 ns/op 416 B/op 5 allocs/op
BenchmarkLoadOrStoreLoad/builtin-4 279954810 4.291 ns/op 0 B/op 0 allocs/op
BenchmarkLoadOrStoreLoad/sync-4 23575126 51.09 ns/op 32 B/op 2 allocs/op
BenchmarkLoadOrStoreLoad/ordered-4 19255971 62.83 ns/op 0 B/op 0 allocs/op
BenchmarkStoreThenDelete/builtin-4 40588748 28.97 ns/op 0 B/op 0 allocs/op
BenchmarkStoreThenDelete/sync-4 1878607 633.8 ns/op 357 B/op 8 allocs/op
BenchmarkStoreThenDelete/ordered-4 4875866 244.9 ns/op 79 B/op 1 allocs/op
BenchmarkRange/10/builtin-4 8666966 138.3 ns/op 0 B/op 0 allocs/op
BenchmarkRange/10/sync-4 18859324 62.89 ns/op 0 B/op 0 allocs/op
BenchmarkRange/10/ordered-4 2830831 423.8 ns/op 0 B/op 0 allocs/op
BenchmarkRange/100/builtin-4 934752 1276 ns/op 0 B/op 0 allocs/op
BenchmarkRange/100/sync-4 2148686 560.0 ns/op 0 B/op 0 allocs/op
BenchmarkRange/100/ordered-4 328244 3674 ns/op 0 B/op 0 allocs/op
BenchmarkRange/1000/builtin-4 83199 14432 ns/op 0 B/op 0 allocs/op
BenchmarkRange/1000/sync-4 183529 6375 ns/op 0 B/op 0 allocs/op
BenchmarkRange/1000/ordered-4 33486 35836 ns/op 0 B/op 0 allocs/op
PASS
ok go.yhsif.com/orderedmap 53.852s
Note that for the benchmark tests,
sync and ordered are parallel benchmarks while builtin are sequential.
License
Documentation
¶
Overview ¶
Package orderedmap provides an implementation of ordered map.
An ordered map guarantees that the iteration order preserves the original insertion order. If an existing key is updated later, that doesn't change its iteration order. But if a key was deleted then later inserted again, the iteration order reflects its last insertion order.
Example ¶
package main
import (
"fmt"
"go.yhsif.com/orderedmap"
)
func main() {
var m orderedmap.Map[string, int]
fmt.Println(m.Load("key1"))
fmt.Println(m.LoadOrStore("key1", 1))
fmt.Println(m.LoadOrStore("key1", 2))
m.Store("key2", 2)
fmt.Println(m.Load("key2"))
m.Store("key1", 11)
fmt.Println(m.Load("key1"))
fmt.Println("Range1:")
m.Range(func(k string, v int) bool {
fmt.Println(k, v)
return true
})
m.Delete("key1")
m.Store("key1", 1)
fmt.Println("Range2:")
m.Range(func(k string, v int) bool {
fmt.Println(k, v)
return true
})
}
Output: 0 false 1 false 1 true 2 true 11 true Range1: key1 11 key2 2 Range2: key2 2 key1 1
Index ¶
- type Map
- func (m *Map[K, V]) All() func(yield func(K, V) bool)
- func (m *Map[K, V]) Delete(key K)
- func (m *Map[K, V]) Load(key K) (value V, ok bool)
- func (m *Map[K, V]) LoadAndDelete(key K) (value V, loaded bool)
- func (m *Map[K, V]) LoadOrStore(key K, value V) (actual V, loaded bool)
- func (m *Map[K, V]) Range(f func(key K, value V) bool)
- func (m *Map[K, V]) Store(key K, value V)
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Map ¶
type Map[K comparable, V any] struct { // contains filtered or unexported fields }
Map represents an ordered map.
An ordered map preserves the inserting order when iterating.
Underlying it's wrapping a sync.Map with a doubly linked list.
The interface is intentionally kept almost the same with sync.Map to be used interchangeably.
The zero value is an empty map ready to use. A map must not be copied after first use.
func (*Map[K, V]) Load ¶
Load loads key from the map.
The ok result indicates whether the value is found in the map.
func (*Map[K, V]) LoadAndDelete ¶ added in v0.2.0
LoadAndDelete deletes the value for a key, returning the previous value if any. The loaded result reports whether the key was present.
func (*Map[K, V]) LoadOrStore ¶
LoadOrStore returns the existing value for the key if present. Otherwise, it stores and returns the given value. The loaded result is true if the value was loaded, false if stored.
Source Files