sortedmap

package module
v0.3.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Mar 26, 2025 License: MIT Imports: 2 Imported by: 0

README

📚 sortedmap

sortedmap provides an effective sorted map implementation for Go. It uses a heap to maintain order and iterators under the hood.

Build Status Go Report Card Coverage Status godoc

Features

  • 🚀 Efficient sorted map implementation
  • 🔧 Customizable sorting by key or value
  • 🐈 Zero dependencies
  • 📦 Easy to use API (inspired by the stdlib maps and slices packages)

Installation

To install the package, run:

go get github.com/egregors/sortedmap

Usage

Here's a quick example of how to use the sortedmap package:

package main

import (
	"fmt"

	sm "github.com/egregors/sortedmap"
)

type Person struct {
	Name string
	Age  int
}

func main() {
	// Create a new map sorted by keys
	m := sm.NewFromMap(map[string]int{
		"Bob":   31,
		"Alice": 26,
		"Eve":   84,
	}, func(i, j sm.KV[string, int]) bool {
		return i.Key < j.Key
	})

	fmt.Println(m.Collect())
	// Output: map[Alice:26 Bob:31 Eve:84]

	m.Insert("Charlie", 34)
	fmt.Println(m.Collect())
	// Output: map[Alice:26 Bob:31 Charlie:34 Eve:84]

	m.Delete("Bob")
	fmt.Println(m.Collect())
	// Output: map[Alice:26 Charlie:34 Eve:84]

	// Create a new map sorted by values
	m2 := sm.NewFromMap(map[string]Person{
		"Bob":   {"Bob", 31},
		"Alice": {"Alice", 26},
		"Eve":   {"Eve", 84},
	}, func(i, j sm.KV[string, Person]) bool {
		return i.Val.Age < j.Val.Age
	})

	fmt.Println(m2.Collect())
	// Output: map[Alice:{Alice 26} Bob:{Bob 31} Eve:{Eve 84}]

	// Create a new map sorted by values but if the values are equal, sort by keys
	m3 := sm.NewFromMap(map[string]Person{
		"Bob":   {"Bob", 26},
		"Alice": {"Alice", 26},
		"Eve":   {"Eve", 84},
	}, func(i, j sm.KV[string, Person]) bool {
		if i.Val.Age == j.Val.Age {
			return i.Key < j.Key
		}

		return i.Val.Age < j.Val.Age
	})

	fmt.Println(m3.Collect())
	// Output: map[Alice:{Alice 26} Bob:{Bob 26} Eve:{Eve 84}]
}

API and Complexity

Method Description Complexity
New Creates a new SortedMap with a comparison function O(1)
NewFromMap Creates a new SortedMap from an existing map with a comparison O(n log n)
Get Retrieves the value associated with a key O(1)
Delete Removes a key-value pair from the map O(n)
All Returns a sequence of all key-value pairs in the map O(n log n)
Keys Returns a sequence of all keys in the map O(n log n)
Values Returns a sequence of all values in the map O(n log n)
Insert Adds or updates a key-value pair in the map O(log n)
Collect Returns a regular map with an unordered content off the SortedMap O(n log n)
CollectAll Returns a slice of key-value pairs O(n log n)
CollectKeys Returns a slice of the map’s keys O(n log n)
CollectValues Returns a slice of the map's values O(n log n)
Len Returns length of underlying map O(1)

Benchmarks

BenchmarkNew-10                         165887913           7.037 ns/op
BenchmarkNewFromMap-10                  419106              2716 ns/op
BenchmarkSortedMap_Get-10               191580795           5.327 ns/op
BenchmarkSortedMap_Delete-10            3328420             365.0 ns/op
BenchmarkSortedMap_All-10               1000000000          0.3116 ns/op
BenchmarkSortedMap_Keys-10              1000000000          0.3118 ns/op
BenchmarkSortedMap_Values-10            1000000000          0.3117 ns/op
BenchmarkSortedMap_Insert-10            6665839             182.5 ns/op
BenchmarkSortedMap_Collect-10           649450              1835 ns/op
BenchmarkSortedMap_CollectAll-10        1237276             972.4 ns/op
BenchmarkSortedMap_CollectKeys-10       1250041             964.9 ns/op
BenchmarkSortedMap_CollectValues-10     1294760             927.7 ns/op
BenchmarkSortedMap_Len-10               1000000000          0.3176 ns/op

License

This project is licensed under the MIT License. See the LICENSE file for details.

Documentation

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type KV 

type KV[K comparable, V any] struct {
	Key K
	Val V
}

KV is a key-value pair.

type SortedMap 

type SortedMap[Map ~map[K]V, K comparable, V any] struct {
	// contains filtered or unexported fields
}

SortedMap is a map-like struct that keeps sorted by key or value. It uses a heap to maintain the order.

func New 

func New[Map ~map[K]V, K comparable, V any](less func(i, j KV[K, V]) bool) *SortedMap[Map, K, V]

New creates a new SortedMap with `less` as the comparison function The complexity is O(1)

Example 
sm := New[map[string]int, string, int](func(i, j KV[string, int]) bool {
	return i.Key < j.Key
})
sm.Insert("Alice", 30)
sm.Insert("Bob", 42)
for k, v := range sm.All() {
	fmt.Println(k, v)
}

Output:

Alice 30
Bob 42

func NewFromMap 

func NewFromMap[Map ~map[K]V, K comparable, V any](m Map, less func(i, j KV[K, V]) bool) *SortedMap[Map, K, V]

NewFromMap creates a new SortedMap with `less` as the comparison function and populates it with the contents of `m`. The complexity is O(n log n) where n = len(m).

Example 
sm := NewFromMap(map[string]int{
	"Bob":     42,
	"Alice":   30,
	"Charlie": 25,
}, func(i, j KV[string, int]) bool {
	return i.Key < j.Key
})
for k, v := range sm.All() {
	fmt.Println(k, v)
}

Output:

Alice 30
Bob 42
Charlie 25

func (*SortedMap[Map, K, V]) All 

func (sm *SortedMap[Map, K, V]) All() iter.Seq2[K, V]

All returns a sequence of key-value pairs

Example 
sm := NewFromMap(map[string]int{
	"Bob":     42,
	"Alice":   30,
	"Charlie": 25,
}, func(i, j KV[string, int]) bool {
	return i.Key < j.Key
})
for k, v := range sm.All() {
	fmt.Println(k, v)
}

Output:

Alice 30
Bob 42
Charlie 25

func (*SortedMap[Map, K, V]) Collect 

func (sm *SortedMap[Map, K, V]) Collect() Map

Collect returns a regular map with an *unordered* content off the SortedMap

Example 
sm := NewFromMap(map[string]int{
	"Bob":     42,
	"Alice":   30,
	"Charlie": 25,
}, func(i, j KV[string, int]) bool {
	return i.Key < j.Key
})
fmt.Println(sm.Collect())

Output:

map[Alice:30 Bob:42 Charlie:25]

func (*SortedMap[Map, K, V]) CollectAll added in v0.3.0 

func (sm *SortedMap[Map, K, V]) CollectAll() []KV[K, V]

CollectAll returns a slice of key-value pairs

Example 
sm := NewFromMap(map[int]string{
	1: "one",
	3: "three",
	2: "two",
	5: "five",
	4: "four",
}, func(i, j KV[int, string]) bool {
	return i.Key < j.Key
})
fmt.Println(sm.CollectAll())

Output:

[{1 one} {2 two} {3 three} {4 four} {5 five}]

func (*SortedMap[Map, K, V]) CollectKeys added in v0.3.0 

func (sm *SortedMap[Map, K, V]) CollectKeys() []K

CollectKeys returns a slice of the map’s keys

Example 
sm := NewFromMap(map[string]int{
	"Bob":     42,
	"Alice":   30,
	"Charlie": 25,
}, func(i, j KV[string, int]) bool {
	return i.Key < j.Key
})
fmt.Println(sm.CollectKeys())

Output:

[Alice Bob Charlie]

func (*SortedMap[Map, K, V]) CollectValues added in v0.3.0 

func (sm *SortedMap[Map, K, V]) CollectValues() []V

CollectValues returns a slice of the map's values

Example 
sm := NewFromMap(map[string]int{
	"Bob":     42,
	"Alice":   30,
	"Charlie": 25,
}, func(i, j KV[string, int]) bool {
	return i.Key < j.Key
})
fmt.Println(sm.CollectValues())

Output:

[30 42 25]

func (*SortedMap[Map, K, V]) Delete 

func (sm *SortedMap[Map, K, V]) Delete(key K) (val *V, existed bool)

Delete removes the key from the map and returns the value associated with the key and a boolean indicating if the key existed in the map. The complexity is O(n) where n = len(sm.h.xs)

Example 
sm := NewFromMap(map[string]int{
	"Bob":     42,
	"Alice":   30,
	"Charlie": 25,
}, func(i, j KV[string, int]) bool {
	return i.Key < j.Key
})
val, ok := sm.Delete("Alice")
fmt.Println(ptrVal(val), ok)
val, ok = sm.Delete("Alice")
fmt.Println(ptrVal(val), ok)

Output:

30 true
0 false

func (*SortedMap[Map, K, V]) Get 

func (sm *SortedMap[Map, K, V]) Get(key K) (V, bool)

Get returns the value associated with the key and a boolean indicating if the key exists in the map The complexity is O(1)

Example 
sm := NewFromMap(map[string]int{
	"Bob":     42,
	"Alice":   30,
	"Charlie": 25,
}, func(i, j KV[string, int]) bool {
	return i.Key < j.Key
})
val, ok := sm.Get("Alice")
fmt.Println(val, ok)

Output:

30 true

func (*SortedMap[Map, K, V]) Insert 

func (sm *SortedMap[Map, K, V]) Insert(key K, val V)

Insert adds a key-value pair to the map. If the key already exists, the value is updated

Example 
sm := New[map[string]int, string, int](func(i, j KV[string, int]) bool {
	return i.Key < j.Key
})
sm.Insert("Alice", 30)
sm.Insert("Bob", 42)
for k, v := range sm.All() {
	fmt.Println(k, v)
}

Output:

Alice 30
Bob 42

func (*SortedMap[Map, K, V]) Keys 

func (sm *SortedMap[Map, K, V]) Keys() iter.Seq[K]

Keys returns a sequence of keys

Example 
sm := NewFromMap(map[string]int{
	"Bob":     42,
	"Alice":   30,
	"Charlie": 25,
}, func(i, j KV[string, int]) bool {
	return i.Key < j.Key
})
for k := range sm.Keys() {
	fmt.Println(k)
}

Output:

Alice
Bob
Charlie

func (*SortedMap[Map, K, V]) Len added in v0.2.0 

func (sm *SortedMap[Map, K, V]) Len() int

Len returns length of underlying map

func (*SortedMap[Map, K, V]) Values 

func (sm *SortedMap[Map, K, V]) Values() iter.Seq[V]

Values returns a sequence of values

Example 
sm := NewFromMap(map[string]int{
	"Bob":     42,
	"Alice":   30,
	"Charlie": 25,
}, func(i, j KV[string, int]) bool {
	return i.Key < j.Key
})
for v := range sm.Values() {
	fmt.Println(v)
}

Output:

30
42
25

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.