orderedmap

An *OrderedMap is a high-performance ordered map that maintains amortized O(1) complexity for Set, Get, Delete, and Len. It is implemented using a standard Go map combined with a trimmed-down linked list to preserve insertion order.

Version Compatibility:

• v3: Requires Go v1.23+.
• v2: Requires Go v1.18+ (for generics support).
• v1: Supports Go v1.17 and below.

import "github.com/elliotchance/orderedmap/v3"

func main() {
	m := orderedmap.NewOrderedMap[string, any]()

	m.Set("foo", "bar")
	m.Set("qux", 1.23)
	m.Set("123", true)

	m.Delete("qux")
}

You can use the standard library slices and maps packages to convert the iterators provided by OrderedMap into other data structures.

• Use slices.Collect() with Keys() or Values() to get a slice of keys or values.
• Use maps.Collect() with AllFromFront() to create a standard unordered Go map from the ordered map.

// Get a slice of keys
fmt.Println(slices.Collect(m.Keys()))
// [A B C]

// Create a regular unordered map from the ordered one
fmt.Println(maps.Collect(m.AllFromFront()))
// [A:1 B:2 C:3]

If you prefer not to use Go iterators, you can manually traverse the map using the linked-list style methods. This involves using Front() or Back() to get the starting element, and then calling .Next() or .Prev() on the element to move through the map.

• Front(): Returns the oldest element.
• Back(): Returns the newest element.
• Next(): Moves to the next element in forward order.
• Prev(): Moves to the previous element in reverse order.

// Iterate through all elements from oldest to newest:
for el := m.Front(); el != nil; el = el.Next() {
    fmt.Println(el.Key, el.Value)
}

// Iterate in reverse:
for el := m.Back(); el != nil; el = el.Prev() {
    fmt.Println(el.Key, el.Value)
}

The *OrderedMap provides several methods that return standard Go iterators, allowing you to use the range keyword to loop over elements.

Available Iterator Methods:

• AllFromFront(): Iterates from oldest to newest.
• AllFromBack(): Iterates from newest to oldest.
• Keys(): Iterates over the keys.
• Values(): Iterates over the values.

Important Notes:

• Iterators are safe to use bidirectionally and return nil once they exceed the bounds of the map.
• Concurrency Warning: If the map is modified while an iteration is in-flight, it may produce unexpected behavior.

// Iterate through all elements from oldest to newest:
for key, value := range m.AllFromFront() {
	fmt.Println(key, value)
}

Use the ReverseIterator() method to obtain an iter.Seq2[K, V] that allows you to traverse the map elements in reverse order (from the most recently inserted to the oldest). This method is compatible with Go 1.23+ for...range loops over functions.

for key, value := range m.ReverseIterator() {
	// process key and value in reverse order
}

Delete(key) removes the specified key and its associated value from the map. It returns true if the key existed and was removed, or false if the key was not found.

m := orderedmap.NewOrderedMap()
m.Set("key", "value")

removed := m.Delete("key") // returns true
missing := m.Delete("non-existent") // returns false

The Copy() method creates a new OrderedMap containing the same elements in the same order as the original.

Warning: Using Copy() while there are concurrent writes to the original map may result in a mangled or inconsistent result. Ensure synchronization if the map is being modified in other goroutines.

m2 := m.Copy()

You can create a new OrderedMap using several constructor functions depending on your needs:

• NewOrderedMap[K, V](): Creates a new empty map.
• NewOrderedMapWithCapacity[K, V](capacity int): Creates a map with pre-allocated space for the specified number of elements to improve performance.
• NewOrderedMapWithElements[K, V](els ...*Element[K, V]): Creates a map initialized with a provided slice of *Element pointers.

// Basic initialization
om := orderedmap.NewOrderedMap[string, int]()

// Initialization with capacity
omWithCap := orderedmap.NewOrderedMapWithCapacity[string, int](10)

The OrderedMap provides several iterators compatible with Go 1.23+ iter.Seq patterns. Iteration follows the insertion order (oldest to newest) unless using the Back variant.

• AllFromFront() iter.Seq2[K, V]: Yields all key-value pairs from oldest to newest.
• AllFromBack() iter.Seq2[K, V]: Yields all key-value pairs from newest to oldest.
• Keys() iter.Seq[K]: Yields all keys from oldest to newest.
• Values() iter.Seq[V]: Yields all values from oldest to newest.

To collect results into a slice, use slices.Collect from the standard library.

import (
	"fmt"
	"slices"
	"github.com/elliotchance/elliotchance/orderedmap/v3"
)

m := orderedmap.NewOrderedMap[string, int]()
m.Set("a", 1)
m.Set("b", 2)

// Iterate over all key-value pairs
for k, v := range m.AllFromFront() {
	fmt.Printf("%s: %d\n", k, v)
}

// Collect keys into a slice
keys := slices.Collect(m.Keys())

Use these methods to inspect the map's structure and size:

• Len() int: Returns the number of elements currently in the map.
• Front() *Element[K, V]: Returns the oldest element (the first one inserted).
• Back() *Element[K, V]: Returns the newest element (the most recent one inserted).
• GetElement(key K) *Element[K, V]: Returns the underlying *Element for a key. Returns nil if the key is not found. This is useful if you need to perform manual list operations via the element pointer.

m := orderedmap.NewOrderedMap[string, int]()
m.Set("first", 1)
m.Set("last", 2)

fmt.Println("Size:", m.Len())
fmt.Println("Oldest key:", m.Front().Key)
fmt.Println("Newest key:", m.Back().Key)

// Get the raw element
elem := m.GetElement("first")

Since this is an ordered map, you can access elements in their insertion order:

• Keys() []K: Returns a slice of all keys in the order they were inserted.
• Front() *Element[K, V]: Returns the first (oldest) element.
• Back() *Element[K, V]: Returns the last (most recent) element.
• GetElement(key K) *Element[K, V]: Returns the underlying *Element for a key, or nil if not found. This is useful for manual iteration using element.Next().

om := orderedmap.NewOrderedMap[string, int]()
om.Set("first", 1)
om.Set("second", 2)

// Get all keys in order
keys := om.Keys()

// Manual iteration via elements
for el := om.Front(); el != nil; el = el.Next() {
    fmt.Printf("Key: %v, Value: %v\n", el.Key, el.Value)
}

Use these methods to inspect the state of the map:

• Len() int: Returns the number of elements currently in the map.
• Has(key K) bool: Returns true if the key exists in the map.

if om.Has("apple") {
    fmt.Printf("Map size: %d\n", om.Len())
}