简介
- Golang中常用的数据类型如切片,哈希表等实现可能不能满足我们的日常需要,如具有有序性的TreeMap等;
- 另外某些数据结构实现起来比较麻烦,如二叉堆Heap等;
- GoDS实现了各种各样的数据结构及匹配算法
GoDS
安装
git clone https://github.com/emirpasic/gods.gitgodssrcgithub.com
接口
根接口
type Container interface {
Empty() bool
Size() int
Clear()
Values() []interface{}
}
Lists
ArrayListSinglyLinkedListDoublyLinkedList
type List interface {
Get(index int) (interface{}, bool)
Remove(index int)
Add(values ...interface{})
Contains(values ...interface{}) bool
Sort(comparator utils.Comparator)
Swap(index1, index2 int)
Insert(index int, values ...interface{})
Set(index int, value interface{})
containers.Container
// Empty() bool
// Size() int
// Clear()
// Values() []interface{}
}
Sets
HashSetTreeSetLinkedHashSet
type Set interface {
Add(elements ...interface{})
Remove(elements ...interface{})
Contains(elements ...interface{}) bool
containers.Container
// Empty() bool
// Size() int
// Clear()
// Values() []interface{}
}
Stacks
LinkedListStackArrayStack
type Stack interface {
Push(value interface{})
Pop() (value interface{}, ok bool)
Peek() (value interface{}, ok bool)
containers.Container
// Empty() bool
// Size() int
// Clear()
// Values() []interface{}
}
Maps
HashMapTreeMapLinkedHashMapHashBidiMapTreeBidiMap
type Map interface {
Put(key interface{}, value interface{})
Get(key interface{}) (value interface{}, found bool)
Remove(key interface{})
Keys() []interface{}
containers.Container
// Empty() bool
// Size() int
// Clear()
// Values() []interface{}
}
Trees
RedBlackTreeAVLTreeBTreeBinaryHeap
type Tree interface {
containers.Container
// Empty() bool
// Size() int
// Clear()
// Values() []interface{}
}
Comparator
// Ex: TreeSet的使用
package main
import "github.com/emirpasic/gods/sets/treeset"
func main() {
set := treeset.NewWithIntComparator() // empty (keys are of type int)
set.Add(1) // 1
set.Add(2, 2, 3, 4, 5) // 1, 2, 3, 4, 5 (in order, duplicates ignored)
set.Remove(4) // 1, 2, 3, 5 (in order)
set.Remove(2, 3) // 1, 5 (in order)
set.Contains(1) // true
set.Contains(1, 5) // true
set.Contains(1, 6) // false
_ = set.Values() // []int{1,5} (in order)
set.Clear() // empty
set.Empty() // true
set.Size() // 0
}
比较器函数签名
type Comparator func(a, b interface{}) int
预设比较器
func StringComparator(a, b interface{}) int
func IntComparator(a, b interface{}) int
func Int8Comparator(a, b interface{}) int
func Int16Comparator(a, b interface{}) int
func Int32Comparator(a, b interface{}) int
func Int64Comparator(a, b interface{}) int
func UIntComparator(a, b interface{}) int
func UInt8Comparator(a, b interface{}) int
func UInt16Comparator(a, b interface{}) int
func UInt32Comparator(a, b interface{}) int
func UInt64Comparator(a, b interface{}) int
func Float32Comparator(a, b interface{}) int
func Float64Comparator(a, b interface{}) int
func ByteComparator(a, b interface{}) int
func RuneComparator(a, b interface{}) int
func TimeComparator(a, b interface{}) int
自定义比较器
// Custom comparator (sort by IDs)
func byID(a, b interface{}) int {
// Type assertion, program will panic if this is not respected
c1 := a.(User)
c2 := b.(User)
switch {
case c1.id > c2.id:
return 1
case c1.id < c2.id:
return -1
default:
return 0
}
}
运用自定义比较器
package main
import (
"fmt"
"github.com/emirpasic/gods/sets/treeset"
)
type User struct {
id int
name string
}
// Custom comparator (sort by IDs)
// 升序
func byID(a, b interface{}) int {
// Type assertion, program will panic if this is not respected
c1 := a.(User)
c2 := b.(User)
switch {
case c1.id > c2.id:
return 1
case c1.id < c2.id:
return -1
default:
return 0
}
}
func main() {
set := treeset.NewWith(byID)
set.Add(User{2, "Second"})
set.Add(User{3, "Third"})
set.Add(User{1, "First"})
set.Add(User{4, "Fourth"})
fmt.Println(set) // {1 First}, {2 Second}, {3 Third}, {4 Fourth}
}