English | 简体中文
This library contains generic containers and algorithms, it is designed to be STL for Golang.
This library depends on go generics, which is introduced in 1.18+.
import "github.com/chen3feng/stl4go"
Package stl4go is a generic container and algo rithm library for go.
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
score。
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.
Currently implemented containers are:
-
BuiltinSet
provided a set funtionality based on Go's ownmap
-
Vector
is a thin encapsulation based onslice
. It provides functions such as insertion and deletion in the middle, range deletion, etc., and is still compatible with slices. -
DList
is a doubly linked list. - SkipList is an ordered associative container that fills the gap where Go
map
only supports unordered. This is currently the fastest skip list I tested in GitHub, see skiplist-survey for performance comparison -
Stack
, is a FILO container based on Slice implementation -
Queue
is a bidirectional FIFO queue, implemented based on linked list. -
PriorityQuque
is a priority queue based on heap. Much easier to use and faster than container/heap.
Different containers support different methods. The following are the methods supported by all containers:
IsEmpty() bool
Returns whether the container is emptyLen() int
returns the number of elements in the containerClear()
to clear the container
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)
}
}
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.
Range
returns a Slice of contains integers in the range of[begin, end)
Generate
generates a sequence with the given function to fill the Slice
Sum
SumSumAs
sums and returns a result as another type (eg. useint64
to return the sum of[]int32
).Average
finds the average value.AverageAs
averages and returns the result as another type (eg. usefloat64
to return the sum of[]int
).Count
returns the number equivalent to the specified valueCountIf
returns the number of elements for which the specified function returnstrue
Equal
checks whether two sequences are equalCompare
compares two sequences and returns-1
,0
, and1
in lexicographical order, respectively indicating the relationship of 2 slices.
Min
,Max
find the maximum and minimumMinN
,MaxN
,MinMax
return the maximum and minimum values in the sliceFind
linearly finds the first specified value and returns its indexFindIf
linearly finds the first value that make specified function returnstrue
and returns its indexAllOf
,AnyOf
,NoneOf
return whether all, any, or none of the elements in the range can make the passed function returntrue
accordingly.
See C++ STL.
- BinarySearch
- LowerBound
- UpperBound
Sort
sortingDescSort
descending sortingStableSort
stable sortingDescStableSort
descending stable sortingIsSorted
check whether the slice is sortedIsDescSorted
check whether the slice is sorted in descending order
Heap provides basic min heap algorithms:
MakeMinHeap
Convert a slice to a min heapIsMinHeap
Check whether a slice is a min heapPushMinHeap
Pushes an element in to the heapPopMinHeap
Popups an element from the top of the heapRemoveMinHeap
Removes an element at index from the heap
and variants with custome comparasion function:
MakeHeapFunc
IsHeapFunc
PushHeapFunc
PopHeapFunc
RemoveHeapFunc
both of them are mush faster and easier to use than container/heap.
See detailed usage and benchmark report in the document of heap。
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.
See Issue。
And add more detailed documents.
Click to view the generated doc.