golang slice 一个易错点，今天我被卡了一个多小时

[EchoUtopia]

今天刷 leetcode 解决一个获取二叉树深度算法题的时候我对我的解法正确性很确定，但是结果就是不对，因为刚接触 leetcode，二叉树输入都是数组形式给出的，我不知道怎么构造出树来，不知道怎么调试，所以这个问题卡了我半天，真的不知所措。后面我用同样的 python 解法都没问题，肉眼排查了半天才找到疑点。于是自己写了下面的 demo，才知道问题出在哪。

那么问题来了，不执行以下代码代码你脑解出答案么？

demo：

package main

import "fmt"

func main() {
    a := []int{1}
    b := a
    a = a[:0]
    a = append(a, 2)
    a = append(a, 3)
    fmt.Println(a, b)
}

其实这个问题专门拿出来说可能比较容易避开这个坑，但是实际情况可能很容易被忽视掉。

有问题版本：

func maxDepth(root *TreeNode) int {
    if root == nil{
        return 0
    }
    depth := 0
    stack := []*TreeNode{root}
    for ;len(stack) != 0;{
        depth ++
        c := stack
        stack = stack[:0]
        for _, v := range c{
            if v.Left != nil{
                stack = append(stack, v.Left)
            }
            if v.Right != nil{
                stack = append(stack, v.Right)
            }
        }
    }
    return depth
}

正确版本：

func maxDepth(root *TreeNode) int {
    if root == nil{
        return 0
    }
    depth := 0
    stack := []*TreeNode{root}
    for ;len(stack) != 0;{
        depth ++
        nxtSt := make([]*TreeNode, 0)
        for _, v := range stack{
            if v.Left != nil{
                nxtSt = append(nxtSt, v.Left)
            }
            if v.Right != nil{
                nxtSt = append(nxtSt, v.Right)
            }
        }
        stack = nxtSt
    }
    return depth
}

希望能帮到同样是 golang 新手的你^_^

[zjlletian]

的确受教了，golang 的 slice 在内存中不光是连续的数据，而且是有保存长度的，append 到 a，但 b 的长度还是 1

[Mitt]

应该是切片后虽然 len 为 0 但地址一样且有足够空间导致的吧

[oovveeaarr]

https://golang.org/pkg/builtin/#append

The append built-in function appends elements to the end of a slice. If it has sufficient capacity, the destination is resliced to accommodate the new elements. If it does not, a new underlying array will be allocated. Append returns the updated slice. It is therefore necessary to store the result of append, often in the variable holding the slice itself:
巴拉巴拉，append 会返回更新过的 slice。所以有必要存储 append 返回的结果，通常我们会使用之前保存这个 slice 的变量本身来保存。

的确算是半个坑吧，不过我个人的话可能 LZ 不说可能没什么机会遇到。
我个人是想 append 都有要求重新赋值操作了，就潜意识认为肯定返回的内容和之前的内容不一样，就不会做这种骚操作了。

[honestyccc]

a 在第二次 append 时候由于切片容量不够了，所以 append 实际是返回一个新的切片

[donething]

这个问题，《 Go 实战》里讲过很清楚。切片后仍然共享内存，只有在 append()后容量不足，才会重新开辟内存。所以切片时指定容量非常重要，如 a=a[0:0:0]

[crayontxx]

这个 Go Blog 上说过
https://blog.golang.org/go-slices-usage-and-internals
简单的说需要把 slice 看成这样的一个 struct
{
data *T
cap, len int
}
上面的其他文章也是值得看的

[EchoUtopia]

@donething @Mitt @oovveeaarr @honestyccc @crayontxx 主要以前用 python 经常这样用，所以这个问题被我给忽视掉了，所以总结起来就是拷贝 slice 最好用 copy 函数， 否则要谨慎，因为如果没扩容就会两个 slice 都会被影响

[zarte]

还是觉得像其他语言那样比较好，默认创建新变量，要引用的时候手动赋值地址。

[EchoUtopia]

@zarte #8 如果你用数组，而不是 slice，那就跟你说的一样了

[xrlin]

其实就是底层实现的内存分配问题，一开始我也有点懵，后来了解了实现后还是挺好理解的，反正需要修改到值的时候要慎重，当时还专门写了笔记记录 slice 和数组各种可能遇到的问题
https://xrlin.github.io/Golang%E4%B8%AD%E7%9A%84%E6%95%B0%E7%BB%84%E4%B8%8ESlice/

[icexin]

go 里面的 slice 是一个 descriptor 结构，包含 ptr, len, cap 三个字段，切片只是修改 len 和 cap，时间复杂度为 O(1)。
python 的 slice 是一次新建一个数组再拷贝的操作，时间复杂度为 O(n)。两者设计理念不一样。