Day09（MapAndContainer）

集合(map) 和容器(Container)

源码

Map

Map 是一种无序键值对的集合，通过 Key来检索数据，key 类似索引，指向数据值，可以使用 for迭代，但是 map是无序的，无法决定他的返回值顺序，这是因为 map 是使用 hash 来实现的

删除元素、判断是否存在

package main

import (
	"github.com/Cc360428/HelpPackage/UtilsHelp/logs"
)

func main() {
	m1 := map[string]string{
		"name1": "lcc",
		"name2": "Cc",
		"name3": "Cc360428"}
	logs.Info(m1)
	m2 := make(map[int]int)
	m2[1] = 11
	m2[2] = 22
	m2[3] = 33
	m2[4] = 44
	m2[5] = 55
	logs.Info(m2)
	delete(m2, 4)
	logs.Info(m2)
	if v, ok := m2[88]; !ok {
		// ok 存在返回true 反之 false
		logs.Info("check key no")
	} else {
		// 当不存在就返回默认值
		logs.Info("check  key is：", v)
	}
}

2020/04/25 10:30:05.829 [I] [map.go:12]  map[name1:lcc name2:Cc name3:Cc360428]
2020/04/25 10:30:05.858 [I] [map.go:19]  map[1:11 2:22 3:33 4:44 5:55]
2020/04/25 10:30:05.858 [I] [map.go:21]  map[1:11 2:22 3:33 5:55]
2020/04/25 10:30:05.858 [I] [map.go:24]  check key no

Container（heap、list、ring）

• 单链表结构

• 双链表结构与删除

  知道上一个下一个，删除时要告诉上一个下个删除

• 双向链表与环形链表

heap（堆）

源码文档

• heap 包提供了对任意类型（实现了 heap.Interface接口）的堆操作。（最小）堆是具有“每个节点都是以其为根的子树中最小值”属性的树。
• 树的最小元素为其根元素，索引 0的位置。
• heap是常用的实现优先队列的方法。要创建一个优先队列，实现一个具有使用（负的）优先级作为比较的依据的 Less 方法的 Heap 接口，如此一来可用 Push 添加项目而用 Pop 取出队列最高优先级的项目。
• 实现优先队列

package main

import (
	"container/heap"
	"fmt"
)

type Item struct {
	value    string // 优先级队列中的数据，可以是任意类型，这里使用string
	priority int    // 优先级队列中节点的优先级
	index    int    // index是该节点在堆中的位置
}

// 优先级队列需要实现heap的interface
type PriorityQueue []*Item

// 绑定Len方法
func (pq PriorityQueue) Len() int {
	return len(pq)
}

// 绑定Less方法，这里用的是小于号，生成的是小根堆
func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}

// 绑定swap方法
func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index, pq[j].index = i, j
}

// 绑定put方法，将index置为-1是为了标识该数据已经出了优先级队列了
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	item.index = -1
	return item
}

// 绑定push方法
func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

// 更新修改了优先级和值的item在优先级队列中的位置
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
	item.value = value
	item.priority = priority
	heap.Fix(pq, item.index)
}

func main() {
	// 创建节点并设计他们的优先级
	items := map[string]int{"二毛": 5, "张三": 3, "狗蛋": 9}
	i := 0
	pq := make(PriorityQueue, len(items)) // 创建优先级队列，并初始化
	for k, v := range items {             // 将节点放到优先级队列中
		pq[i] = &Item{
			value:    k,
			priority: v,
			index:    i}
		i++
	}
	heap.Init(&pq) // 初始化堆
	item := &Item{ // 创建一个item
		value:    "李四",
		priority: 1,
	}
	heap.Push(&pq, item)           // 入优先级队列
	pq.update(item, item.value, 6) // 更新item的优先级
	for len(pq) > 0 {
		item := heap.Pop(&pq).(*Item)
		fmt.Printf("%.2d:%s index:%.2d\n", item.priority, item.value, item.index)
	}
}

03:张三 index:-01
05:二毛 index:-01
06:李四 index:-01
09:狗蛋 index:-01

list（双向链表）

源码文档

双向链表 ，Element 元素是链接列表的元素

• MoveBefore：给定的元素移动到另一个元素的前面
• MoveAfter：给定的元素移动到另一个元素的后面
• MoveToFront：把给定的元素移动到链表的最前端
• MoveToBack：把给定的元素移动到链表的最后端
• Front：获取链表中最前端
• Back：获取链表中最后端
• InsertBefore：指定的元素之前插入新元素
• InsertAfter：指定的元素之后插入新元素
• PushFront：用于在链表的最前端插入新元素。
• PushBack：用于在链表的最前端插入新元素。

package main

import (
	"container/list"
	"fmt"
	"github.com/Cc360428/HelpPackage/UtilsHelp/logs"
)

func main() {
	listType := list.New()
	// 尾部添加
	listType.PushFront("lcc")
	listType.PushFront(18)
	// 头部添加
	listType.PushFront("hello")
	for e := listType.Front(); e != nil; e = e.Next() {
		fmt.Print(e.Value, " ")
	}
	fmt.Print("\n")
	for e := listType.Front(); e != nil; e = e.Next() {
		if e.Value == "hello" {
			// 指定元素之后插入新元素
			listType.InsertAfter("World", e)
		}

		if e.Value == "lcc" {
			// 指定元素之前插入新元素
			listType.InsertBefore("Cc", e)
		}
	}
	for e := listType.Front(); e != nil; e = e.Next() {
		fmt.Print(e.Value, " ")
	}
	fmt.Print("\n")
	for e := listType.Back(); e != nil; e = e.Next() {
		fmt.Print(e.Value)
	}
	// 最前元素
	logs.Info(listType.Front().Value)
	// 最后元素
	logs.Info(listType.Back().Value)
	for e := listType.Front(); e != nil; e = e.Next() {
		if e.Value == "lcc" {
			// 指定元素之前插入新元素
			listType.MoveBefore(e, e)
		}
	}
}

hello 18 lcc
hello World 18 Cc lcc
lcc2020/04/25 16:16:21.548 [I] [list.go:39]  hello
2020/04/25 16:16:21.577 [I] [list.go:41]  lcc

ring（环）

源码文档

ring 实现了环形链表的操作

package main

import (
	"container/ring"
	"github.com/Cc360428/HelpPackage/UtilsHelp/logs"
)

func main() {
	ring1 := ring.New(3)
	for i := 1; i <= 3; i++ {
		ring1.Value = i
		ring1 = ring1.Next()
	}
	ring2 := ring.New(3)
	for i := 0; i <= ring2.Len(); i++ {
		ring2.Value = i
		ring2 = ring2.Next()
	}
	r := ring1.Link(ring2)
	logs.Info(r.Len())

	r.Do(func(p interface{}) {
		logs.Info(p.(int))
	})
	logs.Info(r.Value)
	logs.Info(r.Next().Value)
	logs.Info(r.Prev().Value)
	// ring 的遍历
	for p := r.Next(); p != r; p = p.Next() {
		logs.Info(p.Value.(int))
	}
}

2020/04/25 16:15:42.181 [I] [ring.go:20]  6
2020/04/25 16:15:42.216 [I] [ring.go:23]  2
2020/04/25 16:15:42.216 [I] [ring.go:23]  3
2020/04/25 16:15:42.216 [I] [ring.go:23]  1
2020/04/25 16:15:42.216 [I] [ring.go:23]  1
2020/04/25 16:15:42.216 [I] [ring.go:23]  2
2020/04/25 16:15:42.216 [I] [ring.go:23]  3
2020/04/25 16:15:42.216 [I] [ring.go:25]  2
2020/04/25 16:15:42.216 [I] [ring.go:26]  3
2020/04/25 16:15:42.216 [I] [ring.go:27]  3
2020/04/25 16:15:42.216 [I] [ring.go:30]  3
2020/04/25 16:15:42.216 [I] [ring.go:30]  1
2020/04/25 16:15:42.217 [I] [ring.go:30]  1
2020/04/25 16:15:42.218 [I] [ring.go:30]  2
2020/04/25 16:15:42.218 [I] [ring.go:30]  3