Skip to content
Go implementation of C++ STL iterators and algorithms.
Go Shell
Branch: master
Clone or download
Latest commit 0252883 Dec 15, 2019
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.gitignore cover script Nov 27, 2019
.travis.yml
LICENSE change license Dec 6, 2019
README.md Update README.md Dec 15, 2019
README_ZH.md Update README_ZH.md Dec 15, 2019
algorithm.go add test Dec 6, 2019
algorithm_test.go fix golangci issues Dec 9, 2019
codecov.yml update codecov Dec 6, 2019
cover.sh update codecov Dec 6, 2019
examples_test.go update examples Dec 7, 2019
funcs.go add tests Dec 6, 2019
go.mod first commit Nov 18, 2019
go.sum add comments and tests Nov 27, 2019
iterator.go
iterators.go
iterators_test.go function alias Dec 7, 2019
misc.go fix golangci issues Dec 9, 2019
misc_test.go function alias Dec 7, 2019
reflection.go

README.md

iter

Go implementation of C++ STL iterators and algorithms.

Less hand-written loops, more expressive code.

README translations: 简体中文

GoDoc Build Status codecov Go Report Card

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, iter tends 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

You can’t perform that action at this time.