iter
Note: I'm currently working on making it work with Go generics. For previous version, please check v1 branch.
Go implementation of C++ STL iterators and algorithms.
Less hand-written loops, more expressive code.
README translations: įŽäŊä¸æ
Motivation
Although Go doesn't have generics, we deserve to have reuseable general algorithms. iter helps improving Go code in several ways:
-
Some simple loops are unlikely to be wrong or inefficient, but calling 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.
Examples
The examples are run with some function alias to make it simple. See example_test.go for the detail.
| 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()
GenerateN(ListBackInserter(l), 5, IotaGenerator(1))
Copy(lBegin(l), lEnd(l), IOWriter(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(MakeString(StringRBegin(s), StringREnd(s)))
b := []byte(s)
Reverse(begin(b), end(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}
Sort(begin(in), end(in))
Erase(&in, Unique(begin(in), end(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() {
CopyN(IotaReader(1), 100, ChanWriter(ch))
close(ch)
}()
fmt.Println(Accumulate(ChanReader(ch), ChanEOF, 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 StringBuilderInserter
UniqueCopyIf(sBegin(str), sEnd(str), &sb,
func(x, y Any) bool { return x.(byte) == ' ' && y.(byte) == ' ' })
fmt.Println(sb.String())
// Output:
// a quick brown fox |
| Collect N maximum elements from a channel | |
// Need to manually mantain a min-heap. |
top := make([]int, 5)
PartialSortCopyBy(ChanReader(ch), ChanEOF, begin(top), end(top),
func(x, y Any) bool { return x.(int) > y.(int) })
Copy(begin(top), end(top), IOWriter(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 = NextPermutation(begin(s), end(s)) {
fmt.Println(s)
}
// Output:
// [a b c]
// [a c b]
// [b a c]
// [b c a]
// [c a b]
// [c b a] |
Thanks
License
BSD 3-Clause