A Go slice is a descriptor of an array segment, with three fields:
I think part of the misconception that “slices are pointers” arises from the fact that a slice contains a pointer to a value in its underlying array.
Here are two examples where we need slice pointers.
One common idiom is to use a type, based on a slice, as a method receiver, as with a Heap. As with any receiver whose underlying value is modified as our program runs, we’ll use pointer receivers in our Push() and Pop() methods:
1type intHeap []int
2
3func (h intHeap) Len() int {
4 return len(h)
5}
6func (h intHeap) Less(i, j int) bool {
7 return h[i] < h[j]
8}
9func (h intHeap) Swap(i, j int) {
10 h[i], h[j] = h[j], h[i]
11}
12func (h *intHeap) Push(a any) {
13 *h = append(*h, a.(int))
14}
15func (h *intHeap) Pop() any {
16 old := *h // grab h's value, assign it to old
17 n := len(old)
18 x := old[n-1]
19 *h = old[:n-1] // assign truncated old to *h
20 return x
21}
22
23func main() {
24// create, initialize, use your heap here
25 ...Here’s another example. This function performs inorder traversal of a binary tree. If we implement an inline inOrder function, we can pass our output tracking slice as a value, because our output slice is in the scope of our inOrder function:
1func inorderTraversal(root *TreeNode) []int {
2 output := []int{}
3 var inOrder func(t *TreeNode)
4 inOrder = func(t *TreeNode) {
5 if t == nil {
6 return
7 }
8 inOrder(t.Left)
9 output = append(output, t.Val)
10 inOrder(t.Right)
11 }
12 inOrder(root)
13 return output
14} 1n := &TreeNode{Val: 1}
2n.Right = &TreeNode{Val: 2}
3n.Right.Left = &TreeNode{Val: 3}
4
5 1
6 / \
72 3
8
9fmt.Println(inOrderTraversal(n))
10
11> [2 1 3]Now, let’s move our inOrder function into a named function:
1func inorderTraversal(root *TreeNode) []int {
2 output := []int{}
3 inOrder(output, root)
4 return output
5}
6
7func inOrder(output []int, t *TreeNode) {
8 if t == nil {
9 return
10 }
11 inOrder(output, t.Left)
12 output = append(output, t.Val)
13 inOrder(output, t.Right)
14}
15
16fmt.Println(inOrderTraversal(n))
17
18> [] // should be [2 1 3]
Go passes function params by value. In the above code, a copy of output is passed to our inOrder function. If “slices are pointers”, output should be filled with the right values. But it’s not.
We make our code work by passing a pointer to our output []int slice into our inOrder function:
1func inorderTraversal(root *TreeNode) []int {
2 output := []int{}
3 inOrder(&output, root) // pass &output
4 return output
5}
6
7func inOrder(output *[]int, t *TreeNode) {
8 if t == nil {
9 return
10 }
11 inOrder(output, t.Left)
12 *output = append(*output, t.Val)
13 inOrder(output, t.Right)
14}
15
16fmt.Println(inOrderTraversal(n))
17
18> [2 1 3]Here, we’re appending an []int slice to our [][]int output. Because our []int slice is updated during the lifetime of our program, the output might not be what we expect:
1func main() {
2 res := combinationSum([]int{2, 3, 6, 7}, 7)
3 fmt.Println(res)
4}
5
6func combinationSum(candidates []int, target int) [][]int {
7 output := [][]int{}
8
9 bt(&output, []int{}, candidates, 0, target)
10 return output
11}
12
13func bt(output *[][]int, curr, candidates []int, idx, target int) {
14 if idx > len(candidates) || target < 0 {
15 return
16 }
17
18 if target == 0 {
19 fmt.Println(curr)
20 *output = append(*output, curr)
21 return
22 }
23
24 for i := idx; i < len(candidates); i++ {
25 curr = append(curr, candidates[i])
26 bt(output, curr, candidates, i, target-candidates[i])
27 curr = curr[:len(curr)-1]
28 }
29 return
30}1// we print out the correct results from iside our bt function ...
2> [2 2 3]
3> [7]1// but our output is wrong:
2> [[2 2 7] [7]]This is because we’re pushing our curr slice onto our output slice, then we’re changing the value of curr’s underlying array.
We can fix this using copy:
1func bt(output *[][]int, curr, candidates []int, idx, target int) {
2 if idx > len(candidates) || target < 0 {
3 return
4 }
5
6 if target == 0 {
7 fmt.Println(curr)
8 cp := make([]int, len(curr))
9 copy(cp, curr)
10 *output = append(*output, cp) // push cp onto output
11 return
12 }
13
14 for i := idx; i < len(candidates); i++ {
15 curr = append(curr, candidates[i])
16 bt(output, curr, candidates, i, target-candidates[i])
17 curr = curr[:len(curr)-1]
18 }
19 return
20}1$ [2 2 3]
2$ [7]
3$ [[2 2 3] [7]] // output matches what we print from inside our bt function
Where we copy a slice of slices, we’re copying only the pointer to the underlying array of slices; we’re not copying each member slice.
Let’s make a 2d 3 x 2 slice:
12dSlice := make([][]int, 3)So far, we are creating a slice that points to an underlying array of length 3, of nil slices.
1for i := range 2dSlice {
2 curr := make([]int, 2)
3 2dSlice = append(2dSlice, curr)
4}Now we have a slice that points to an underlying array of length 3, of []int slices, each of length 2. If we copy our 2dSlice into a new slice, the new slice will contain slices that point to the same arrays as 2dSlice’s. This can lead to subtle bugs that might go unnoticed for some time, depending on how functions get called over time.
Since this code is long, I’ve included the fix in commented-out code in the Rotate2d function:
1func main() {
2 inputSl := [][]int{
3 {1,2,3},
4 {4,5,6},
5 }
6 fmt.Println("---- orig")
7 Print2dSl(inputSl)
8 fmt.Println("---- transposed")
9 transposed := Transpose2d(inputSl)
10 Print2dSl(transposed)
11 fmt.Println("---- twoSeventy")
12 twoSeventy := Rotate2d(270, inputSl)
13 Print2dSl(twoSeventy)
14 fmt.Println("---- ninety")
15 ninety := Rotate2d(90, inputSl)
16 Print2dSl(ninety)
17 oneEighty := Rotate2d(180, inputSl)
18 fmt.Println("---- oneEighty")
19 Print2dSl(oneEighty)
20 twoSeventy = Rotate2d(270, inputSl)
21 fmt.Println("---- twoSeventy")
22 Print2dSl(twoSeventy)
23}
24
25func Rotate2d[T any](deg int, inputSl [][]T) [][]T {
26 var transpose func(sl [][]T) [][]T
27 transpose = func(sl [][]T) [][]T {
28 output := make([][]T, len(sl[0]))
29 for i := range output {
30 output[i] = make([]T, len(sl))
31 }
32 for i := 0; i < len(sl); i++ {
33 for j := 0; j < len(sl[0]); j++ {
34 output[j][i] = sl[i][j]
35 }
36 }
37 return output
38 }
39
40 var swapColumns func(sl [][]T)
41 swapColumns = func(sl [][]T) {
42 for row := 0; row < len(sl); row++ {
43 for l, r := 0, len(sl[0])-1; l < r; l, r = l+1, r-1 {
44 sl[row][l], sl[row][r] = sl[row][r], sl[row][l]
45 }
46 }
47 }
48 var swapRows func(sl [][]T)
49 swapRows = func(sl [][]T) {
50 for top, bottom := 0, len(sl)-1; top < bottom; top, bottom = top+1, bottom-1 {
51 sl[top], sl[bottom] = sl[bottom], sl[top]
52 }
53 }
54
55 if deg == 0 {
56 return inputSl
57 } else if deg == 90 {
58 output := transpose(inputSl)
59 swapColumns(output)
60 return output
61 } else if deg == 180 {
62 output := make([][]T, len(inputSl))
63 for i := range output {
64 output[i] = make([]T, len(inputSl[0]))
65 }
66 //for i := 0; i < len(inputSl); i++ {
67 // copy(output[i], inputSl[i])
68 //}
69 copy(output, inputSl) // wrong!!
70 swapRows(output)
71 swapColumns(output)
72 return output
73 } else if deg == 270 {
74 output := transpose(inputSl)
75 swapRows(output)
76 return output
77 } else {
78 panic("deg must be 0, 90, 180 or 270")
79 }
80}
81
82func Transpose2d[T any](sl [][]T) [][]T {
83 output := make([][]T, len(sl[0]))
84 for i := range output {
85 output[i] = make([]T, len(sl))
86 }
87 for i := 0; i < len(sl); i++ {
88 for j := 0; j < len(sl[0]); j++ {
89 output[j][i] = sl[i][j]
90 }
91 }
92 return output
93}
94
95func Print2dSl[T any](sl [][]T) {
96 for _, ln := range sl {
97 fmt.Println(ln)
98 }
99}Note that the first time we call this code, twoSeventy returns the correct answer, but the second time, it does not.
1> ---- orig
2> [1 2 3]
3> [4 5 6]
4> ---- transposed
5> [1 4]
6> [2 5]
7> [3 6]
8> ---- twoSeventy
9> [3 6]
10> [2 5]
11> [1 4]
12> ---- ninety
13> [4 1]
14> [5 2]
15> [6 3]
16> ---- oneEighty
17> [6 5 4]
18> [3 2 1]
19> ---- twoSeventy
20> [1 4]
21> [2 5]
22> [3 6]This may not seem intuitive. How can the state of our function survive individual calls to it? This is because when we call Rotate2d(180, inputSl), we are copying our inputSl into a new output slice whose members remain pointers to the same underlying arrays as inputSl.
I imagine this bug is fairly prevalent in the wild, because, as we see, if Rotate2d(270, inputSl) is called independently of Rotate2d(180, inputSl), it won’t create problems. But as called above, it will.
As you can see in the commented-out code, the fix is to copy each slice inside inputSl to each row of output.