search

chen3feng / stl4go

Generic Container and Algorithm Library for Go
Apache License 2.0
315 stars 49 forks source link
go golang stl

readme

stl4go -- STL for Golang

English | 简体中文

This library contains generic containers and algorithms, it is designed to be STL for Golang.

License Apache 2.0 Golang Build Status Coverage Status GoReport Go Reference

This library depends on go generics, which is introduced in 1.18+.

import "github.com/chen3feng/stl4go"

Package stl4go is a generic container and algorithm library for go.

Introduce

This library is a general container and algorithm library that attempts to learn from the C++ STL implementation after Go 1.18 began to support generics. (Personally I's totally unacceptable for me use to languages without generics, so I didn't try it until go 1.18).

The code quality of this library is quite high and follows the latest best practices in the industry. Test coverage is close💯%, ✅，CI, and gosec check are both set up, got GoReport score。

Features

As we all know, C++'s STL includes containers, algorithms, and iterators relate the two.

Due to language limitations, it is impossible and unnecessary to completely imitate the interface of C++ STL in Go, so C++ users may feel familiar, and sometimes (maybe) feel more convenient.

Containers

There are following container interfaces:

Different interface has different methods. The Container interface has following methods:

Read source code for details.

Currently container implementations are:

Non-Container Components

Iterators

Vector, DList and SkipList support iterators.

// Iterator is the interface for container's iterator.
type Iterator[T any] interface {
    IsNotEnd() bool // Whether it is point to the end of the range.
    MoveToNext()    // Let it point to the next element.
    Value() T       // Return the value of current element.
}

// MutableIterator is the interface for container's mutable iterator.
type MutableIterator[T any] interface {
    Iterator[T]
    Pointer() *T // Return the pointer to the value of current element.
}
l := stl4go.NewDListOf(Range(1, 10000)...)
sum := 0
for i := 0; i < b.N; i++ {
    for it := l.Iterate(); it.IsNotEnd(); it.MoveToNext() {
        sum += it.Value()
    }
}

The iterator of SkipList is MutableMapIterator:

// MapIterator is the interface for map's iterator.
type MapIterator[K any, V any] interface {
    Iterator[V]
    Key() K // The key of the element
}

// MutableMapIterator is the interface for map's mutable iterator.
type MutableMapIterator[K any, V any] interface {
    MutableIterator[V]
    Key() K // The key of the element
}

SkipList also supports range iteration:

sl := stl4go.NewSkipList[int, int]()
for i := 0; i < 1000; i++ {
    sl.Insert(i, 0)
}
it := sl.FindRange(120, 350)

Iterating over it only yields the keys between 120 and 349.

In many cases, it is more convenient to use the ForEach and ForEachIf methods provided by the container, and the performance is often better:

func TestSkipList_ForEach(t *testing.T) {
    sl := newSkipListN(100)
    a := []int{}
    sl.ForEach(func(k int, v int) {
        a = append(a, k)
    })
    expectEq(t, len(a), 100)
    expectTrue(t, IsSorted(a))
}

ForEachIf is used for scenarios that you want to end early during the iteration:

func Test_DList_ForEachIf(t *testing.T) {
    l := NewDListOf(1, 2, 3)
    c := 0
    l.ForEachIf(func(n int) bool {
        c = n
        return n != 2
    })
    expectEq(t, c, 2)
}

You can use ForEachMutable or ForEachMutable to modify the value of an element during the iteration:

func TestSkipList_ForEachMutable(t *testing.T) {
    sl := newSkipListN(100)
    sl.ForEachMutable(func(k int, v *int) {
        *v = -*v
    })
    for i := 0; i < sl.Len(); i++ {
        expectEq(t, *sl.Find(i), -i)
    }
}

Algorithms

Due to the limitations of language, most algorithms only support Slice. The functions name of the algorithms ends with If or Func, indicating that a custom comparison function can be passed.

Generate

Data manipulation

Compute

Compare

Lookup

Binary Search

See C++ STL.

Sort

heap

Heap provides basic min heap algorithms:

and variants with custome comparasion function:

both of them are mush faster and easier to use than container/heap.

See detailed usage and benchmark report in the document of heap。

Interface Design and Naming

The design leart much from the C++ STL. The T here represents template. Yes, Go's generic is not template. but who made C++ so influential and STL so famous?

Many libraries are designed for small code repositories or split into multiple subpackages in one repository. For example:

import (
    "github.com/someone/awesomelib/skiplist"
    "github.com/someone/awesomelib/binarysearch"
)

func main() {
    sl := skiplist.New()
}

This way of writing seems elegant, but because everyone likes good names, import renaming has to be introduced in use in case of package name conflict, and different users have different renaming style, which increases the mental burden of code reading and writing.

I don't like this style, especially in a larger repository.

Therefore, this library is all under the stl4go package, and it is expected that it will not namesake in other people's libraries.

TODO

See Issue。

And add more detailed documents.

Go Doc

Click to view the generated doc.

Reference