GoSTL-强大的go语言数据结构和算法库

stirlingx · 2019-11-05 15:17:52 · 1927 次点击

GoSTL

GoSTL是一个go语言数据结构和算法库，类似C++的STL，但功能更强大。结合go语言的特点，大部分数据结构都实现了线程安全，可以在创建对象的时候通过配置参数指定是否开启。

功能列表

数据结构
算法

例子

切片（slice）

这个库中的切片是对go原生切片的重定义。
下面是一个如何将go原生的切片转成IntSlice，然后对其排序的例子。

package main

import (
    "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 main

import (
    "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 main

import (
    "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 main

import (
    "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 main

import (
    "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 main

import (
    "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 main

import (
    "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 main

import (
    "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 main

import (
    "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 list
func 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-save
func 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 main

import (
    "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 main

import (
    "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 main

import (
    "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 main

import (
    "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 main

import (
    "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 main

import (
    "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 main

import (
    "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 main

import (
    "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 main

import (
    "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 main

import (
    "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
        }
    }
}