Go Slices

From NovaOrdis Knowledge Base
Revision as of 00:54, 2 September 2023 by Ovidiu (talk | contribs) (→‎Sorting)
Jump to navigation Jump to search

External

Internal

Overview

A slice is a contiguous "window" on an underlying array. In Go, slices are preferred to be used instead of arrays, and they are some times referred to as dynamic arrays. Given that declaring a slice will create the backing array if no array is explicitly provided, you can almost always use a slice instead of an array.

A slice has variable length, up the total length of the underlying array. "Length" and "size" can be used interchangeably. Unlike in array's case, the size of the slice can change.

A slice is a three-field data structure that contains the metadata needed to manipulate the underlying array:

  • the pointer, indicates the start of the slice in the underlying array. It points to the first element , as the index of an array's element. Is this an integer index, or an actual pointer, that points to the location in memory of the first element of the slice?
  • the length is the number of elements in the slice. The length is read with function len(). append() places the new element after the last element counted within the current length, at the index len(s).
  • the capacity is the maximum number of elements in the slice. The capacity is determined as the difference between the size of underlying array and the slice's pointer. The capacity is read with function cap(). An existing slice can increase up to the end of the array, but the slice can be expanded beyond the length of the underlying array by creating a slice with a new, longer underlying array with append().

Slice.png

Overlapping slices can refer to the same underlying array, and changing an element in a slice reflect in all other slices associated with the array.

Lexically, the slice type is a reference type.

Passing Slices as Arguments

Unlike arrays, which are values and, given the fact that function arguments are always passed by value in Go, problematic to pass when they are large, slices are amenable to be passed as function arguments. They footprint is very small, and the mechanics of passing them by value is efficient: only the slice metadata is copied (that includes the pointer to the array), not the underlying array. When passing slices we don't have to deal with pointers and complicated syntax:

func passSliceExample(s []int) {
    s[1] = s[1] + 1
}

func callerFunction() {
    s := []int{10, 20, 30}
    passSliceExample(s)
    fmt.Println(s) // will print [10, 21, 30]
}

Printing Slices

s := make([]int, 0, 3)
fmt.Println("slice", s)
fmt.Printf("slice %v\n", s)

The calls are equivalent.

Declaration

A slice is declared with the following notation:

var <var-name> []<type>
var s []int

This declaration is similar to an array's except the length is not specified. Note that this declaration will create a nil slice. See Empty Slice and nil Slice below.

A slice may be declared on a previously declared array. The slice is declared using the following brackets and colon notation:

<array-variable-name>[<index-of-the-first-array-element-in-slice>:<index-of-the-first-array-element-outside-slice>]
colors := [...]string{"red", "blue", "green", "yellow", "black", "white", "purple"}
s := colors[0:3]

A slice may be declared, using a slice literal so it creates the underlying array. When a slice is declared with a literal (see Literals below for an example), the slice points to the start of the newly created array, and its length is equal with its capacity.

Literals

The following declaration initializes a slice. We know it's a slice and not an array because the type declaration uses [] (undetermined length) and not [...] or [7], which, because of their specific length or the ... token, signal that they represent an array.

s := []string{"red", "blue", "green"}
println(len(s)) // prints 3
println(cap(s)) // prints 3

A different literal format sets the length and the capacity by initializing only the last element of the slice. The following declaration creates a slice that has a length and capacity of 10:

s := []int{9: 0}

Initialization

To initialize an empty slice, see Empty Slices and nil Slices below. A nil slice is usually sufficient, as it works well with append().

To initialize a non-empty slice, the underlying array can be used in the initialization syntax:

a := [...]int{7, 17, 37, 47, 57}
b := a[1:4]

The "low" index is the index where the slice starts and "high" is the index where slice ends. The new slice will exclude the element indicated by the "high" index. The length of the new slice is given by the formula high - low. However, the capacity of the new slice will be determined by the boundary of the shared underlying array, so it will be len(underlying_array) - low. The same result is yielded by cap(a) - low.

SliceExpression.png

Slices can be initialized with a slice literal:

s2 := []int{7, 17, 37}

Initialization with make()

Slices can also be initialized using the built-in function make():

make([]<element-type>, <length>, [capacity])
s := make([]int, 3)     // create an int slice of length (and capacity) 3
s2 := make([]int, 3, 5) // create an int slice of length 3 and capacity 5

make() returns the slice instance, not a pointer. It is not allowed to create a slice with a capacity smaller than its length, such a situation will be handled as compile-time error.

Empty Slice and nil Slice

Declaring a slice without initializing it creates a nil slice. The slice variable is initialized with nil. This is common behavior for reference types.

var s []int
fmt.Printf("%p\n", s) // will display 0x0

A nil slice can be used with append().

If the initialization statement invokes make(), it will create an empty slice:

s := make([]int, 0)
fmt.Printf("%p\n", s) // will display something else than 0x0

An empty slice points to a zero length array. The slice length is initialized to 0 and the capacity is initialized to 0. Regardless of whether they are applied to a nil or an empty slice, the built-in functions append(), len() and cap() work consistently.

Operators

Indexing Operator []

Slice elements can be read and written with the indexing operator [].

colors := [...]string{"red", "blue", "green", "yellow"}
s := colors[0:3]
println(s[1]) // prints "blue"
s[1] = "fuchsia"
println(s[1]) // prints "fuchsia"

A slice can only access indexes up to its length, an attempt to access an element beyond the slice length will cause a runtime error. If the slice capacity exceeds its length, the elements associated to the capacity that do not belong to the slice cannot be accessed via the index operator, they're only available for growth (see append()) and an attempt to access them via the index operator will also cause a runtime error.

The syntax s[i:i] is legal, as long as i is an index between 0 and the capacity (inclusive). The syntax means a zero length slice that starts at i. len() function on that slice will return 0. If an i value larger than the capacity is used, the runtime throws an error similar to:

panic: runtime error: slice bounds out of range [:4] with capacity 3

Functions

len()

len() is a built-in function that returns the length of a slice.

cap()

cap() is a built-in function that returns the capacity of a slice.

make()

make() is a built-in function that can be used to make new slices. See Initialization above.

append()

TODO: research if anything new (slice, underlying array) is allocated if increase in capacity is NOT needed. Factor this in https://blog.golang.org/slices

append() is a built-in function that can be used to simultaneously 1) create a new slice by copying the content of an existing slice provided as argument 2) add elements at the end of the newly created slice and 3) expand the newly created slice capacity, if by adding the elements we fall beyond the source slice capacity.

//
// create a zero-length slice with capacity 3
//
s := make([]int, 0, 3)

//
// create a new slice with append()
// this append() invocation does not increase the capacity
//
s2 := append(s, 11)    // create a new slice, that has a length of 1, capacity of 3 and the element on position 0 equal to 11
fmt.Printf("source slice len: %d, cap: %d\n", len(s), cap(s)) // will print 0, 3
fmt.Printf("new slice len: %d, cap: %d, elements: %d\n", len(s2), cap(s2), s2[0]) // will print 1, 3, 11

//
// create a new slice with append()
// this append() invocation will increase the capacity
//
s3 := append(s, 11, 22, 33, 44)    // create a new slice, that has a length of 4 and larger capacity
fmt.Printf("source slice len: %d, cap: %d\n", len(s), cap(s)) // will print 0, 3
fmt.Printf("new slice len: %d, cap: %d, elements: %d, %d, %d, %d\n", len(s3), cap(s3), s3[0], s3[1], s3[2], s3[3]) // will print 4, 6, 11, 22, 33, 44

append() works well with nil slices.

copy()

copy(target_slice, source_slice)

The function copies all source slice elements over the corresponding target slice elements, overwriting the target. If the slices have different lengths, the shortest one will be used.

Iterating through Slices

Use the range keyword. range allows to iterate by indices, values or both. Iterate by indices:

for i := range s {
  fmt.Printf("index: %d\n", i)
}

Iterate by values:

for _, e := range s {
  fmt.Printf("element value: %d\n", e)
}

Iterate by both indices and values:

for i, e := range s {
  fmt.Printf("index: %d, element value: %d\n", i, e)
}

Sorting

There are sorting functions provided by the slices package. The sort package also provides sorting, but the sort documentation mentions that the slice sorting functions run faster.

Sorting with the slices Package

TO DISTRIBUTE

Overlapping Slices


Note that after applying the slicing operation, the resulted slice shares a portion of the underlying array with the initial slice, so changing an element in one slice is reflected in the other. This is not necessarily a good thing, because those two slices are connected in a non-obvious way, and making a change in one slice causes a (non-obvious) change in the second slice, leading to hard to troubleshoot bugs. In order to avoid this behavior, restrict the capacity of the newly created slice with a third index. See Three-index Slice Expression below.

Special forms of the "slice" expression:

  • a[i:] is equivalent with a[i:len(a)]
  • a[:i] is equivalent with a[0:i]
  • a[:] is equivalent with a[0:len(a)]

Three-Index Slice Expression

The third index specified with the slice expression restricts the capacity of the newly created slice.

new_slice_identifier := old_slice_identifier[low:high:high_for_capacity]

The "low" and "high" have the same semantics as in the case of the regular slice expression. "high_for_capacity" is the index where to end the underlying array of the slice: the underlying array of the new slice can use as "capacity" elements all the elements up to, but not including the "high_for_capacity" index.

Example:

a := []string {"a", "b", "c", "d", "e"} // creates a slice with length 5 and capacity 5
b := a[1:2:3] // creates a slice with length 1, containing 'b", and the capacity 2

Note that "high_for_capacity" must fall inside the underlying array backing "a", or, at most, must fall right outside the array (which means that the whole array will be used for capacity) otherwise we get "slice bounds out of range". The slices keep sharing the memory areas corresponding to their backing arrays, so b[0]="x" will cause a[1] to become "x".

The three-index slice expression is useful to create slices whose capacity is the same as the length, so the first append() operation creates a new underlying array, thus completely detaching the slices - which is a good thing. See "slices share memory" note for an explanation why. From a practical perspective, it is a good idea to always use the "three-index slice expression" where the "high" and "high_for_capacity" coincide:

b := a[low, high, high]

Example:

b := a[2, 5, 5]

append() TO DEPLETE

append() adds element at the end of the slice, increasing its length, and, if necessary, the capacity:

<new_slice_identifier> := append(<old_slice_identifier>, <new_element>)

The addition is operated by writing the values in the corresponding positions in the underlying array, unless the array is not long enough. In this case, a new array long enough to accommodate the new elements is created and the original array values are copied across. Be aware that as long as no new array is created, the slices share the underlying array, thus are prone to lateral effects. Also see "slices share memory" note.


The function always creates a new slice instance, don't expect that a lateral effect will change your input slice.

Example:

s := make([]int, 0) // the length of s is 0

s2 := append(s, 1) // the length of s stays 0 
                   // but the length of s2 (a new slice) is 1

append() as variadic function

append() is a variadic function, it accepts multiple elements to be appended to the slice:

s2 := append(s, 1, 2, 3, 4, 5)

When we want to pass the variadic arguments of an enclosing function, we need to use this syntax:

func enclosing(args ...int) {
   ...
   s = append(s, args ...)
}

Note the use of ellipsis (...) when passing the args... variadic argument to append(). More on variadic functions is available here Variadic Functions.

Passing a Slice's Elements to a Variadic Function

Variadic Functions

Multidimensional Slices

Go in Action page 100.

Further Process