1[](https://pkg.go.dev/github.com/wk8/go-ordered-map/v2)
2[](https://app.circleci.com/pipelines/github/wk8/go-ordered-map)
3
4# Golang Ordered Maps
5
6Same as regular maps, but also remembers the order in which keys were inserted, akin to [Python's `collections.OrderedDict`s](https://docs.python.org/3.7/library/collections.html#ordereddict-objects).
7
8It offers the following features:
9* optimal runtime performance (all operations are constant time)
10* optimal memory usage (only one copy of values, no unnecessary memory allocation)
11* allows iterating from newest or oldest keys indifferently, without memory copy, allowing to `break` the iteration, and in time linear to the number of keys iterated over rather than the total length of the ordered map
12* supports any generic types for both keys and values. If you're running go < 1.18, you can use [version 1](https://github.com/wk8/go-ordered-map/tree/v1) that takes and returns generic `interface{}`s instead of using generics
13* idiomatic API, akin to that of [`container/list`](https://golang.org/pkg/container/list)
14* support for JSON and YAML marshalling
15
16## Documentation
17
18[The full documentation is available on pkg.go.dev](https://pkg.go.dev/github.com/wk8/go-ordered-map/v2).
19
20## Installation
21```bash
22go get -u github.com/wk8/go-ordered-map/v2
23```
24
25Or use your favorite golang vendoring tool!
26
27## Supported go versions
28
29Go >= 1.18 is required to use version >= 2 of this library, as it uses generics.
30
31If you're running go < 1.18, you can use [version 1](https://github.com/wk8/go-ordered-map/tree/v1) instead.
32
33## Example / usage
34
35```go
36package main
37
38import (
39 "fmt"
40
41 "github.com/wk8/go-ordered-map/v2"
42)
43
44func main() {
45 om := orderedmap.New[string, string]()
46
47 om.Set("foo", "bar")
48 om.Set("bar", "baz")
49 om.Set("coucou", "toi")
50
51 fmt.Println(om.Get("foo")) // => "bar", true
52 fmt.Println(om.Get("i dont exist")) // => "", false
53
54 // iterating pairs from oldest to newest:
55 for pair := om.Oldest(); pair != nil; pair = pair.Next() {
56 fmt.Printf("%s => %s\n", pair.Key, pair.Value)
57 } // prints:
58 // foo => bar
59 // bar => baz
60 // coucou => toi
61
62 // iterating over the 2 newest pairs:
63 i := 0
64 for pair := om.Newest(); pair != nil; pair = pair.Prev() {
65 fmt.Printf("%s => %s\n", pair.Key, pair.Value)
66 i++
67 if i >= 2 {
68 break
69 }
70 } // prints:
71 // coucou => toi
72 // bar => baz
73}
74```
75
76An `OrderedMap`'s keys must implement `comparable`, and its values can be anything, for example:
77
78```go
79type myStruct struct {
80 payload string
81}
82
83func main() {
84 om := orderedmap.New[int, *myStruct]()
85
86 om.Set(12, &myStruct{"foo"})
87 om.Set(1, &myStruct{"bar"})
88
89 value, present := om.Get(12)
90 if !present {
91 panic("should be there!")
92 }
93 fmt.Println(value.payload) // => foo
94
95 for pair := om.Oldest(); pair != nil; pair = pair.Next() {
96 fmt.Printf("%d => %s\n", pair.Key, pair.Value.payload)
97 } // prints:
98 // 12 => foo
99 // 1 => bar
100}
101```
102
103Also worth noting that you can provision ordered maps with a capacity hint, as you would do by passing an optional hint to `make(map[K]V, capacity`):
104```go
105om := orderedmap.New[int, *myStruct](28)
106```
107
108You can also pass in some initial data to store in the map:
109```go
110om := orderedmap.New[int, string](orderedmap.WithInitialData[int, string](
111 orderedmap.Pair[int, string]{
112 Key: 12,
113 Value: "foo",
114 },
115 orderedmap.Pair[int, string]{
116 Key: 28,
117 Value: "bar",
118 },
119))
120```
121
122`OrderedMap`s also support JSON serialization/deserialization, and preserves order:
123
124```go
125// serialization
126data, err := json.Marshal(om)
127...
128
129// deserialization
130om := orderedmap.New[string, string]() // or orderedmap.New[int, any](), or any type you expect
131err := json.Unmarshal(data, &om)
132...
133```
134
135Similarly, it also supports YAML serialization/deserialization using the yaml.v3 package, which also preserves order:
136
137```go
138// serialization
139data, err := yaml.Marshal(om)
140...
141
142// deserialization
143om := orderedmap.New[string, string]() // or orderedmap.New[int, any](), or any type you expect
144err := yaml.Unmarshal(data, &om)
145...
146```
147
148## Alternatives
149
150There are several other ordered map golang implementations out there, but I believe that at the time of writing none of them offer the same functionality as this library; more specifically:
151* [iancoleman/orderedmap](https://github.com/iancoleman/orderedmap) only accepts `string` keys, its `Delete` operations are linear
152* [cevaris/ordered_map](https://github.com/cevaris/ordered_map) uses a channel for iterations, and leaks goroutines if the iteration is interrupted before fully traversing the map
153* [mantyr/iterator](https://github.com/mantyr/iterator) also uses a channel for iterations, and its `Delete` operations are linear
154* [samdolan/go-ordered-map](https://github.com/samdolan/go-ordered-map) adds unnecessary locking (users should add their own locking instead if they need it), its `Delete` and `Get` operations are linear, iterations trigger a linear memory allocation