stl4go -- STL for Golang

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.

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 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:

Container is the base interface for all containers
Map is a key-value associative container
Set is set container
SortedMap is a ordered key-value associative container
SortedSet is a ordered set container
Queue is a FIFO Queue
Deque is a double ended queue

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

IsEmpty() bool returns whether the container is empty
Len() int returns the number of elements in the container
Clear() to clear the container

Read source code for details.

Currently container implementations are:

BuiltinSet provided a set funtionality based on Go's own map. It provides basic operations such as insert, search and remove, as well as advanced functions such as union, intersection, difference, subset, superset, and disjoint.
Vector is a thin encapsulation based on slice. 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, supports push/popup at both ending.
SList is a singly linked list, supports push/popup at the head and push at the tail.
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
SkipList is a SortedSet container based on the skiplist.
Stack, is a FILO container based on Slice implementation
DListQueue 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.

Non-Container Components

Pool A type safe Pool, is implemented based on sync.Pool.

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

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

Data manipulation

Copy return a copies of specified slice
CopyTo copies all elements in slice a to slice to, return the copied slice.
Fill repeatedly fills a slice with the specified value
FillPattern repeatedly fills a slice with the specified pattern
Replace replaces every element that equals to old with new
ReplaceIf replaces every element that make preq returns true with new
Transform passes the value at each position of the slice to the specified function and sets it back with its return value
TransformTo passes the value at each position of slice a to the specified function, sets its return value to the corresponding position in slice b, and returns a slice of corresponding length of slice b
TransformCopy passes the value at each position of the slice to the specified function, sets its return value to the corresponding position in a new slice and returns
Unique removes adjacent duplicate elements from a slice and returns a slice with new length containing the remaining elements, UniqueCopy returns a copy without modifying the original slice
Remove removes all elements in the slice equal to the specified value, RemoveCopy returns a copy without modifying the original slice
RemoveIf removes all elements in the slice that are equivalent to making the specified function return true, RemoveIfCopy does not modify the original slice but returns a copy
Shuffle random shuffle elements in the slice
Reverse reverses a slice, ReverseCopy returns a copy without modifying the original slice

Compute

Sum Sum
SumAs sums and returns a result as another type (eg. use int64 to return the sum of []int32).
Average finds the average value.
AverageAs averages and returns the result as another type (eg. use float64 to return the sum of []int).
Count returns the number equivalent to the specified value
CountIf returns the number of elements for which the specified function returns true

Compare

Equal checks whether two sequences are equal
Compare compares two sequences and returns -1, 0, and 1 in lexicographical order, respectively indicating the relationship of 2 slices.

Lookup

Min, Max find the maximum and minimum
MinN, MaxN, MinMax return the maximum and minimum values in the slice
Find linearly finds the first specified value and returns its index
FindIf linearly finds the first value that make specified function returns true and returns its index
AllOf, AnyOf, NoneOf return whether all, any, or none of the elements in the range can make the passed function return true accordingly.

Binary Search

See C++ STL.

BinarySearch
LowerBound
UpperBound

Sort

Sort sorting
DescSort descending sorting
StableSort stable sorting
DescStableSort descending stable sorting
IsSorted check whether the slice is sorted
IsDescSorted check whether the slice is sorted in descending order

heap

Heap provides basic min heap algorithms:

MakeMinHeap Convert a slice to a min heap
IsMinHeap Check whether a slice is a min heap
PushMinHeap Pushes an element in to the heap
PopMinHeap Popups an element from the top of the heap
RemoveMinHeap 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。

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.

chen3feng/stl4go

chen3feng

Reviews

Repository Details