Optimal implementation of ordered maps for Golang - ie maps that remember the order in which keys were inserted.

Overview

Build Status

Goland Ordered Maps

Same as regular maps, but also remembers the order in which keys were inserted, akin to Python's collections.OrderedDicts.

It offers the following features:

  • optimal runtime performance (all operations are constant time)
  • optimal memory usage (only one copy of values, no unnecessary memory allocation)
  • 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
  • takes and returns generic interface{}s
  • idiomatic API, akin to that of container/list

Installation

go get -u github.com/wk8/go-ordered-map

Or use your favorite golang vendoring tool!

Documentation

The full documentation is available on godoc.org.

Example / usage

package main

import (
	"fmt"

	"github.com/wk8/go-ordered-map"
)

func main() {
	om := orderedmap.New()

	om.Set("foo", "bar")
	om.Set("bar", "baz")
	om.Set("coucou", "toi")

	fmt.Println(om.Get("foo"))          // => bar, true
	fmt.Println(om.Get("i dont exist")) // => <nil>, false

	// iterating pairs from oldest to newest:
	for pair := om.Oldest(); pair != nil; pair = pair.Next() {
		fmt.Printf("%s => %s\n", pair.Key, pair.Value)
	} // prints:
	// foo => bar
	// bar => baz
	// coucou => toi

	// iterating over the 2 newest pairs:
	i := 0
	for pair := om.Newest(); pair != nil; pair = pair.Prev() {
		fmt.Printf("%s => %s\n", pair.Key, pair.Value)
		i++
		if i >= 2 {
			break
		}
	} // prints:
	// coucou => toi
	// bar => baz
}

All of OrderedMap's methods accept and return interface{}s, so you can use any type of keys that regular maps accept, as well pack/unpack arbitrary values, e.g.:

type myStruct struct {
	payload string
}

func main() {
	om := orderedmap.New()

	om.Set(12, &myStruct{"foo"})
	om.Set(1, &myStruct{"bar"})

	value, present := om.Get(12)
	if !present {
		panic("should be there!")
	}
	fmt.Println(value.(*myStruct).payload) // => foo

	for pair := om.Oldest(); pair != nil; pair = pair.Next() {
		fmt.Printf("%d => %s\n", pair.Key, pair.Value.(*myStruct).payload)
	} // prints:
	// 12 => foo
	// 1 => bar
}

Alternatives

There 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:

  • iancoleman/orderedmap only accepts string keys, its Delete operations are linear
  • cevaris/ordered_map uses a channel for iterations, and leaks goroutines if the iteration is interrupted before fully traversing the map
  • mantyr/iterator also uses a channel for iterations, and its Delete operations are linear
  • 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
Issues
  • Please bump v0.2.0 tag

    Please bump v0.2.0 tag

    Hi, Could you release a new tag please? go get -u github.com/wk8/go-ordered-map does not update, I had to specify the master branch go get -u github.com/wk8/[email protected] in order to update :-) like v0.2.0

    Thank you!

    opened by SVilgelm 6
  • Feature request

    Feature request

    Can you add a set function or an option in New() with a LRU type feature, where the order is maintained as per update?

    I understand it's not the way an ordered map works but I am requesting an added functionality. OrderedMap where the order can be defined on update also rather than only on creation.

    It's not an issue but a feature request. I can add the desired piece of code.

    opened by shubham2508 3
  • Add alias function Load and Store, Expose Move function from list.List

    Add alias function Load and Store, Expose Move function from list.List

    1. Add alias function Load and Store sync.Map uses Load/Store but this uses Get() and Set(), so I added alias to make the API more consistency.

    2. Expose Move* function from list.List so that users cam move the order of the element in orderedMap directly.

    	om := New()
    	om.Set("1", "bar")
    	om.Set(2, 28)
    	om.Set(3, 100)
    	om.Set("4", "baz")
    	om.Set(5, "28")
    	om.Set(6, "100")
    	om.Set("7", "baz")
    	om.Set("8", "baz")
    
    	om.MoveAfter(2, 3)
    	om.MoveBefore(6, "4")
            om.MoveToBack(3)
    	om.MoveToFront(5)
    
    opened by KusakabeShi 2
Releases(v2.0.0)
Owner
Jean Rougé
Jean Rougé
subtraction operations and also parentheses to indicate order of operations

basic parsing expose a Calculate method that accepts a string of addition / subtraction operations and also parentheses to indicate order of operation

Michael Street 0 Feb 22, 2022
Golang: unify nil and empty slices and maps

unifynil, unify nil and empty slices and maps in Golang Empty slices and maps can be nil or not nil in Go. It may become a nightmare in tests and JSON

Boris Nagaev 0 Jan 16, 2022
A Go package for checking conditions for slices and maps.

check Go package The check package of Go helps one to check various conditions for slices: []int []float64 []string []bool maps: map[string]int map[st

null 4 Feb 3, 2022
Create deep copies (clones) of your maps and slices without using reflection.

DeepCopy DeepCopy helps you create deep copies (clones) of your maps and slices. Create deep copies (clones) of your objects The package is based on t

null 3 Apr 12, 2022
Access and modify property values in deeply nested maps, using dot-separated paths

Dig lets you access and modify property values in deeply nested, unstructured maps, using dot-separated paths: source := make(map[string]interface{})

Preslav Rachev 12 May 7, 2022
Automatically creates & tiles .tmx format maps from a world map interface

Autotile Create tiled maps for an arbitrarily large world space from a simple interface, then add larger objects randomly with simple rules (eg. place

null 0 Jan 9, 2022
🍕 Enjoy a slice! A utility library for dealing with slices and maps that focuses on type safety and performance.

?? github.com/elliotchance/pie Enjoy a slice! pie is a library of utility functions for common operations on slices and maps. Quick Start FAQ What are

Elliot Chance 1k Jun 18, 2022
yaml-patch is a version of Evan Phoenix's json-patch, which is an implementation of JSON Patch, directly transposed to YAML

yaml-patch yaml-patch is a version of Evan Phoenix's json-patch, which is an implementation of JavaScript Object Notation (JSON) Patch, directly trans

Steve Coffman 0 Jan 15, 2022
Goridge is high performance PHP-to-Golang codec library which works over native PHP sockets and Golang net/rpc package.

Goridge is high performance PHP-to-Golang codec library which works over native PHP sockets and Golang net/rpc package. The library allows you to call Go service methods from PHP with a minimal footprint, structures and []byte support.

Spiral Scout 1.1k Jun 24, 2022
A lib of golang which contains many funny api;

A lib of golang which contains many funny api; I created it cause I could not find these more-effient apis from other repo.

acehinnnqru 1 Oct 27, 2021
Cpu-profiling - Basic example of CPU Profiling in Golang which shows the bottlenecks and how much time is spent per function

cpu-profiling Basic example of CPU Profiling in Golang which shows the bottlenec

Felipe Azevedo 0 Jan 4, 2022
Flock is a project which provides a Go solution for system level file locks for all platforms Golang supports.

Flock is a project which provides a Go solution for system level file locks for all platforms Golang supports.

Ken Sipe 0 Feb 8, 2022
This is a Pub/Sub for the Watermill project which uses the Bolt database.

Watermill Bolt Pub/Sub This is a Pub/Sub for the Watermill project which uses the Bolt database.

Three Dots Labs 6 Jun 13, 2022
Simple go package which converts roman strings to integer

romanparse Simple go package which converts roman strings

Caio Ribeiro Pereira 2 Oct 6, 2021
Utility to restrict which package is allowed to import another package.

go-import-rules Utility to restrict which package is allowed to import another package. This tool will read import-rules.yaml or import-rules.yml in t

PAYFAZZ 0 Jan 7, 2022
ms - 'my story' creates a secure password string which can be memorized with a technique shared by Max.

On 23.12.21 20:22, Stefan Claas wrote: [...] > > Yes, I am aware of that, but how can one memorize a key when traveling > and not taking any devices

Stefan Claas 0 Dec 24, 2021
Lightweight, Simple, Quick, Thread-Safe Golang Stack Implementation

stack Lightweight, Simple, Quick, Thread-Safe Golang Stack Implementation Purpose Provide a fast, thread safe, and generic Golang Stack API with minim

Brendan Wilson 5 May 3, 2022
Sliding window counters Redis rate limiting implementation for Golang

Sliding window counters Redis rate limiting implementation for Golang (Based on the Figma API rate limit algorithm)

Barnaby Keene 5 Apr 4, 2022
A pure Golang implementation of Rockchip rknand vendor storage interface.

go-rkvendorstorage A pure Golang implementation of Rockchip rknand vendor storage interface. Usage package main import ( "fmt" "github.com/jamesits

James Swineson 3 May 31, 2022