结构算法库 Lists / Sets / Stacks / Maps / Trees
最后更新于：2022-04-02 02:38:26
[TOC]
> [github.com](https://github.com/emirpasic/gods)
## 概述
* [Containers](https://github.com/emirpasic/gods#containers)
* [Lists](https://github.com/emirpasic/gods#lists)
* [ArrayList](https://github.com/emirpasic/gods#arraylist)
* [SinglyLinkedList](https://github.com/emirpasic/gods#singlylinkedlist)
* [DoublyLinkedList](https://github.com/emirpasic/gods#doublylinkedlist)
* [Sets](https://github.com/emirpasic/gods#sets)
* [HashSet](https://github.com/emirpasic/gods#hashset)
* [TreeSet](https://github.com/emirpasic/gods#treeset)
* [LinkedHashSet](https://github.com/emirpasic/gods#linkedhashset)
* [Stacks](https://github.com/emirpasic/gods#stacks)
* [LinkedListStack](https://github.com/emirpasic/gods#linkedliststack)
* [ArrayStack](https://github.com/emirpasic/gods#arraystack)
* [Maps](https://github.com/emirpasic/gods#maps)
* [HashMap](https://github.com/emirpasic/gods#hashmap)
* [TreeMap](https://github.com/emirpasic/gods#treemap)
* [LinkedHashMap](https://github.com/emirpasic/gods#linkedhashmap)
* [HashBidiMap](https://github.com/emirpasic/gods#hashbidimap)
* [TreeBidiMap](https://github.com/emirpasic/gods#treebidimap)
* [Trees](https://github.com/emirpasic/gods#trees)
* [RedBlackTree](https://github.com/emirpasic/gods#redblacktree)
* [AVLTree](https://github.com/emirpasic/gods#avltree)
* [BTree](https://github.com/emirpasic/gods#btree)
* [BinaryHeap](https://github.com/emirpasic/gods#binaryheap)
* [Functions](https://github.com/emirpasic/gods#functions)
* [Comparator](https://github.com/emirpasic/gods#comparator)
* [Iterator](https://github.com/emirpasic/gods#iterator)
* [IteratorWithIndex](https://github.com/emirpasic/gods#iteratorwithindex)
* [IteratorWithKey](https://github.com/emirpasic/gods#iteratorwithkey)
* [ReverseIteratorWithIndex](https://github.com/emirpasic/gods#reverseiteratorwithindex)
* [ReverseIteratorWithKey](https://github.com/emirpasic/gods#reverseiteratorwithkey)
* [Enumerable](https://github.com/emirpasic/gods#enumerable)
* [EnumerableWithIndex](https://github.com/emirpasic/gods#enumerablewithindex)
* [EnumerableWithKey](https://github.com/emirpasic/gods#enumerablewithkey)
* [Serialization](https://github.com/emirpasic/gods#serialization)
* [JSONSerializer](https://github.com/emirpasic/gods#jsonserializer)
* [JSONDeserializer](https://github.com/emirpasic/gods#jsondeserializer)
* [Sort](https://github.com/emirpasic/gods#sort)
* [Container](https://github.com/emirpasic/gods#container)
* [Appendix](https://github.com/emirpasic/gods#appendix)
## 接口
### 通用接口
```
type Container interface {
Empty() bool
Size() int
Clear()
Values() []interface{}
}
```
所有接口包含上述参数
### Lists
```
import (
"github.com/emirpasic/gods/lists/arraylist"
"github.com/emirpasic/gods/utils"
)
func main() {
list := arraylist.New() // ArrayList
// list := sll.New() // SinglyLinkedList
// list := dll.New() // DoublyLinkedList
list.Add("a") // ["a"]
list.Add("c", "b") // ["a","c","b"]
list.Sort(utils.StringComparator) // ["a","b","c"]
_, _ = list.Get(0) // "a",true
_, _ = list.Get(100) // nil,false
_ = list.Contains("a", "b", "c") // true
_ = list.Contains("a", "b", "c", "d") // false
list.Swap(0, 1) // ["b","a",c"]
list.Remove(2) // ["b","a"]
list.Remove(1) // ["b"]
list.Remove(0) // []
list.Remove(0) // [] (ignored)
_ = list.Empty() // true
_ = list.Size() // 0
list.Add("a") // ["a"]
list.Clear() // []
list.Insert(0, "b") // ["b"]
list.Insert(0, "a") // ["a","b"]
}
```
### Map
```
import "github.com/emirpasic/gods/sets/hashset"
func main() {
set := hashset.New() // HashSet
// set := treeset.New() // TreeSet
// set := linkedhashset.New() // LinkedHashSet
set.Add(1) // 1
set.Add(2, 2, 3, 4, 5) // 3, 1, 2, 4, 5 (random order, duplicates ignored)
set.Remove(4) // 5, 3, 2, 1 (random order)
set.Remove(2, 3) // 1, 5 (random order)
set.Contains(1) // true
set.Contains(1, 5) // true
set.Contains(1, 6) // false
_ = set.Values() // []int{5,1} (random order)
set.Clear() // empty
set.Empty() // true
set.Size() // 0
}
```
### Stacks
```
import lls "github.com/emirpasic/gods/stacks/linkedliststack"
func main() {
stack := lls.New() // LinkedListStack
// stack := arraystack.New() // ArrayStack
stack.Push(1) // 1
stack.Push(2) // 1, 2
stack.Values() // 2, 1 (LIFO order)
_, _ = stack.Peek() // 2,true
_, _ = stack.Pop() // 2, true
_, _ = stack.Pop() // 1, true
_, _ = stack.Pop() // nil, false (nothing to pop)
stack.Push(1) // 1
stack.Clear() // empty
stack.Empty() // true
stack.Size() // 0
}
```
### Maps
```
import "github.com/emirpasic/gods/maps/hashmap"
func main() {
m := hashmap.New() // HashMap
// m := treemap.NewWithIntComparator() // TreeMap
// m := linkedhashmap.New() // LinkedHashMap
// m := hashbidimap.New() // HashBidiMap
// m := treebidimap.NewWith(utils.IntComparator, utils.StringComparator) // TreeBidiMap
m.Put(1, "x") // 1->x
m.Put(2, "b") // 2->b, 1->x (random order)
m.Put(1, "a") // 2->b, 1->a (random order)
_, _ = m.Get(2) // b, true
_, _ = m.Get(3) // nil, false
_ = m.Values() // []interface {}{"b", "a"} (random order)
_ = m.Keys() // []interface {}{1, 2} (random order)
m.Remove(1) // 2->b
m.Clear() // empty
m.Empty() // true
m.Size() // 0
}
```
### Trees
#### RedBlackTree
```
import (
"fmt"
rbt "github.com/emirpasic/gods/trees/redblacktree"
)
func main() {
tree := rbt.NewWithIntComparator() // RedBlackTree
tree.Put(1, "x") // 1->x
tree.Put(2, "b") // 1->x, 2->b (in order)
tree.Put(1, "a") // 1->a, 2->b (in order, replacement)
tree.Put(3, "c") // 1->a, 2->b, 3->c (in order)
tree.Put(4, "d") // 1->a, 2->b, 3->c, 4->d (in order)
tree.Put(5, "e") // 1->a, 2->b, 3->c, 4->d, 5->e (in order)
tree.Put(6, "f") // 1->a, 2->b, 3->c, 4->d, 5->e, 6->f (in order)
fmt.Println(tree)
//
// RedBlackTree
// │ ┌── 6
// │ ┌── 5
// │ ┌── 4
// │ │ └── 3
// └── 2
// └── 1
_ = tree.Values() // []interface {}{"a", "b", "c", "d", "e", "f"} (in order)
_ = tree.Keys() // []interface {}{1, 2, 3, 4, 5, 6} (in order)
tree.Remove(2) // 1->a, 3->c, 4->d, 5->e, 6->f (in order)
fmt.Println(tree)
//
// RedBlackTree
// │ ┌── 6
// │ ┌── 5
// └── 4
// │ ┌── 3
// └── 1
tree.Clear() // empty
tree.Empty() // true
tree.Size() // 0
// Other:
tree.Left() // gets the left-most (min) node
tree.Right() // get the right-most (max) node
tree.Floor(1) // get the floor node
tree.Ceiling(1) // get the ceiling node
}
```
#### AVLTree
```
import (
"fmt"
avl "github.com/emirpasic/gods/trees/avltree"
)
func main() {
tree := avl.NewWithIntComparator() // empty(keys are of type int)
tree.Put(1, "x") // 1->x
tree.Put(2, "b") // 1->x, 2->b (in order)
tree.Put(1, "a") // 1->a, 2->b (in order, replacement)
tree.Put(3, "c") // 1->a, 2->b, 3->c (in order)
tree.Put(4, "d") // 1->a, 2->b, 3->c, 4->d (in order)
tree.Put(5, "e") // 1->a, 2->b, 3->c, 4->d, 5->e (in order)
tree.Put(6, "f") // 1->a, 2->b, 3->c, 4->d, 5->e, 6->f (in order)
fmt.Println(tree)
//
// AVLTree
// │ ┌── 6
// │ ┌── 5
// └── 4
// │ ┌── 3
// └── 2
// └── 1
_ = tree.Values() // []interface {}{"a", "b", "c", "d", "e", "f"} (in order)
_ = tree.Keys() // []interface {}{1, 2, 3, 4, 5, 6} (in order)
tree.Remove(2) // 1->a, 3->c, 4->d, 5->e, 6->f (in order)
fmt.Println(tree)
//
// AVLTree
// │ ┌── 6
// │ ┌── 5
// └── 4
// └── 3
// └── 1
tree.Clear() // empty
tree.Empty() // true
tree.Size() // 0
}
```
#### BTree
```
package main
import (
"fmt"
"github.com/emirpasic/gods/trees/btree"
)
func main() {
tree := btree.NewWithIntComparator(3) // empty (keys are of type int)
tree.Put(1, "x") // 1->x
tree.Put(2, "b") // 1->x, 2->b (in order)
tree.Put(1, "a") // 1->a, 2->b (in order, replacement)
tree.Put(3, "c") // 1->a, 2->b, 3->c (in order)
tree.Put(4, "d") // 1->a, 2->b, 3->c, 4->d (in order)
tree.Put(5, "e") // 1->a, 2->b, 3->c, 4->d, 5->e (in order)
tree.Put(6, "f") // 1->a, 2->b, 3->c, 4->d, 5->e, 6->f (in order)
tree.Put(7, "g") // 1->a, 2->b, 3->c, 4->d, 5->e, 6->f, 7->g (in order)
fmt.Println(tree)
// BTree
// 1
// 2
// 3
// 4
// 5
// 6
// 7
_ = tree.Values() // []interface {}{"a", "b", "c", "d", "e", "f", "g"} (in order)
_ = tree.Keys() // []interface {}{1, 2, 3, 4, 5, 6, 7} (in order)
tree.Remove(2) // 1->a, 3->c, 4->d, 5->e, 6->f, 7->g (in order)
fmt.Println(tree)
// BTree
// 1
// 3
// 4
// 5
// 6
// 7
tree.Clear() // empty
tree.Empty() // true
tree.Size() // 0
// Other:
tree.Height() // gets the height of the tree
tree.Left() // gets the left-most (min) node
tree.LeftKey() // get the left-most (min) node's key
tree.LeftValue() // get the left-most (min) node's value
tree.Right() // get the right-most (max) node
tree.RightKey() // get the right-most (max) node's key
tree.RightValue() // get the right-most (max) node's value
}
```
';