go语言数据结构和算法库GoSTL

59次阅读

共计 9114 个字符，预计需要花费 23 分钟才能阅读完成。

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 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}
    }
}

正文完
golang 数据结构和算法
发表至：无分类
2019-11-05
 0