开源一个 Go 泛型数据容器库

[Nazz]

https://github.com/lxzan/dao

DAO 是一个基于泛型的数据结构与算法库, 旨在补充标准库在数据容器和算法方面的不足, 简化业务开发.

Features

简单介绍下一些特色数据容器

Vector

为简化 CRUD 而开发的容器, 使用带接口约束泛型, 部分弥补了 Go 不支持泛型方法的不足

package main

import (
	"fmt"
	"github.com/lxzan/dao/vector"
	"time"
)

type User struct {
	ID        int64
	Name      string
	CreatedAt time.Time
	UpdatedAt time.Time
}

func (u *User) GetID() int64 {
	return u.ID
}

func main() {
	var docs = vector.NewFromDocs[int64, *User](
		&User{ID: 1, Name: "ming"},
		&User{ID: 3, Name: "hong"},
		&User{ID: 3, Name: "hong"},
		&User{ID: 4, Name: "mei"},
		&User{ID: 4, Name: "mei"},
	)
	docs.
		Unique().
		Filter(func(i int, v *User) bool {
			return v.ID%2 == 1
		}).
		Range(func(i int, v *User) bool {
			fmt.Printf("id=%d, name=%s\n", v.ID, v.Name)
			return true
		})
}

IndexedHeap

N 叉索引堆, 在普通堆的基础上拓展了更新和删除方法.

package main

import (
	"github.com/lxzan/dao/heap"
	"github.com/lxzan/dao/types/cmp"
)

func main() {
	var h = heap.NewIndexedHeap[int, string](heap.Quadratic, cmp.Less[int])
	h.Push(1, "")
	h.Push(3, "")
	h.Push(5, "")
	var node = h.Push(2, "")
	h.Push(4, "")
	h.Push(6, "")

	h.DeleteByIndex(node.Index())
	for h.Len() > 0 {
		println(h.Pop().Key())
	}
}

Deque

高性能双端队列, 基于数组实现, 使用数据索引模拟指针. Deque 内部不包含任何指针, 删除的槽位内存可复用, 不依赖 sync.Pool.

package main

import (
	"fmt"
	"github.com/lxzan/dao/deque"
)

func main() {
	var q = deque.Deque[int]{}
	q.PushBack(1)
	q.PushBack(3)
	q.PushBack(5)
	q.PushBack(7)
	q.PushBack(9)

	for i := q.Front(); i != nil; i = q.Get(i.Next()) {
		fmt.Printf("%d ", i.Value())
	}

	fmt.Printf("\n")

	for i := q.Back(); i != nil; i = q.Get(i.Prev()) {
		fmt.Printf("%d ", i.Value())
	}
}

红黑树

高性能红黑树实现, 从 nginx 移植而来.

package main

import (
	"github.com/lxzan/dao/rbtree"
)

func main() {
	var tree = rbtree.New[int, struct{}]()
	for i := 0; i < 100; i++ {
		tree.Set(i, struct{}{})
	}

	var results = tree.
		NewQuery().
		Left(func(key int) bool { return key >= 45 }).
		Right(func(key int) bool { return key <= 65 }).
		Limit(5).
		Offset(5).
		Order(rbtree.DESC).
		FindAll()
	for _, item := range results {
		println(item.Key)
	}
}