README

PkgGoDev Go Report Card

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 sync.Map and a doubly linked list. The interface is intentionally kept the same with sync.Map to be used interchangeably.

Benchmark

This package comes with benchmark test to test against builtin map and sync.Map:

$ go test -bench . -benchmem
goos: linux
goarch: amd64
pkg: go.yhsif.com/orderedmap
BenchmarkMap/DeleteEmpty/builtin-4              96833191                12.1 ns/op             0 B/op          0 allocs/op
BenchmarkMap/DeleteEmpty/sync-4                 79389284                15.0 ns/op             0 B/op          0 allocs/op
BenchmarkMap/DeleteEmpty/ordered-4              66165724                18.0 ns/op             0 B/op          0 allocs/op
BenchmarkMap/LoadEmpty/builtin-4                98423847                12.1 ns/op             0 B/op          0 allocs/op
BenchmarkMap/LoadEmpty/sync-4                   77803774                15.3 ns/op             0 B/op          0 allocs/op
BenchmarkMap/LoadEmpty/ordered-4                66868016                17.9 ns/op             0 B/op          0 allocs/op
BenchmarkMap/Store1/builtin-4                   13271734                88.9 ns/op            32 B/op          2 allocs/op
BenchmarkMap/Store1/sync-4                       7618335               157 ns/op              48 B/op          3 allocs/op
BenchmarkMap/Store1/ordered-4                    9210949               129 ns/op              64 B/op          3 allocs/op
BenchmarkMap/Store2/builtin-4                   12802537                94.4 ns/op            32 B/op          2 allocs/op
BenchmarkMap/Store2/sync-4                       7385720               162 ns/op              48 B/op          3 allocs/op
BenchmarkMap/Store2/ordered-4                    9084321               131 ns/op              64 B/op          3 allocs/op
BenchmarkMap/Update1/builtin-4                  13431109                89.5 ns/op            32 B/op          2 allocs/op
BenchmarkMap/Update1/sync-4                      7723395               156 ns/op              48 B/op          3 allocs/op
BenchmarkMap/Update1/ordered-4                   9167068               129 ns/op              64 B/op          3 allocs/op
BenchmarkMap/Load1/builtin-4                    44437922                26.9 ns/op             0 B/op          0 allocs/op
BenchmarkMap/Load1/sync-4                       38100231                31.4 ns/op             0 B/op          0 allocs/op
BenchmarkMap/Load1/ordered-4                    29717439                40.3 ns/op             0 B/op          0 allocs/op
BenchmarkMap/Load3/builtin-4                    76247488                15.6 ns/op             0 B/op          0 allocs/op
BenchmarkMap/Load3/sync-4                       59924874                20.0 ns/op             0 B/op          0 allocs/op
BenchmarkMap/Load3/ordered-4                    34028864                35.2 ns/op             0 B/op          0 allocs/op
BenchmarkLoadOrStoreStore/builtin-4             11663713               103 ns/op              32 B/op          2 allocs/op
BenchmarkLoadOrStoreStore/sync-4                 2815587               426 ns/op             376 B/op          8 allocs/op
BenchmarkLoadOrStoreStore/ordered-4              2138095               560 ns/op             520 B/op         11 allocs/op
BenchmarkLoadOrStoreLoad/builtin-4              14577663                81.9 ns/op            32 B/op          2 allocs/op
BenchmarkLoadOrStoreLoad/sync-4                 12393217                95.9 ns/op            32 B/op          2 allocs/op
BenchmarkLoadOrStoreLoad/ordered-4              12630664                94.0 ns/op            32 B/op          2 allocs/op
BenchmarkStoreThenDelete/builtin-4               9594682               126 ns/op              32 B/op          2 allocs/op
BenchmarkStoreThenDelete/sync-4                  2062261               580 ns/op             360 B/op          9 allocs/op
BenchmarkStoreThenDelete/ordered-4               1765857               680 ns/op             440 B/op         11 allocs/op
BenchmarkRange/10/builtin-4                      8392304               142 ns/op               0 B/op          0 allocs/op
BenchmarkRange/10/sync-4                         7705442               155 ns/op               0 B/op          0 allocs/op
BenchmarkRange/10/ordered-4                     34963722                34.2 ns/op             0 B/op          0 allocs/op
BenchmarkRange/100/builtin-4                      859714              1377 ns/op               0 B/op          0 allocs/op
BenchmarkRange/100/sync-4                         827470              1439 ns/op               0 B/op          0 allocs/op
BenchmarkRange/100/ordered-4                     3568192               337 ns/op               0 B/op          0 allocs/op
BenchmarkRange/1000/builtin-4                      77983             15334 ns/op               0 B/op          0 allocs/op
BenchmarkRange/1000/sync-4                         72570             16524 ns/op               0 B/op          0 allocs/op
BenchmarkRange/1000/ordered-4                     354681              3372 ns/op               0 B/op          0 allocs/op
PASS
ok      go.yhsif.com/orderedmap 51.884s

As you can see, all operations except Range are on-par or only slightly slower than sync.Map, while Range is a lot faster.

License

BSD 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
    Output:
    
    <nil> false
    value1 false
    value1 true
    value2 true
    new value1 true
    Range1:
    key1 new value1
    key2 value2
    Range2:
    key2 value2
    key1 value1
    

    Index

    Examples

    Constants

    This section is empty.

    Variables

    This section is empty.

    Functions

    This section is empty.

    Types

    type Interface

    type Interface interface {
    	Delete(key interface{})
    	Load(key interface{}) (value interface{}, ok bool)
    	LoadAndDelete(key interface{}) (value interface{}, loaded bool)
    	LoadOrStore(key, value interface{}) (actual interface{}, loaded bool)
    	Range(f func(key, value interface{}) bool)
    	Store(key, value interface{})
    }

      Interface defines the common interface between orderedmap.Map and sync.Map.

      type Map

      type Map 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 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) Delete

        func (m *Map) Delete(key interface{})

          Delete deletes key from the map.

          key must be hashable.

          func (*Map) Load

          func (m *Map) Load(key interface{}) (value interface{}, ok bool)

            Load loads key from the map.

            key must be hashable.

            The ok result indicates whether the value is found in the map.

            func (*Map) LoadAndDelete

            func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool)

              LoadAndDelete deletes the value for a key, returning the previous value if any. The loaded result reports whether the key was present.

              func (*Map) LoadOrStore

              func (m *Map) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool)

                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.

                key must be hashable.

                func (*Map) Range

                func (m *Map) Range(f func(key, value interface{}) bool)

                  Range calls f sequentially for each key and value present in the map. If f returns false, range stops the iteration.

                  The order of the iteration preserves the original insertion order.

                  func (*Map) Store

                  func (m *Map) Store(key, value interface{})

                    Store stores the key value pair into the map.

                    key must be hashable.