Slices represent variable-length sequences
whose elements all have the same type.
A slice type is written []T
, where the elements have
type T
; it looks like an array type without a size.
Arrays and slices are intimately connected.
A slice is a lightweight data structure that gives access to
a subsequence (or perhaps all) of the elements of an array,
which is known as the slice’s underlying array.
A slice has three components: a pointer, a length, and a
capacity.
The pointer points to the first element of the array that is
reachable through the slice, which is not necessarily the array’s
first element.
The length is the number of slice elements; it can’t exceed
the capacity, which is usually the number of elements between the
start of the slice and the end of the underlying array.
The built-in functions len
and cap
return those values.
Multiple slices can share the same underlying array and may refer to overlapping parts of that array. Figure 4.1 shows an array of strings for the months of the year, and two overlapping slices of it. The array is declared as
months := [...]string{1: "January", /* ... */, 12: "December"}
so January is months[1]
and December is months[12]
.
Ordinarily, the array element at index 0 would contain the first
value, but because months are always numbered from 1, we can leave it
out of the declaration and it will be initialized to an empty string.
The slice operator s[i:j]
,
where 0 ≤ i
≤ j
≤ cap(s)
,
creates a
new slice that refers to elements i
through j-1
of the sequence s
,
which may be an array variable, a pointer to an array, or another
slice. The resulting slice has j-i
elements.
If i
is omitted, it’s 0, and if j
is omitted, it’s
len(s)
.
Thus the slice months[1:13]
refers to the whole range of valid months, as does
the slice months[1:]
; the slice months[:]
refers to the whole array.
Let’s define overlapping slices for the second quarter and the
northern summer:
Q2 := months[4:7] summer := months[6:9] fmt.Println(Q2) // ["April" "May" "June"] fmt.Println(summer) // ["June" "July" "August"]
June is included in each and is the sole output of this (inefficient) test for common elements:
for _, s := range summer { for _, q := range Q2 { if s == q { fmt.Printf("%s appears in both ", s) } } }
Slicing beyond cap(s)
causes a panic, but slicing beyond
len(s)
extends the slice,
so the result may be longer than the original:
fmt.Println(summer[:20]) // panic: out of range endlessSummer := summer[:5] // extend a slice (within capacity) fmt.Println(endlessSummer) // "[June July August September October]"
As an aside, note the similarity of the substring operation on strings
to the slice operator on []byte
slices. Both are written
x[m:n]
, and both return a subsequence of the original bytes,
sharing the underlying representation so that both operations take constant
time. The expression x[m:n]
yields a string if x
is a string,
or a []byte
if x
is a []byte
.
Since a slice contains a pointer to an element of an array, passing a
slice to a function permits the function to modify the underlying
array elements.
In other words, copying a slice creates an alias (§2.3.2) for the underlying array.
The function reverse
reverses the elements of an []int
slice in place,
and it may be applied to slices of any length.
// reverse reverses a slice of ints in place. func reverse(s []int) { for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 { s[i], s[j] = s[j], s[i] } }
Here we reverse the
whole array a
:
a := [...]int{0, 1, 2, 3, 4, 5} reverse(a[:]) fmt.Println(a) // "[5 4 3 2 1 0]"
A simple way to rotate a slice left by n elements is to apply the
reverse
function three times, first to the leading n
elements, then to the remaining elements, and finally to the whole
slice. (To rotate to the right, make the third call first.)
s := []int{0, 1, 2, 3, 4, 5} // Rotate s left by two positions. reverse(s[:2]) reverse(s[2:]) reverse(s) fmt.Println(s) // "[2 3 4 5 0 1]"
Notice how the expression that initializes the slice s
differs
from that for the array a
.
A slice literal looks like an array literal, a sequence of values
separated by commas and surrounded by braces, but the size is not
given. This implicitly creates an array variable of the right size and
yields a slice that points to it.
As with array literals, slice literals may specify the values in order, or
give their indices explicitly, or use a mix of the two styles.
Unlike arrays, slices are not comparable, so we cannot use ==
to
test whether two slices contain the same elements. The standard library
provides the highly optimized bytes.Equal
function for comparing two
slices of bytes ([]byte
), but for other types of slice,
we must do the comparison ourselves:
func equal(x, y []string) bool { if len(x) != len(y) { return false } for i := range x { if x[i] != y[i] { return false } } return true }
Given how natural this “deep” equality test is,
and that it is no more costly at run time than
the ==
operator for arrays of strings,
it may be puzzling that slice comparisons do not also work this way.
There are two reasons why deep equivalence is problematic.
First, unlike array elements, the elements of a slice are indirect,
making it possible for a slice to contain itself.
Although there are ways to deal with such cases,
none is simple, efficient, and most importantly, obvious.
Second, because slice elements are indirect, a fixed slice value may
contain different elements at different times as the contents of the
underlying array are modified.
Because a hash table such as Go’s map type makes only shallow copies
of its keys, it requires that equality for each key remain the same
throughout the lifetime of the hash table.
Deep equivalence would thus make slices unsuitable for use
as map keys.
For reference types like pointers and channels, the ==
operator
tests reference identity,
that is, whether the two entities refer to the same thing.
An analogous “shallow” equality test for slices could be useful, and
it would solve the problem with maps, but the inconsistent treatment
of slices and arrays by the ==
operator would be confusing.
The safest choice is to disallow slice comparisons altogether.
The only legal slice comparison is against nil
, as in
if summer == nil { /* ... */ }
The zero value of a slice type is nil
.
A nil slice has no underlying array.
The nil slice has length and capacity zero, but there are also non-nil
slices of length and capacity zero, such as []int{}
or
make([]int, 3)[3:]
.
As with any type that can have nil values, the nil value of a particular
slice type can be written using a conversion expression such as
[]int(nil)
.
var s []int // len(s) == 0, s == nil s = nil // len(s) == 0, s == nil s = []int(nil) // len(s) == 0, s == nil s = []int{} // len(s) == 0, s != nil
So, if you need to test whether a slice is empty, use len(s) == 0
,
not s == nil
.
Other than comparing equal to nil
, a nil slice behaves like any other
zero-length slice; reverse(nil)
is perfectly safe, for example.
Unless clearly documented to the contrary, Go functions should treat
all zero-length slices the same way, whether nil or non-nil.
The built-in function make
creates
a slice of a specified element type, length, and capacity.
The capacity argument may be omitted, in which case the capacity
equals the length.
make([]T, len) make([]T, len, cap) // same as make([]T, cap)[:len]
Under the hood, make
creates an unnamed array variable
and returns a slice of it; the array is accessible
only through the returned slice.
In the first form, the slice is a view of the entire array.
In the second, the slice is a view of only the array’s first
len
elements, but its capacity includes the entire array.
The additional elements are set aside for future growth.
append
Function
The built-in append
function appends items to slices:
var runes []rune for _, r := range "Hello, " { runes = append(runes, r) } fmt.Printf("%q ", runes) // "['H' 'e' 'l' 'l' 'o' ',' ' ' '' '']"
The loop uses append
to build the slice of nine runes
encoded by the string literal, although this specific problem is more
conveniently solved by using the built-in conversion []rune("Hello, ")
.
The append
function is crucial to understanding how slices work, so
let’s take a look at what is going on. Here’s a version called
appendInt
that is specialized for []int
slices:
func appendInt(x []int, y int) []int { var z []int zlen := len(x) + 1 if zlen <= cap(x) { // There is room to grow. Extend the slice. z = x[:zlen] } else { // There is insufficient space. Allocate a new array. // Grow by doubling, for amortized linear complexity. zcap := zlen if zcap < 2*len(x) { zcap = 2 * len(x) } z = make([]int, zlen, zcap) copy(z, x) // a built-in function; see text } z[len(x)] = y return z }
Each call to appendInt
must check whether the slice has
sufficient capacity to hold the new elements in the existing array.
If so, it extends the slice by defining a larger slice (still within the original array),
copies the element y
into the new space, and returns
the slice. The input x
and the result z
share the same
underlying array.
If there is insufficient space for growth, appendInt
must allocate a
new array big enough to hold the result, copy the values from x
into
it, then append the new element y
. The result z
now refers to a
different underlying array than the array that x
refers to.
It would be straightforward to copy the elements with explicit loops,
but it’s easier to use the built-in function copy
, which copies
elements from one slice to another of the same type.
Its first argument is the destination and its second is the source,
resembling the order of operands in an assignment like dst = src
.
The slices may refer to the same underlying array; they may even
overlap.
Although we don’t use it here, copy
returns the number
of elements actually copied, which is the smaller of the two slice
lengths, so there is no danger of running off the end or
overwriting something out of range.
For efficiency, the new array is usually somewhat larger than the
minimum needed to hold x
and y
. Expanding the array
by doubling its size at each expansion avoids
an excessive number of allocations and ensures that
appending a single element takes constant time on average.
This program demonstrates the effect:
func main() { var x, y []int for i := 0; i < 10; i++ { y = appendInt(x, i) fmt.Printf("%d cap=%d %v ", i, cap(y), y) x = y } }
Each change in capacity indicates an allocation and a copy:
0 cap=1 [0] 1 cap=2 [0 1] 2 cap=4 [0 1 2] 3 cap=4 [0 1 2 3] 4 cap=8 [0 1 2 3 4] 5 cap=8 [0 1 2 3 4 5] 6 cap=8 [0 1 2 3 4 5 6] 7 cap=8 [0 1 2 3 4 5 6 7] 8 cap=16 [0 1 2 3 4 5 6 7 8] 9 cap=16 [0 1 2 3 4 5 6 7 8 9]
Let’s take a closer look at the i=3
iteration. The slice x
contains
the three elements [0 1 2]
but has capacity 4
, so there is a
single element of slack at the end, and appendInt
of the element
3
may proceed without reallocating. The resulting slice y
has
length and capacity 4
, and has the same underlying array as the original
slice x
, as Figure 4.2 shows.
On the next iteration, i=4
, there is no slack at all, so
appendInt
allocates a new array of size 8,
copies the four elements [0 1 2 3]
of x
,
and appends 4
, the value of i
. The resulting slice
y
has a length of 5 but a capacity of 8; the slack of 3 will save
the next three iterations from the need to reallocate. The slices y
and x
are views of different arrays.
This operation is depicted in Figure 4.3.
The built-in append
function may use a more sophisticated
growth strategy than appendInt
’s simplistic one.
Usually we don’t know whether a given call to append
will
cause a reallocation, so we can’t assume that the original slice
refers to the same array as the resulting slice, nor that it refers to
a different one.
Similarly, we must not assume that assignments to elements of the old slice will
(or will not) be reflected in the new slice.
Consequently, it’s usual to assign the result of a call to
append
to the same slice variable whose value we passed to
append
:
runes = append(runes, r)
Updating the slice variable is required not just when calling append
, but for any
function that may change the length or capacity of a slice or make it
refer to a different underlying array.
To use slices correctly, it’s important to bear in mind that although
the elements of the underlying array are indirect, the slice’s pointer,
length, and capacity are not.
To update them requires an assignment like the one above.
In this respect, slices are not “pure” reference types but resemble
an aggregate type such as this struct:
type IntSlice struct { ptr *int len, cap int }
Our appendInt
function adds a single element to
a slice, but the built-in append
lets us add more than one new
element, or even a whole slice of them.
var x []int x = append(x, 1) x = append(x, 2, 3) x = append(x, 4, 5, 6) x = append(x, x...) // append the slice x fmt.Println(x) // "[1 2 3 4 5 6 1 2 3 4 5 6]"
With the small modification shown below, we can match the behavior
of the built-in append
.
The ellipsis “...
” in the declaration of appendInt
makes the function variadic: it accepts any number of
final arguments.
The corresponding ellipsis in the call above to append
shows
how to supply a list of arguments from a slice.
We’ll explain this mechanism in detail in Section 5.7.
func appendInt(x []int, y ...int) []int { var z []int zlen := len(x) + len(y) // ...expand z to at least zlen... copy(z[len(x):], y) return z }
The logic to expand z
’s underlying array remains unchanged and is
not shown.
Let’s see more examples of functions that, like rotate
and
reverse
, modify the elements of a slice in place.
Given a list of strings, the nonempty
function returns the non-empty
ones:
// Nonempty is an example of an in-place slice algorithm. package main import "fmt" // nonempty returns a slice holding only the non-empty strings. // The underlying array is modified during the call. func nonempty(strings []string) []string { i := 0 for _, s := range strings { if s != "" { strings[i] = s i++ } } return strings[:i] }
The subtle part is that the input slice and the output slice share the
same underlying array.
This avoids the need to allocate another array, though of course the
contents of data
are partly overwritten, as evidenced by the
second print statement:
data := []string{"one", "", "three"} fmt.Printf("%q ", nonempty(data)) // `["one" "three"]` fmt.Printf("%q ", data) // `["one" "three" "three"]`
Thus we would usually write: data = nonempty(data)
.
The nonempty
function can also be written using append
:
func nonempty2(strings []string) []string { out := strings[:0] // zero-length slice of original for _, s := range strings { if s != "" { out = append(out, s) } } return out }
Whichever variant we use, reusing an array in this way requires that at most one output value is produced for each input value, which is true of many algorithms that filter out elements of a sequence or combine adjacent ones. Such intricate slice usage is the exception, not the rule, but it can be clear, efficient, and useful on occasion.
A slice can be used to implement a stack. Given an
initially empty slice stack
, we can push a new value onto
the end of the slice with append
:
stack = append(stack, v) // push v
The top of the stack is the last element:
top := stack[len(stack)-1] // top of stack
and shrinking the stack by popping that element is
stack = stack[:len(stack)-1] // pop
To remove an element from the middle of a slice, preserving the order
of the remaining elements, use copy
to slide the
higher-numbered elements down by one to fill the gap:
func remove(slice []int, i int) []int { copy(slice[i:], slice[i+1:]) return slice[:len(slice)-1] } func main() { s := []int{5, 6, 7, 8, 9} fmt.Println(remove(s, 2)) // "[5 6 8 9]" }
And if we don’t need to preserve the order, we can just move the last element into the gap:
func remove(slice []int, i int) []int { slice[i] = slice[len(slice)-1] return slice[:len(slice)-1] } func main() { s := []int{5, 6, 7, 8, 9} fmt.Println(remove(s, 2)) // "[5 6 9 8] }
Exercise 4.3:
Rewrite reverse
to use an array pointer instead of a slice.
Exercise 4.4:
Write a version of rotate
that operates in a single pass.
Exercise 4.5:
Write an in-place function to eliminate adjacent duplicates
in a []string
slice.
Exercise 4.6:
Write an in-place function that squashes each run of adjacent Unicode
spaces (see unicode.IsSpace
) in a UTF-8-encoded []byte
slice into a single ASCII space.
Exercise 4.7:
Modify reverse
to reverse the characters of a
[]byte
slice that represents a UTF-8-encoded string, in place.
Can you do it without allocating new memory?
44.203.235.24