由于目前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))
}
}
来自 管理员在2009年8月13日编辑了该文章文章。