GoSTL
GoSTL是一个go语言数据结构和算法库，类似C++的STL，但功能更强大。结合go语言的特点，大部分数据结构都实现了线程安全，可以在创建对象的时候通过配置参数指定是否开启。
功能列表
数据结构
- 切片（slice）
- 数组（array）
- 向量（vector）
- 列表（list）
- 双端队列（deque）
- 队列（queue）
- 优先队列（priority_queue）
- 栈（stack）
- 红黑树（rbtree）
- 映射（map/multimap）
- 集合（set/multiset）
- 位映射（bitmap）
- 布隆过滤器（bloom_filter）
- 哈希映射树（hamt）
- 一致性哈希（ketama）
- 跳表（skiplist）
算法
- 快排（sort）
- 稳定排序（stable_sort）
- 二分查找（binary_search）
- 二分查找第一个元素的位置（lower_bound）
- 二分查找第一个大于该元素的位置（upper_bound）
- 下一个排列组合（next_permutation）
例子
切片（slice）
这个库中的切片是对go原生切片的重定义。
下面是一个如何将go原生的切片转成IntSlice，然后对其排序的例子。
package mainimport ( "fmt" "github.com/liyue201/gostl/algorithm/sort" "github.com/liyue201/gostl/ds/slice" "github.com/liyue201/gostl/utils/comparator")func main() { a := slice.IntSlice(make([]int, 0)) a = append(a, 2) a = append(a, 1) a = append(a, 3) fmt.Printf("%v\n", a) // sort in ascending sort.Sort(a.Begin(), a.End()) fmt.Printf("%v\n", a) // sort in descending sort.Sort(a.Begin(), a.End(), comparator.Reverse(comparator.BuiltinTypeComparator)) fmt.Printf("%v\n", a)}数组（array）
数组是一种一旦创建长度就固定的数据结构，支持随机访问和迭代器访问。
package mainimport ( "fmt" "github.com/liyue201/gostl/ds/array")func main() { a := array.New(5) for i := 0; i < a.Size(); i++ { a.Set(i, i + 1) } for i := 0; i < a.Size(); i++ { fmt.Printf("%v ", a.At(i)) } fmt.Printf("\n") for iter := a.Begin(); iter.IsValid(); iter.Next() { fmt.Printf("%v ", iter.Value()) }}vector
向量是一种大小可以自动伸缩的数据结构，内部使用切片实现。支持随机访问和迭代器访问。
package mainimport ( "fmt" "github.com/liyue201/gostl/algorithm/sort" "github.com/liyue201/gostl/ds/vector" "github.com/liyue201/gostl/utils/comparator")func main() { v := vector.New() v.PushBack(1) v.PushBack(2) v.PushBack(3) for i := 0; i < v.Size(); i++ { fmt.Printf("%v ", v.At(i)) } fmt.Printf("\n") // sort in descending sort.Sort(v.Begin(), v.End(), comparator.Reverse(comparator.BuiltinTypeComparator)) for iter := v.Begin(); iter.IsValid(); iter.Next() { fmt.Printf("%v ", iter.Value()) }}列表（list）
- 简单列表
简单列表是一种单向列表，支持从头部和尾部插入数据，只支持从头部遍历数据。
package mainimport ( "fmt" "github.com/liyue201/gostl/ds/list/simple_list")func main() { l := simple_list.New() l.PushBack(1) l.PushFront(2) l.PushFront(3) l.PushBack(4) for n := l.FrontNode(); n != nil; n = n.Next() { fmt.Printf("%v ", n.Value) }}- 双向列表
双向列表，支持从头部和尾部插入数据，支持从头部和尾部遍历数据。
package mainimport ( "fmt" list "github.com/liyue201/gostl/ds/list/bid_list")func main() { l := list.New() l.PushBack(1) l.PushFront(2) l.PushFront(3) l.PushBack(4) for n := l.FrontNode(); n != nil; n = n.Next() { fmt.Printf("%v ", n.Value) } fmt.Printf("\n", ) for n := l.BackNode(); n != nil; n = n.Prev() { fmt.Printf("%v ", n.Value) }}双端队列（deque）
双端队列支持从头部和尾部高效的插入数据，支持随机访问和迭代器访问。
package mainimport ( "fmt" "github.com/liyue201/gostl/algorithm/sort" "github.com/liyue201/gostl/ds/deque")func main() { q := deque.New() q.PushBack(2) q.PushFront(1) q.PushBack(3) q.PushFront(4) fmt.Printf("%v\n", q) sort.Sort(q.Begin(), q.End()) fmt.Printf("%v\n", q) fmt.Printf("%v\n", q.PopBack()) fmt.Printf("%v\n", q.PopFront()) fmt.Printf("%v\n", q)}队列（queue）
队列是一种先进先出的数据结构，底层使用双端队列或者链表作为容器，默认使用双端队列，若想使用链表，可以在创建对象时使用queue.WithListContainer()参数。支持线程安全。
package mainimport ( "fmt" "github.com/liyue201/gostl/ds/queue" "sync" "time")func example1() { fmt.Printf("example1:\n") q := queue.New() for i := 0; i < 5; i++ { q.Push(i) } for !q.Empty() { fmt.Printf("%v\n", q.Pop()) }}// 基于链表func example2() { fmt.Printf("example2:\n") q := queue.New(queue.WithListContainer()) for i := 0; i < 5; i++ { q.Push(i) } for !q.Empty() { fmt.Printf("%v\n", q.Pop()) }}// 线程安全func example3() { fmt.Printf("example3:\n") s := queue.New(queue.WithThreadSave()) sw := sync.WaitGroup{} sw.Add(2) go func() { defer sw.Done() for i := 0; i < 10; i++ { s.Push(i) time.Sleep(time.Microsecond * 100) } }() go func() { defer sw.Done() for i := 0; i < 10; { if !s.Empty() { val := s.Pop() fmt.Printf("%v\n", val) i++ } else { time.Sleep(time.Microsecond * 100) } } }() sw.Wait()}func main() { example1() example2() example3()}优先队列（priority_queue）
优先队列基于go标准库的container/heap包实现，支持线程安全。
package mainimport ( "fmt" "github.com/liyue201/gostl/ds/priority_queue" "github.com/liyue201/gostl/utils/comparator")func main() { q := priority_queue.New(priority_queue.WithComparator(comparator.Reverse(comparator.BuiltinTypeComparator)), priority_queue.WithThreadSave()) q.Push(5) q.Push(13) q.Push(7) q.Push(9) q.Push(0) q.Push(88) for !q.Empty() { fmt.Printf("%v\n", q.Pop()) }}栈（stack）
栈是一种后进先出的数据结构，底层使用双端队列或者链表作为容器，默认使用双端队列，若想使用链表，可以在创建对象时使用queue.WithListContainer()参数。支持线程安全。
package mainimport ( "fmt" "github.com/liyue201/gostl/ds/stack" "sync" "time")func example1() { fmt.Printf("example1:\n") s := stack.New() s.Push(1) s.Push(2) s.Push(3) for !s.Empty() { fmt.Printf("%v\n", s.Pop()) }}// based on listfunc example2() { fmt.Printf("example2:\n") s := stack.New(stack.WithListContainer()) s.Push(1) s.Push(2) s.Push(3) for !s.Empty() { fmt.Printf("%v\n", s.Pop()) }}// thread-savefunc example3() { fmt.Printf("example3:\n") s := stack.New(stack.WithThreadSave()) sw := sync.WaitGroup{} sw.Add(2) go func() { defer sw.Done() for i := 0; i < 10; i++ { s.Push(i) time.Sleep(time.Microsecond * 100) } }() go func() { defer sw.Done() for i := 0; i < 10; { if !s.Empty() { val := s.Pop() fmt.Printf("%v\n", val) i++ } else { time.Sleep(time.Microsecond * 100) } } }() sw.Wait()}func main() { example1() example2() example3()}红黑树（rbtree）
红黑树是一种平衡二叉排序树，用于高效的插入和查找数据。
package mainimport ( "fmt" "github.com/liyue201/gostl/ds/rbtree")func main() { tree := rbtree.New() tree.Insert(1, "aaa") tree.Insert(5, "bbb") tree.Insert(3, "ccc") fmt.Printf("find %v returns %v\n",5, tree.Find(5)) tree.Traversal(func(key, value interface{}) bool { fmt.Printf("%v : %v\n", key, value) return true }) tree.Delete(tree.FindNode(3))}映射（map）
映射底层使用红黑树实现，支持按key顺序迭代访问，有别于go原生的map类型（go原生的map底层是哈希，不支持按key顺序迭代访问）。支持线程安全。
package mainimport ( "fmt" "github.com/liyue201/gostl/ds/map")func main() { m := treemap.New(treemap.WithThreadSave()) m.Insert("a", "aaa") m.Insert("b", "bbb") fmt.Printf("a = %v\n", m.Get("a")) fmt.Printf("b = %v\n", m.Get("b")) m.Erase("b")}集合（set）
集合底层使用红黑树实现，支持线程安全。支持集合的基本运算，如求并集，交集，差集。支持线程安全。
package mainimport ( "fmt" "github.com/liyue201/gostl/ds/set")func main() { s := set.New(set.WithThreadSave()) s.Insert(1) s.Insert(5) s.Insert(3) s.Insert(4) s.Insert(2) s.Erase(4) for iter := s.Begin(); iter.IsValid(); iter.Next() { fmt.Printf("%v\n", iter.Value()) } fmt.Printf("%v\n", s.Contains(3)) fmt.Printf("%v\n", s.Contains(10))}位映射（bitmap）
位映射用于快速标记和查找一个非负整数是否集合中。相对于map或数组占用内存空间更小。
package mainimport ( "fmt" "github.com/liyue201/gostl/ds/bitmap")func main() { bm := bitmap.New(1000) bm.Set(6) bm.Set(10) fmt.Printf("%v\n", bm.IsSet(5)) fmt.Printf("%v\n", bm.IsSet(6)) bm.Unset(6) fmt.Printf("%v\n", bm.IsSet(6))}布隆过滤器（bloom_filter）
布隆过滤器用来快速判断数据是否在集合中，底层使用bitmap实现，相对于map占用内存空间更小。缺点是不支持删除和有一定的错误率。支持线程安全。支持数据导出和通过导出的数据重现构建。
package mainimport ( "fmt" "github.com/liyue201/gostl/ds/bloomfilter")func main() { filter := bloom.New(100, 4, bloom.WithThreadSave()) filter.Add("hhhh") filter.Add("gggg") fmt.Printf("%v\n", filter.Contains("aaaa")) fmt.Printf("%v\n", filter.Contains("gggg"))}哈希映射树（hamt）
哈希映射树相对于传统哈希（开放地址法或链表法哈希），出现哈希冲突的概率更小，空间利用率更高。扩容缩容性时间复杂度低。支持线程安全。
package mainimport ( "fmt" "github.com/liyue201/gostl/ds/hamt")func main() { h := hamt.New() // h := hamt.New(hamt.WithThreadSave()) key := []byte("aaaaa") val := "bbbbbbbbbbbbb" h.Insert(key, val) fmt.Printf("%v = %v\n", string(key), h.Get(key)) h.Erase(key) fmt.Printf("%v = %v\n", string(key), h.Get(key))}一致性哈希（ketama）
一致性哈希ketama算法，使用64位的哈希函数和map存储，出现冲突的概率更小。支持线程安全。
package mainimport ( "github.com/liyue201/gostl/ds/ketama" "fmt")func main() { k := ketama.New() k.Add("1.2.3.3") k.Add("2.4.5.6") k.Add("5.5.5.1") node, _ := k.Get("aaa") fmt.Printf("%v\n", node) k.Remove("2.4.5.6")}跳表（skliplist）
跳表是一种通过以空间换时间来实现快速查找的数据结构。支持线程安全。
package mainimport ( "fmt" "github.com/liyue201/gostl/ds/skiplist")func main() { list := skiplist.New(skiplist.WithMaxLevel(15)) list.Insert("aaa", "1111") list.Insert("bbb", "2222") fmt.Printf("aaa = %v\n", list.Get("aaa")) fmt.Printf("aaa = %v\n\n", list.Get("bbb")) list.Traversal(func(key, value interface{}) bool { fmt.Printf("key:%v value:%v\n", key, value) return true }) list.Remove("aaa")}排序、稳定排序、二分查找
Sort: 内部使用的是快速排序算法。
Stable: 稳定排序，内部使用归并排序。
BinarySearch: 通过二分查找，判断一个元素是否在迭代器范围中。
LowerBound: 通过二分查找，找到第一个等于该元素的数据返回该迭代器。
UpperBound： 通过二分查找，找到第一个大于该元素的数据返回该迭代器。
package mainimport ( "github.com/liyue201/gostl/algorithm/sort" "github.com/liyue201/gostl/utils/comparator" "github.com/liyue201/gostl/ds/slice" "fmt")func main() { a := make([]string, 0) a = append(a, "bbbb") a = append(a, "ccc") a = append(a, "aaaa") a = append(a, "bbbb") a = append(a, "bb") sliceA := slice.StringSlice(a) ////Sort in ascending order sort.Sort(sliceA.Begin(), sliceA.End()) //sort.Stable(sliceA.Begin(), sliceA.End()) fmt.Printf("%v\n", a) if sort.BinarySearch(sliceA.Begin(), sliceA.End(), "bbbb") { fmt.Printf("BinarySearch: found bbbb\n") } iter := sort.LowerBound(sliceA.Begin(), sliceA.End(), "bbbb") if iter.IsValid() { fmt.Printf("LowerBound bbbb: %v\n", iter.Value()) } iter = sort.UpperBound(sliceA.Begin(), sliceA.End(), "bbbb") if iter.IsValid() { fmt.Printf("UpperBound bbbb: %v\n", iter.Value()) } //Sort in descending order sort.Sort(sliceA.Begin(), sliceA.End(), comparator.Reverse(comparator.BuiltinTypeComparator)) //sort.Stable(sliceA.Begin(), sliceA.End(), comparator.Reverse(comparator.BuiltinTypeComparator)) fmt.Printf("%v\n", a)}下个排序组合（next_permutation）
这个函数修改迭代器范围内的数据为下一个排序组合。
package mainimport ( "github.com/liyue201/gostl/algorithm/sort" "github.com/liyue201/gostl/ds/slice" "github.com/liyue201/gostl/utils/comparator" "fmt")func main() { a := slice.IntSlice(make([]int, 0)) for i := 1; i <= 3; i++ { a = append(a, i) } fmt.Println("NextPermutation") for { fmt.Printf("%v\n", a) if !sort.NextPermutation(a.Begin(), a.End()) { break } } fmt.Println("PrePermutation") for { fmt.Printf("%v\n", a) if !sort.NextPermutation(a.Begin(), a.End(), comparator.Reverse(comparator.BuiltinTypeComparator)) { break } }}