Note: The generic v2 API is still under development and has not been released. It requires Go 1.26 or later. For the previous version, please check the v1 branch.
Go implementation of C++ STL iterators and algorithms.
Less hand-written loops, more expressive code.
README translations: 简体中文
Go now has generics, and we deserve to have reusable general algorithms. iter helps improve Go code in several ways:
-
Some simple loops are unlikely to be wrong or inefficient, but calling an algorithm instead will make the code more concise and easier to comprehend. Such as AllOf, FindIf, Accumulate.
-
Some algorithms are not complicated, but it is not easy to write them correctly. Reusing code makes them easier to reason for correctness. Such as Shuffle, Sample, Partition.
-
STL also includes some complicated algorithms that may take hours to make it correct. Implementing it manually is impractical. Such as NthElement, StablePartition, NextPermutation.
-
The implementation in the library contains some imperceptible performance optimizations. For instance, MinmaxElement is done by taking two elements at a time. In this way, the overall number of comparisons is significantly reduced.
There are alternative libraries have similar goals, such as gostl, gods and go-stp. What makes iter unique is:
-
Non-intrusive. Instead of introducing new containers,
itertends to reuse existed containers in Go (slice, string, list.List, etc.) and use iterators to adapt them to algorithms. -
Full algorithms (>100). It includes almost all algorithms come before C++17. Check the Full List.
The examples keep package qualifiers so the generic v2 API is explicit. See examples_test.go for complete, executable examples.
| Print a list.List | |
|---|---|
l := list.New()
for i := 1; i <= 5; i++ {
l.PushBack(i)
}
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value)
if e.Next() != nil {
fmt.Print("->")
}
}
// Output:
// 1->2->3->4->5 |
l := list.New()
algo.GenerateN(lists.ListBackInserter[int](l), 5, iter.IotaGenerator(1))
algo.Copy(lists.Begin[int](l), lists.End[int](l), iter.IOWriter[int](os.Stdout, "->"))
// Output:
// 1->2->3->4->5 |
| Reverse a string | |
s := "!dlrow olleH"
var sb strings.Builder
for i := len(s) - 1; i >= 0; i-- {
sb.WriteByte(s[i])
}
fmt.Println(sb.String())
b := []byte(s)
for i := len(s)/2 - 1; i >= 0; i-- {
j := len(s) - 1 - i
b[i], b[j] = b[j], b[i]
}
fmt.Println(string(b))
// Output:
// Hello world!
// Hello world! |
s := "!dlrow olleH"
fmt.Println(strs.MakeString(strs.RBegin(s), strs.REnd(s)))
b := []byte(s)
iterslices.Reverse(b)
fmt.Println(string(b))
// Output:
// Hello world!
// Hello world! |
| In-place deduplicate (from SliceTricks, with minor change) | |
in := []int{3, 2, 1, 4, 3, 2, 1, 4, 1}
sort.Ints(in)
j := 0
for i := 1; i < len(in); i++ {
if in[j] == in[i] {
continue
}
j++
in[j] = in[i]
}
in = in[:j+1]
fmt.Println(in)
// Output:
// [1 2 3 4] |
in := []int{3, 2, 1, 4, 3, 2, 1, 4, 1}
iterslices.Sort(in)
in = iterslices.Unique(in)
fmt.Println(in)
// Output:
// [1 2 3 4] |
| Sum all integers received from a channel | |
ch := make(chan int)
go func() {
for _, x := range rand.Perm(100) {
ch <- x + 1
}
close(ch)
}()
var sum int
for x := range ch {
sum += x
}
fmt.Println(sum)
// Output:
// 5050 |
ch := make(chan int)
go func() {
algo.CopyN[int](iter.IotaReader(1), 100, iter.ChanWriter(ch))
close(ch)
}()
fmt.Println(algo.Accumulate(iter.ChanReader(ch), nil, 0))
// Output:
// 5050 |
| Remove consecutive spaces in a string | |
str := " a quick brown fox "
var sb strings.Builder
var prevIsSpace bool
for i := 0; i < len(str); i++ {
if str[i] != ' ' || !prevIsSpace {
sb.WriteByte(str[i])
}
prevIsSpace = str[i] == ' '
}
fmt.Println(sb.String())
// Output:
// a quick brown fox |
str := " a quick brown fox "
var sb strs.StringBuilderInserter[byte]
algo.UniqueCopyIf(strs.Begin(str), strs.End(str), &sb,
func(x, y byte) bool { return x == ' ' && y == ' ' })
fmt.Println(sb.String())
// Output:
// a quick brown fox |
| Collect N maximum elements from a channel | |
// Need to manually maintain a min-heap. |
top := make([]int, 5)
algo.PartialSortCopyBy(iter.ChanReader(ch), nil, iterslices.Begin(top), iterslices.End(top),
func(x, y int) bool { return x > y })
algo.Copy(iterslices.Begin(top), iterslices.End(top), iter.IOWriter[int](os.Stdout, ", ")) |
| Print all permutations of ["a", "b", "c"] | |
// Usually requires some sort of recursion. |
s := []string{"a", "b", "c"}
for ok := true; ok; ok = iterslices.NextPermutation(s) {
fmt.Println(s)
}
// Output:
// [a b c]
// [a c b]
// [b a c]
// [b c a]
// [c a b]
// [c b a] |
BSD 3-Clause