细节总结

循环遍历

在使用 for 循环某个集合的时候，会复用过程中承载值的变量，所以在涉及指针的时候要提起注意。

  1. a := make([]*int, 4)
  2. for i := 0; i < len(a); i++ {
  3.     a[i] = &i // i 始终是复用自最初变量，所以结果是a中所有值都是相同的i地址
  4. }
  1. func main() {
  2.     a := make([]*int, 4)
  3.     b := [...]int{1, 2, 3, 4}
  4.     for k, v := range b {
  5.         a[k] = &v // v 同样是复用自一个变量，所以结果也是a中所有值都是相同的v地址
  6.     }
  7. }

方法赋予

在 GO 中自定义了一个类型之后，可以给该类型赋予方法。被赋予方法的类型，就叫做接受者，接受者可以是值接受者，也可以是指针接受者。

  1. type T struct {
  2.      x int   
  3. }
  5. func (t T) Func1() { } // 值接受者
  6. func (t *T) Func2() { } // 指针接受者

这里就会出现一个疑惑，上述的方法最终是赋予给了该类型还是该类型的指针？先给出结论：在调用方法的时候，值类型和指针类型都可以调用指针接受者的方法和值接受者的方法，因为调用时的细节转换已经由编译器完成。仍然是上边的例子，可以如此调用：

  1. func main() {
  2.     t1 := T{x: 0} // 获取一个T类型值
  3.     t1.Func1()
  4.     t1.Func2() // 编译器转换成 (&t1).Func2()
  6.     t2 := &T{x: 10} // 获取一个T类型指针
  7.     t2.Func1() // 编译器转换成 (&t2).Func1()
  8.     t2.Func2()
  9. }

这两者的区别在于是否会真正改动接受者的字段。

类型 定义 行为
值接受者 func (t T) Func() {} 获取T类型的值拷贝，之后在函数中的操作都是对该副本进行，不会影响原值。
指针接受者 func (t *T) Func() {} 本质上也是获取一个值拷贝，但这个值是 *T 类型，也就是地址。所以之后的操作都会访问该地址，就会影响到原值。

容器

heap

结构分析

使用实例

小根堆，使用的时候需要实现 heap.Interface 接口，该接口定义了构造堆所必要的方法。

  1. // heap.Interface
  2. type Interface interface {
  3.     sort.Interface
  4.     Push(x interface{}) // add x as element Len()
  5.     Pop() interface{}   // remove and return element Len() - 1.
  6. }
  8. // sort.Interface
  9. type Interface interface {
  10.     Len() int
  11.     Less(i, j int) bool // 排序默认是升序，可看作返回true则i在j之前
  12.     Swap(i, j int)
  13. }

通过源码的分析可以知道：

  • heap 插入元素的过程是先调用用户的 Push 方法，接着通过将最后一个叶子上拉来维护堆性质，所以在实现 Push 方法时只需要在集合的最后添加元素；
  • 而 heap 弹出元素弹出的是堆顶元素，过程是先将堆顶与最后一个叶子互换位置，然后将新堆顶下拉来维护堆的性质，最后调用用户的 Pop 方法，所以在实现 Pop 方法的时候是删除集合的最后一个元素。

总而言之，在实现 Interface 接口时，Pop 和 Push 都针对集合的最后一个元素就好。

常用 API

  1. // h均为一个集合的 引用
  2. func Fix(h Interface, i int)
  3. func Init(h Interface)
  4. func Pop(h Interface) interface{}
  5. func Push(h Interface, x interface{})
  6. func Remove(h Interface, i int) interface{} // 返回被删除的元素
  7. type Interface

list

结构分析

节点可以是任意类型，使用示例

双向链表，其结构稍微与常见的双向链表不同，非常巧妙。链表的总体类型为 List，每一个元素类型为 Element

  1. type Element struct {
  2.     next, prev *Element
  3.     list *List            // 当前节点元素所属的链表
  4.     Value interface{}     // 节点值可以是任意类型
  5. }
  7. type List struct {
  8.     root Element // sentinel list element, only &root, root.prev, and root.next are used
  9.     len  int     // current list length excluding (this) sentinel element
  10. }

List 可以看作是整个链表的抽象代表，包含一个很巧妙的节点元素 root，root 既是双向链表的头部又是尾部：root.next 指向第一个元素，root.prev 指向最后一个元素。所以总体来看，链表是一个环形结构。
image.png
从 Element 的结构可以发现，其多了一个 list 字段指向所属链表。这个字段的作用是在删除某个节点时，快速判断节点是否属于链表，省去了不必要的遍历时间，提高删除的效率。

  1. func (l *List) Remove(e *Element) interface{} {
  2.     if e.list == l {
  3.         l.remove(e)
  4.     }
  5.     return e.Value
  6. }

常用 API

  1. func New() *List
  2. func (l *List) Back() *Element
  3. func (l *List) Front() *Element
  4. func (l *List) Init() *List
  5. func (l *List) InsertAfter(v interface{}, mark *Element) *Element
  6. func (l *List) InsertBefore(v interface{}, mark *Element) *Element
  7. func (l *List) Len() int
  8. func (l *List) MoveAfter(e, mark *Element)
  9. func (l *List) MoveBefore(e, mark *Element)
  10. func (l *List) MoveToBack(e *Element)
  11. func (l *List) MoveToFront(e *Element)
  12. func (l *List) PushBack(v interface{}) *Element
  13. func (l *List) PushBackList(other *List)
  14. func (l *List) PushFront(v interface{}) *Element
  15. func (l *List) PushFrontList(other *List)
  16. func (l *List) Remove(e *Element) interface{} // 返回节点的Value

字符串