README
¶
📚 sortedmap
sortedmap provides an effective sorted map implementation for Go.
It uses a heap to maintain order and iterators under the hood.
Features
- 🚀 Efficient sorted map implementation
- 🔧 Customizable sorting by key or value
- 🐈 Zero dependencies
- 📦 Easy to use API (inspired by the stdlib
mapsandslicespackages)
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 map with the same contents as the SortedMap |
O(n log n) |
Benchmarks
goos: darwin
goarch: arm64
pkg: github.com/egregors/sortedmap
cpu: Apple M1 Max
BenchmarkNew-10 165633163 7.143 ns/op
BenchmarkNewFromMap-10 406633 2806 ns/op
BenchmarkSortedMap_Get-10 154206174 7.849 ns/op
BenchmarkSortedMap_All-10 1000000000 0.3153 ns/op
BenchmarkSortedMap_Collect-10 627693 1929 ns/op
BenchmarkSortedMap_Keys-10 1000000000 0.3150 ns/op
BenchmarkSortedMap_Values-10 1000000000 0.3233 ns/op
BenchmarkSortedMap_Insert-10 6625201 182.0 ns/op
BenchmarkSortedMap_Delete-10 3301149 373.4 ns/op
PASS
License
This project is licensed under the MIT License. See the LICENSE file for details.
Documentation
¶
Index ¶
- type KV
- type SortedMap
- func (sm *SortedMap[Map, K, V]) All() iter.Seq2[K, V]
- func (sm *SortedMap[Map, K, V]) Collect() Map
- func (sm *SortedMap[Map, K, V]) Delete(key K) (val *V, existed bool)
- func (sm *SortedMap[Map, K, V]) Get(key K) (V, bool)
- func (sm *SortedMap[Map, K, V]) Insert(key K, val V)
- func (sm *SortedMap[Map, K, V]) Keys() iter.Seq[K]
- func (sm *SortedMap[Map, K, V]) Values() iter.Seq[V]
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 }
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)
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).
func (*SortedMap[Map, K, V]) Collect ¶
func (sm *SortedMap[Map, K, V]) Collect() Map
Collect returns a map with the same contents as the SortedMap
func (*SortedMap[Map, K, V]) Delete ¶
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)
func (*SortedMap[Map, K, V]) Get ¶
Get returns the value associated with the key and a boolean indicating if the key exists in the map The complexity is O(1)
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.
Source Files