How slices grow

Lesson 7 of 24 · Part 2 · Data · about 15 minutes

In the last lesson a slice worked like a row of boxes that can grow. This lesson looks inside: a slice doesn't hold the elements itself. They live in an array behind it. The slice remembers three things: where in the array it starts, how many elements it has now (len), and how many the array has room for (cap, the capacity).

1package main2 3import "fmt"4 5func main() {6	s := make([]int, 3, 5)7	fmt.Println(s, len(s), cap(s))8	s = append(s, 7)9	fmt.Println(s, len(s), cap(s))10}

[0 0 0] 3 5
[0 0 0 7] 4 5

make([]int, 3, 5) builds an array with room for 5, and the slice uses the first 3. After one append the length is 4 and the capacity is still 5: the array already had a free box.

len and cap

len is how many elements you can read and write by index; cap is how many boxes the array has, counting from the start of the slice. Indexes only go up to len-1, even if there is free capacity:

1package main2 3import "fmt"4 5func main() {6	s := make([]int, 2, 10)7	fmt.Println(len(s), cap(s))8	s[1] = 59	s[2] = 910	fmt.Println(s)11}

2 10
panic: runtime error: index out of range [2] with length 2

goroutine 1 [running]:
main.main(...)
	/tmp/sandbox/prog.go:9 +0x1d
exit status 2

index out of range [2] with length 2: the error talks about the length, not the capacity. You reach the free boxes with append.

Moving when it's full

When you append and the array has a free box, the element goes there. When it's full, Go builds a bigger new array, moves the old elements over, and then adds the new one. Add one at a time and watch the capacity:

1package main2 3import "fmt"4 5func main() {6	var nums []int7	for i := range 10 {8		nums = append(nums, i)9		fmt.Println("len", len(nums), "cap", cap(nums))10	}11}

len 1 cap 1
len 2 cap 2
len 3 cap 4
len 4 cap 4
len 5 cap 8
len 6 cap 8
len 7 cap 8
len 8 cap 8
len 9 cap 16
len 10 cap 16

The capacity goes 1, 2, 4, 8, 16: when it's full it roughly doubles (more slowly once the slice is long). So most appends don't move anything, and they are fast. Press Step and watch the boxes: on the steps where the capacity changes, the slice moves to a new row of boxes.

After a move, they're separate

Because of these moves, you must always assign the result of append. And because of them, a and b below no longer share an array:

1package main2 3import "fmt"4 5func main() {6	a := []int{1, 2, 3}7	b := append(a, 4)8	b[0] = 1009	fmt.Println("a:", a, cap(a))10	fmt.Println("b:", b, cap(b))11}

a: [1 2 3] 3
b: [100 2 3 4] 6

a has capacity 3 and is full, so append moves the elements to a new array (capacity 6), and b uses the new one. Changing b[0] doesn't touch a. Press Step and watch b := append(a, 4): b gets a new row of boxes.

Slices sharing one array

Slicing with s[a:b] doesn't copy anything: the new slice points into the same array. Change it, and the original changes too:

1package main2 3import "fmt"4 5func main() {6	scores := []int{90, 75, 88, 62}7	firstTwo := scores[0:2]8	firstTwo[1] = 809	fmt.Println("firstTwo:", firstTwo)10	fmt.Println("scores:", scores)11}

firstTwo: [90 80]
scores: [90 80 88 62]

firstTwo[1] and scores[1] are the same box. Press Step and see both slices pointing at one row of boxes.

Here is a common trap: when there is free capacity, append also writes into the shared array.

1package main2 3import "fmt"4 5func main() {6	base := make([]int, 3, 10)7	x := append(base, 1)8	y := append(base, 2)9	fmt.Println(x[3], y[3])10}

copy makes a real copy

For a copy that doesn't affect the original, make a slice of the same length, then copy the elements into it. copy(destination, source) returns how many it copied:

1package main2 3import "fmt"4 5func main() {6	prices := []int{12, 30, 8}7	backup := make([]int, len(prices))8	n := copy(backup, prices)9	prices[0] = 010	fmt.Println("Copied:", n)11	fmt.Println("prices:", prices)12	fmt.Println("backup:", backup)13}

Copied: 3
prices: [0 30 8]
backup: [12 30 8]

copy only copies as many as fit on both sides: if the destination has length 0, it copies nothing. So give make a long enough length.

Tip: slices.Clone(prices) makes a copy in one step; it needs import "slices".

Making room ahead of time

If you know roughly how many you'll add, use make([]int, 0, 100): length 0, capacity 100. Then keep calling append; up to 100 elements, nothing ever moves:

1package main2 3import "fmt"4 5func main() {6	orders := make([]int, 0, 100)7	for i := range 100 {8		orders = append(orders, i+1)9	}10	fmt.Println(len(orders), cap(orders))11	fmt.Println(orders[:5])12}

100 100
[1 2 3 4 5]

The length starts at 0, so you add with append, not by index.

The cap of a slice of a slice

s[a:b] has length b-a; its capacity runs from a to the end of the original array. So a slice cut from the middle can still "see" the boxes after it:

1package main2 3import "fmt"4 5func main() {6	week := []int{1, 2, 3, 4, 5, 6, 7}7	mid := week[2:4]8	fmt.Println(mid, len(mid), cap(mid))9	mid = append(mid, 0)10	fmt.Println(week)11}

[3 4] 2 5
[1 2 3 4 0 6 7]

mid has capacity 5 (indexes 2 to 6), so append doesn't move anything and changes week[4] directly. To keep it away from the boxes after it, write week[2:4:4]: the third number says where the capacity ends, so append moves to a new array.

Practice

Write the code, then press Check. A hint costs nothing; the answer is there when you need it.

[40 20 10] [50 30 20]
[89 5] [99 15]

1package main2 3import "fmt"4 5func discounted(prices []int) []int {6	for i := range prices {7		prices[i] -= 108	}9	return prices10}11 12func main() {13	a := []int{50, 30, 20}14	fmt.Println(discounted(a), a)15	b := []int{99, 15}16	fmt.Println(discounted(b), b)17}

5
8

1package main2 3import "fmt"4 5func moves(n int) int {6	var s []int7	count := 08	_ = s // a placeholder so s counts as used; delete it once the loop is in9	return count10}11 12func main() {13	fmt.Println(moves(10))14	fmt.Println(moves(100))15}

[milk bread apples]
[milk bread eggs]

1package main2 3import "fmt"4 5func main() {6	base := make([]string, 0, 5)7	base = append(base, "milk", "bread")8	anna := append(base, "apples")9	ben := append(base, "eggs")10	fmt.Println(anna)11	fmt.Println(ben)12}

What you learned

• A slice has an array behind it; len is how many elements you can use, and cap is how many boxes the array has from the start of the slice.
• append uses a free box if there is one; otherwise it moves to a bigger new array (for []int: capacity 1, 2, 4, 8, 16…). That's why you always assign its result.
• Slicing with s[a:b] doesn't copy: several slices can share one array, so changing one changes the other. With free capacity, append writes into the shared boxes too.
• copy(dst, src) copies elements, and dst must be maked long enough first; slices.Clone copies in one step.
• make([]int, 0, n) makes room ahead of time, so append doesn't move.
• The capacity of s[a:b] runs from a to the end of the array; s[a:b:c] stops it at index c, so the capacity is c-a.