go标准库-Container

oublie included in Golang

2023-02-01 1192 words 3 minutes

Contents

go语言中文网

godoc

go语言中文网有很多文档缺少内容比如string.Builder就没有，godoc绝对详尽，推荐阅读godoc

heap

type Interface interface

heap中的参数，需要实现5个方法，Less(i,j int)bool，Swap(i,j int)，Len()int，Push(x interface{})和Pop()interface{}方法，通常用数组或切片

常见使用见labuladong第一章

常用函数

func Init(h Interface)：初始化，清空堆
func Push(h Interface, x interface{})：添加元素
func Pop(h Interface) interface{}：弹出堆顶元素
func Remove(h Interface, i int) interface{}：删除第i个元素
func Fix(h Interface, i int)：修改第i个元素后，调用该函数修复堆

使用sort.IntSlice实现优先队列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


type PriorityQueue struct {
	sort.IntSlice
}

func (h *PriorityQueue) Push(x interface{}) {
	h.IntSlice = append(h.IntSlice, x.(int))
}

func (h *PriorityQueue) Pop() interface{} {
	l := len(h.IntSlice)
	ret := h.IntSlice[l-1]
	h.IntSlice = h.IntSlice[:l-1]
	return ret
}

func (h *PriorityQueue) HPush(x int) { heap.Push(h, x) }

func (h *PriorityQueue) HPop() int { return heap.Pop(h).(int) }

list

list是封装好的双向链表

有两个结构体，Element和List

type Element struct

1
2
3
4
5


type Element struct {
    // 元素保管的值
    Value interface{}
    // 内含隐藏或非导出字段
}

变量

Value interface{}

方法

func (e *Element) Next() *Element:获取后一个元素
func (e *Element) Prev() *Element：获取前一个元素

type List struct

List代表一个双向链表

func New() *List：创建一个双向链表
func (l *List) Init() *List：清空链表
func (l *List) Len() int：链表中的元素个数，O(1)时间复杂度
func (l *List) Front() *Element：返回第一个元素或nil
func (l *List) Back() *Element：返回最后一个元素或nil
func (l *List) PushFront(v interface{}) *Element：将v插入队头并返回生成的Element
func (l *List) PushFrontList(other *List)：将other链表的拷贝插入队头
func (l *List) PushBack(v interface{}) *Element：将v插入队尾并返回生成的Element
func (l *List) PushBackList(other *List)：将other链表的拷贝插入队尾
func (l *List) InsertBefore(v interface{}, mark *Element) *Element：将v插入mark的前面
func (l *List) InsertAfter(v interface{}, mark *Element) *Element：将v插入mark的后面
func (l *List) MoveToFront(e *Element)：将e放到队头
func (l *List) MoveToBack(e *Element)：将e放到队尾
func (l *List) MoveBefore(e, mark *Element)：将e放到mark前面
func (l *List) MoveAfter(e, mark *Element)：将e放到mark后面
func (l *List) Remove(e *Element) interface{}：移除e并返回e.Value

ring

type Ring struct

Ring代表环形链表的一个元素

变量

Value interface{} ：获取值

函数

func New(n int) *Ring：创建具有n个元素的环形链表

方法

func (r *Ring) Len() int：环形链表元素个数，O(n)
func (r *Ring) Next() *Ring：后一个元素
func (r *Ring) Prev() *Ring：前一个元素
func (r *Ring) Move(n int) *Ring：移动n个位置（n>=0向前移动，n<0向后移动）后的元素
func (r *Ring) Link(s *Ring) *Ring：Link连接r和s，并返回r原本的后继元素r.Next()
func (r *Ring) Unlink(n int) *Ring：删除链表中n % r.Len()个元素，返回删除的元素构成的链表
func (r *Ring) Do(f func(interface{}))：对链表的每一个元素都执行f（正向顺序）