GitHub - igrmk/treemap: Generic sorted map for Go with red-black tree under the hood (original) (raw)

TreeMap v2

TreeMap is a generic key-sorted map using a red-black tree under the hood. It requires and relies on Go 1.18 generics feature. Iterators are designed after C++.

Usage

package main

import ( "fmt"

"github.com/igrmk/treemap/v2"

)

func main() { tr := treemap.Newint, string tr.Set(1, "World") tr.Set(0, "Hello") for it := tr.Iterator(); it.Valid(); it.Next() { fmt.Println(it.Key(), it.Value()) } }

// Output: // 0 Hello // 1 World

Install

go get github.com/igrmk/treemap/v2

Complexity

Name	Time
Set	O(log_N_)
Del	O(log_N_)
Get	O(log_N_)
Contains	O(log_N_)
Len	O(1)
Clear	O(1)
Range	O(log_N_)
Iterator	O(1)
Reverse	O(log_N_)
Iterate through the entire map	O(N)

Memory usage

TreeMap uses O(N) memory.

TreeMap v1

The previous version of this package used gotemplate library to generate a type specific file in your local directory. Here is the link to this version treemap v1.