Skip to content
/ treemap Public

Generic sorted map for Go with red-black tree under the hood

License

Notifications You must be signed in to change notification settings

igrmk/treemap

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

66 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

TreeMap v2

PkgGoDev Unlicense Build Status Coverage Status GoReportCard Mentioned in Awesome Go

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.New[int, 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(logN)
Del O(logN)
Get O(logN)
Contains O(logN)
Len O(1)
Clear O(1)
Range O(logN)
Iterator O(1)
Reverse O(logN)
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.

Licensing

Copyright © 2022 igrmk. This work is free. You can redistribute it and/or modify it under the terms of the Unlicense. See the LICENSE file for more details.

Thanks to

JetBrains