golang 标准库 container/ring 及 container/heap

yujian0231 · · 5418 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

由于目前golang 没有提供泛型机制,所以通用容器实现基本和 c 类似,golang 用 interface{} 做转接, c 用 void * 转接。

ring 包实现循环双向链表:

type Ring struct   {    
   next, prev *Ring    		
   Value      interface{} 	
}

内部导出一个用户可以操作的Value 字段。

heap 包实现 binary heap :

type Interface interface {        
     sort.Interface
     Push(x interface{}) // add x as element Len()
     Pop() interface{}   // remove and return element Len() - 1.
}

heap.Interface 内嵌 sort.Interface, 提供了接口组合的好例子,只要客户的数据类型实现这五个方法,即可插入binary heap  中,进行相关操作(排序,优先队列等)。

package main

import (
	"container/heap"
	"container/ring"
	"fmt"
)

func josephus(n, m int) []int {
	var res []int
	ring := ring.New(n)
	ring.Value = 1
	for i, p := 2, ring.Next(); p != ring; i, p = i+1, p.Next() {
		p.Value = i
	}
	h := ring.Prev()
	for h != h.Next() {
		for i := 1; i < m; i++ {
			h = h.Next()
		}
		res = append(res, h.Unlink(1).Value.(int))
	}
	res = append(res, h.Value.(int))
	return res
}

type intHeap []int

func (h intHeap) Len() int           { return len(h) }
func (h intHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h intHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *intHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}
func (h *intHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func main() {
	fmt.Println(josephus(9, 5))
	h := &intHeap{10, 3, 9, 7, 2, 88, 31, 67}
	heap.Init(h)
	heap.Push(h, 1)
	for h.Len() > 0 {
		fmt.Printf("%d ", heap.Pop(h))
	}
}


本文来自:开源中国博客

感谢作者:yujian0231

查看原文:golang 标准库 container/ring 及 container/heap

入群交流(和以上内容无关):Go中文网 QQ 交流群:798786647 或加微信入微信群:274768166 备注:入群;关注公众号:Go语言中文网

5418 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传