GoSTL - Golang 实现的类似 C++ STL 的数据结构与算法库

GoSTL 是一个为 Go 语言设计的数据结构和算法库，旨在提供类似 C++ STL 的功能，但更强大。结合 Go 语言的特点，大多数数据结构都实现了 goroutine 安全。在创建对象时，可以通过配置参数指定是否开启。

功能列表

数据结构

slice
array
vector
list
deque
queue
priority_queue
stack
rbtree (red_black_tree)
map/multimap
set/multiset
bitmap
bloom_filter
hamt (hash_array_mapped_trie)
ketama
skiplist

算法

sort (quick_sort)
stable_sort (merge_sort)
binary_search
lower_bound
upper_bound
next_permutation
nth_element
swap
reverse
count/count_if
find/find_if
min_element/max_element

使用示例

Slice 示例

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 := make([]int, 0)
 a = append(a, 2)
 a = append(a, 1)
 a = append(a, 3)
 fmt.Printf("%v\n", a)

 wa := slice.NewSliceWrapper(a)

 // 升序排序
 sort.Sort[int](wa.Begin(), wa.End(), comparator.IntComparator)
 fmt.Printf("%v\n", a)

 // 降序排序
 sort.Sort[int](wa.Begin(), wa.End(), comparator.Reverse(comparator.IntComparator))
 fmt.Printf("%v\n", a)
}

Array 示例

package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/array"
)

func main() {
  a := array.New[int](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[int]()
  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.Sort[int](v.Begin(), v.End(), comparator.Reverse(comparator.IntComparator))
  for iter := v.Begin(); iter.IsValid(); iter.Next() {
    fmt.Printf("%v ", iter.Value())
  }
}

List 示例

单向链表

package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/list/simplelist"
)

func main() {
  l := simplelist.New[int]()
  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===============\n")
}

双向链表

package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/list/bidlist"
)

func main() {
  l := bidlist.New[int]()
  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"
  "github.com/liyue201/gostl/utils/comparator"
  "math/rand"
)

func main() {
  q := deque.New[int]()
  for i := 0; i < 100; i++ {
    r := rand.Int() % 100
    q.PushBack(r)
    q.PushFront(r)
  }
  fmt.Printf("%v\n", q)

  sort.Sort[int](q.Begin(), q.End(), comparator.IntComparator)
  fmt.Printf("%v\n", q)

  for !q.Empty() {
    r := rand.Int() % q.Size()
    q.EraseAt(r)
  }
  fmt.Printf("%v\n", q)
}

Queue 示例

package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/queue"
)

func main() {
  q := queue.New[int]()
  for i := 0; i < 5; i++ {
    q.Push(i)
  }
  for !q.Empty() {
    fmt.Printf("%v\n", q.Pop())
  }
}

Priority Queue 示例

package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/priorityqueue"
  "github.com/liyue201/gostl/utils/comparator"
)

func main() {
  q := priorityqueue.New[int](comparator.Reverse(comparator.IntComparator),
    priorityqueue.WithGoroutineSafe())
  q.Push(4)
  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 示例

package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/stack"
)

func main() {
  s := stack.New[int]()
  s.Push(1)
  s.Push(2)
  s.Push(3)
  for !s.Empty() {
    fmt.Printf("%v\n", s.Pop())
  }
}

RBTree 示例

package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/rbtree"
  "github.com/liyue201/gostl/utils/comparator"
)

func main() {
  tree := rbtree.New[int, string](comparator.IntComparator)
  tree.Insert(1, "aaa")
  tree.Insert(5, "bbb")
  tree.Insert(3, "ccc")
  v, _ := tree.Find(5)
  fmt.Printf("find %v returns %v\n", 5, v)

  tree.Traversal(func(key int, value string) bool {
    fmt.Printf("%v : %v\n", key, value)
    return true
  })
  tree.Delete(tree.FindNode(3))
}

Map 示例

package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/map"
  "github.com/liyue201/gostl/utils/comparator"
)

func main() {
  m := treemap.New[string, string](comparator.StringComparator, treemap.WithGoroutineSafe())

  m.Insert("a", "aaa")
  m.Insert("b", "bbb")

  a, _ := m.Get("a")
  b, _ := m.Get("b")
  fmt.Printf("a = %v\n", a)
  fmt.Printf("b = %v\n", b)

  m.Erase("b")
}

Set 示例

package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/set"
  "github.com/liyue201/gostl/utils/comparator"
)

func main() {
  s := set.New[int](comparator.IntComparator, set.WithGoroutineSafe())
  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 示例

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 示例

package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/bloomfilter"
)

func main() {
  filter := bloom.New(100, 4, bloom.WithGoroutineSafe())
  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[string](hamt.WithGoroutineSafe())
  key := []byte("aaaaa")
  val := "bbbbbbbbbbbbb"

  h.Insert(key, val)
  v, _ := h.Get(key)
  fmt.Printf("%v = %v\n", string(key), v)

  h.Erase(key)
  v, _ = h.Get(key)
  fmt.Printf("%v = %v\n", string(key), v)
}

Ketama 示例

package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/ketama"
)

func main() {
  k := ketama.New()
  k.Add("1.2.3.3")
  k.Add("2.4.5.6")
  k.Add("5.5.5.1")

  for i := 0; i < 10; i++ {
    node, _ := k.Get(fmt.Sprintf("%d", i))
    fmt.Printf("%v\n", node)
  }
  k.Remove("2.4.5.6")
}

Skiplist 示例

package main

import (
  "fmt"
  "github.com/liyue201/gostl/ds/skiplist"
  "github.com/liyue201/gostl/utils/comparator"
)

func main() {
  list := skiplist.New[string, string](comparator.StringComparator, skiplist.WithMaxLevel(15))
  list.Insert("aaa", "1111")
  list.Insert("bbb", "2222")
  v1, _ := list.Get("aaa")
  v2, _ := list.Get("bbb")
  fmt.Printf("aaa = %v\n", v1)
  fmt.Printf("bbb = %v\n", v2)

  list.Traversal(func(key, value string) bool {
    fmt.Printf("key:%v value:%v\n", key, value)
    return true
  })

  list.Remove("aaa")
}

排序算法示例

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 := 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.NewSliceWrapper(a)

  // 升序排序
  sort.Sort[string](sliceA.Begin(), sliceA.End(), comparator.OrderedTypeCmp[string])

  sort.Stable[string](sliceA.Begin(), sliceA.End(), comparator.StringComparator)
  fmt.Printf("%v\n", a)

  if sort.BinarySearch[string](sliceA.Begin(), sliceA.End(), "bbbb", comparator.StringComparator) {
    fmt.Printf("BinarySearch: found bbbb\n")
  }

  iter := sort.LowerBound[string](sliceA.Begin(), sliceA.End(), "bbbb", comparator.StringComparator)
  if iter.IsValid() {
    fmt.Printf("LowerBound bbbb: %v\n", iter.Value())
  }
  iter = sort.UpperBound[string](sliceA.Begin(), sliceA.End(), "bbbb", comparator.StringComparator)
  if iter.IsValid() {
    fmt.Printf("UpperBound bbbb: %v\n", iter.Value())
  }
  // 降序排序
  sort.Sort[string](sliceA.Begin(), sliceA.End(), comparator.Reverse(comparator.StringComparator))
  fmt.Printf("%v\n", a)
}

Next Permutation 示例

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 := make([]int, 0)
  for i := 1; i <= 3; i++ {
    a = append(a, i)
  }
  wa := slice.NewSliceWrapper(a)
  fmt.Println("NextPermutation")
  for {
    fmt.Printf("%v\n", a)
    if !sort.NextPermutation[int](wa.Begin(), wa.End(), comparator.IntComparator) {
      break
    }
  }
  fmt.Println("PrePermutation")
  for {
    fmt.Printf("%v\n", a)
    if !sort.NextPermutation[int](wa.Begin(), wa.End(), comparator.Reverse(comparator.IntComparator)) {
      break
    }
  }
}

Nth Element 示例

package main

import (
  "fmt"
  "github.com/liyue201/gostl/algorithm/sort"
  "github.com/liyue201/gostl/ds/deque"
  "github.com/liyue201/gostl/utils/comparator"
)

func main() {
  a := deque.New[int]()
  a.PushBack(9)
  a.PushBack(8)
  a.PushBack(7)
  a.PushBack(6)
  a.PushBack(5)
  a.PushBack(4)
  a.PushBack(3)
  a.PushBack(2)
  a.PushBack(1)
  fmt.Printf("%v\n", a)
  sort.NthElement[int](a.Begin(), a.End(), 3, comparator.IntComparator)
  fmt.Printf("%v\n", a.At(3))
  fmt.Printf("%v\n", a)
}

Swap/Reverse 示例

package main

import (
  "fmt"
  "github.com/liyue201/gostl/algorithm"
  "github.com/liyue201/gostl/ds/deque"
)

func main() {
  a := deque.New[int]()
  for i := 0; i < 9; i++ {
    a.PushBack(i)
  }
  fmt.Printf("%v\n", a)

  algorithm.Swap[int](a.First(), a.Last())
  fmt.Printf("%v\n", a)

  algorithm.Reverse[int](a.Begin(), a.End())
  fmt.Printf("%v\n", a)
}

Count/Find 等算法示例

package main

import (
  "fmt"
  "github.com/liyue201/gostl/algorithm"
  "github.com/liyue201/gostl/ds/deque"
  "github.com/liyue201/gostl/utils/comparator"
  "github.com/liyue201/gostl/utils/iterator"
)

func isEven(iter iterator.ConstIterator[int]) bool {
  return iter.Value()%2 == 0
}

func greaterThan5(iter iterator.ConstIterator[int]) bool {
  return iter.Value() > 5
}

func main() {
  a := deque.New[int]()
  for i := 0; i < 10; i++ {
    a.PushBack(i)
  }
  for i := 0; i < 5; i++ {
    a.PushBack(i)
  }
  fmt.Printf("%v\n", a)

  fmt.Printf("Count 2: %v\n", algorithm.Count[int](a.Begin(), a.End(), 2, comparator.IntComparator))

  fmt.Printf("Count 2: %v\n", algorithm.CountIf[int](a.Begin(), a.End(), isEven))

  iter := algorithm.Find[int](a.Begin(), a.End(), 2, comparator.IntComparator)
  if !iter.Equal(a.End()) {
    fmt.Printf("Fund %v\n", iter.Value())
  }
  iter = algorithm.FindIf[int](a.Begin(), a.End(), greaterThan5)
  if !iter.Equal(a.End()) {
    fmt.Printf("FindIf greaterThan5 : %v\n", iter.Value())
  }
  iter = algorithm.MaxElement[int](a.Begin(), a.End(), comparator.IntComparator)
  if !iter.Equal(a.End()) {
    fmt.Printf("largest value : %v\n", iter.Value())
  }
  iter = algorithm

更多关于golang实现类似C++ STL的数据结构与算法插件库gostl的使用的实战教程也可以访问 https://www.itying.com/category-94-b0.html

sinazl 1楼

更多关于golang实现类似C++ STL的数据结构与算法插件库gostl的使用的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html

GoSTL - Go语言实现的STL风格数据结构库

GoSTL是一个模仿C++ STL风格的Go语言数据结构与算法库，提供了类似STL的容器和算法实现。虽然Go语言本身的标准库已经提供了一些基础数据结构，但GoSTL提供了更丰富的STL风格实现。

主要特性

类似STL的容器实现
泛型支持(通过Go 1.18+的泛型)
常用算法实现
线程安全选项

基本数据结构实现

1. Vector (动态数组)

package main

import (
	"fmt"
	"github.com/liyue201/gostl/ds/vector"
)

func main() {
	v := vector.New[int]()
	v.PushBack(1)
	v.PushBack(2)
	v.PushBack(3)
	
	fmt.Printf("Size: %d\n", v.Size())  // Size: 3
	fmt.Printf("Front: %d\n", v.Front()) // Front: 1
	fmt.Printf("Back: %d\n", v.Back())   // Back: 3
	
	v.SetAt(1, 5)
	for iter := v.Begin(); iter.IsValid(); iter.Next() {
		fmt.Printf("%v ", iter.Value()) // 1 5 3
	}
}

2. List (双向链表)

package main

import (
	"fmt"
	"github.com/liyue201/gostl/ds/list"
)

func main() {
	l := list.New[int]()
	l.PushBack(1)
	l.PushBack(2)
	l.PushFront(0)
	
	fmt.Printf("Size: %d\n", l.Size()) // Size: 3
	
	for iter := l.Begin(); iter.IsValid(); iter.Next() {
		fmt.Printf("%v ", iter.Value()) // 0 1 2
	}
}

3. Deque (双端队列)

package main

import (
	"fmt"
	"github.com/liyue201/gostl/ds/deque"
)

func main() {
	dq := deque.New[int]()
	dq.PushBack(1)
	dq.PushBack(2)
	dq.PushFront(0)
	
	fmt.Printf("Front: %d\n", dq.Front()) // Front: 0
	fmt.Printf("Back: %d\n", dq.Back())   // Back: 2
	
	dq.PopFront()
	fmt.Printf("Size after pop: %d\n", dq.Size()) // Size after pop: 2
}

4. Map (基于红黑树的有序映射)

package main

import (
	"fmt"
	"github.com/liyue201/gostl/ds/map"
)

func main() {
	m := treemap.NewWithIntComparator[string]()
	m.Insert(1, "one")
	m.Insert(2, "two")
	m.Insert(3, "three")
	
	value, found := m.Get(2)
	fmt.Printf("Key 2: %s, found: %v\n", value, found) // Key 2: two, found: true
	
	m.Erase(1)
	fmt.Printf("Size after erase: %d\n", m.Size()) // Size after erase: 2
}

5. Set (基于红黑树的有序集合)

package main

import (
	"fmt"
	"github.com/liyue201/gostl/ds/set"
)

func main() {
	s := treeset.NewWithIntComparator()
	s.Insert(3)
	s.Insert(1)
	s.Insert(2)
	
	fmt.Printf("Size: %d\n", s.Size()) // Size: 3
	fmt.Printf("Contains 2: %v\n", s.Contains(2)) // Contains 2: true
	
	s.Erase(1)
	fmt.Printf("Size after erase: %d\n", s.Size()) // Size after erase: 2
}

算法实现

1. 排序算法

package main

import (
	"fmt"
	"github.com/liyue201/gostl/algorithm/sort"
	"github.com/liyue201/gostl/ds/vector"
)

func main() {
	v := vector.New[int]()
	v.PushBack(3)
	v.PushBack(1)
	v.PushBack(4)
	v.PushBack(2)
	
	sort.Sort[int](v.Begin(), v.End())
	for iter := v.Begin(); iter.IsValid(); iter.Next() {
		fmt.Printf("%d ", iter.Value()) // 1 2 3 4
	}
}

2. 查找算法

package main

import (
	"fmt"
	"github.com/liyue201/gostl/algorithm/binary_search"
	"github.com/liyue201/gostl/ds/vector"
)

func main() {
	v := vector.New[int]()
	v.PushBack(1)
	v.PushBack(2)
	v.PushBack(3)
	v.PushBack(4)
	
	// 必须先排序
	iter := binary_search.LowerBound[int](v.Begin(), v.End(), 3)
	if iter.IsValid() {
		fmt.Printf("Found: %d\n", iter.Value()) // Found: 3
	}
}

线程安全版本

GoSTL还提供了线程安全的容器版本，在容器名后加_safe后缀：

package main

import (
	"fmt"
	"github.com/liyue201/gostl/ds/vector_safe"
	"sync"
)

func main() {
	v := vector_safe.New[int]()
	
	var wg sync.WaitGroup
	for i := 0; i < 10; i++ {
		wg.Add(1)
		go func(val int) {
			defer wg.Done()
			v.PushBack(val)
		}(i)
	}
	wg.Wait()
	
	fmt.Printf("Size: %d\n", v.Size()) // Size: 10
}

自定义比较器

package main

import (
	"fmt"
	"github.com/liyue201/gostl/ds/set"
)

type Person struct {
	Name string
	Age  int
}

func main() {
	// 自定义比较函数
	comparator := func(a, b Person) int {
		if a.Age < b.Age {
			return -1
		} else if a.Age > b.Age {
			return 1
		}
		return 0
	}
	
	s := treeset.NewWith(comparator)
	s.Insert(Person{"Alice", 30})
	s.Insert(Person{"Bob", 25})
	s.Insert(Person{"Charlie", 35})
	
	for iter := s.Begin(); iter.IsValid(); iter.Next() {
		fmt.Printf("%+v\n", iter.Value())
	}
	// Output:
	// {Name:Bob Age:25}
	// {Name:Alice Age:30}
	// {Name:Charlie Age:35}
}

性能考虑

GoSTL的性能通常接近Go原生数据结构
对于简单用例，标准库的slice和map可能更高效
复杂数据结构(如红黑树)在需要有序性时很有价值

总结

GoSTL为Go开发者提供了类似C++ STL的数据结构和算法实现，特别适合需要复杂数据结构或从C++转Go的开发者。虽然Go标准库已经提供了基本数据结构，但GoSTL在以下场景特别有用：

需要有序映射/集合
需要复杂数据结构如优先队列
需要STL风格的算法操作
需要线程安全容器

项目地址: https://github.com/liyue201/gostl

注意：Go 1.18+的泛型已经可以很好地支持类似STL的编程风格，你也可以考虑基于泛型实现自己的STL风格库。