Go ordered map

Go implementation of an ordered map using generics.

Implementation

An ordered map is a map that additionally maintains ordering among its entries. This data structure can be used to solve a variety of problems: one very common use case is implementing LRU or LRU-like cache replacement policies.

This implementation supports O(1) lookup, update, removal, insertion to front/back, insertion before/after a specific key, move to front/back, move before/after a specific key.

Under the hood this is implemented as a combination of a map and doubly-linked list, whereby each value in the map is node of the list. The list is implemented by forking the standard library container/list package and adding support for generics.

This implementation is not safe for concurrent usage.

Installation

You can get this module by invoking from your terminal

go get -u github.com/lorenzosaino/go-orderedmap

and then importing it in your code with

import orderedmap "github.com/lorenzosaino/go-orderedmap"

Since it requires generics support, you will need Go 1.18 or above.

Usage

For reference and examples, see Go doc.

Development

You can invoke make help to see all make targets provided.

$ make help
all                            Run all checks and tests
mod-upgrade                    Upgrade all vendored dependencies
mod-update                     Ensure all used dependencies are tracked in go.{mod|sum} and vendored
fmt-check                      Validate that all source files pass "go fmt"
lint                           Run go lint
vet                            Run go vet
staticcheck                    Run staticcheck
test                           Run all tests
container-shell                Open a shell on a Docker container
container-%                    Run any target of this Makefile in a Docker container
help                           Print help

License

BSD 3-clause