Go Slices: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
No edit summary
Line 3: Line 3:
=Internal=
=Internal=
{{Internal|Go_Language#Slices|Go Language}}
{{Internal|Go_Language#Slices|Go Language}}
=Overview=


=TO DISTRIBUTE=
=TO DISTRIBUTE=
Line 11: Line 12:
* Slice tricks: https://github.com/golang/go/wiki/SliceTricks
* Slice tricks: https://github.com/golang/go/wiki/SliceTricks


=Internal=
==Internal==
 
* [[Go Concepts - The Type System#Built-in_Types|Built-in Types]]
* [[Go Concepts - The Type System#Built-in_Types|Built-in Types]]
* [[Go Arrays|Arrays]]
* [[Go Arrays|Arrays]]
* [[Go Maps|Maps]]
* [[Go Maps|Maps]]
 
==Overview==
=Overview=


A ''slice'' is a [[Go_Concepts_-_The_Type_System#Reference_Types|reference type]] that implements a ''dynamic array''. Slices are indexable, and they have a variable length. They are always associated with an underlying array, and the slice length cannot be longer than the underlying array - but it can be shorter. The [[Go_Slices#Slice_Capacity|slice's capacity]] is equal to the length on the underlying array. The index operator does not work beyond the capacity of the slice, but the slice can be expanded beyond the length of the underlying array by creating a new, longer underlying array - and consequently a new slice - with <tt>[[Go_Slices#append.28.29|append()]]</tt>.
A ''slice'' is a [[Go_Concepts_-_The_Type_System#Reference_Types|reference type]] that implements a ''dynamic array''. Slices are indexable, and they have a variable length. They are always associated with an underlying array, and the slice length cannot be longer than the underlying array - but it can be shorter. The [[Go_Slices#Slice_Capacity|slice's capacity]] is equal to the length on the underlying array. The index operator does not work beyond the capacity of the slice, but the slice can be expanded beyond the length of the underlying array by creating a new, longer underlying array - and consequently a new slice - with <tt>[[Go_Slices#append.28.29|append()]]</tt>.
Line 25: Line 24:
Unlike arrays, which [[Go_Arrays#Arrays_are_Values|are values and problematic to pass as function arguments]], slices can be easily be passed as values - their memory footprint is very small, and when passed as values, only the slices are copied, not the underlying array. Also, when passing slices we don't have to deal with pointers and complicated syntax.
Unlike arrays, which [[Go_Arrays#Arrays_are_Values|are values and problematic to pass as function arguments]], slices can be easily be passed as values - their memory footprint is very small, and when passed as values, only the slices are copied, not the underlying array. Also, when passing slices we don't have to deal with pointers and complicated syntax.


=Implementation Details=
==Implementation Details==


The slices are three-field data structures that contain the metadata needed to manipulate the underlying array.
The slices are three-field data structures that contain the metadata needed to manipulate the underlying array.
Line 31: Line 30:
[[Image:Slice.png]]
[[Image:Slice.png]]


==Accessing the Slice's Underlying Array==
===Accessing the Slice's Underlying Array===


<font color=red>'''TODO''', process this: http://stackoverflow.com/questions/25551082/how-would-you-access-the-underlying-array-passed-to-a-function-expecting-an-empt</font>
<font color=red>'''TODO''', process this: http://stackoverflow.com/questions/25551082/how-would-you-access-the-underlying-array-passed-to-a-function-expecting-an-empt</font>


=Declaration=
==Declaration==


==Long Declaration==
===Long Declaration===


A slice declaration is similar to an array's except the length is not specified. The slice is created with a zero length if no literal is specified.
A slice declaration is similar to an array's except the length is not specified. The slice is created with a zero length if no literal is specified.
Line 51: Line 50:
</pre>
</pre>


==Short Declaration==
===Short Declaration===


===Short Declaration with Literals===
====Short Declaration with Literals====


A short declaration using a slice literal. The declaration is similar to declaring an array, except that the brackets do not contain the length:
A short declaration using a slice literal. The declaration is similar to declaring an array, except that the brackets do not contain the length:
Line 69: Line 68:
</pre>
</pre>


===Short Declaration with <tt>make()</tt>===
====Short Declaration with <tt>make()</tt>====


A short declaration can also be performed using <tt>[[Go Slices#make.28.29|make()]]</tt>. <tt>make()</tt> takes the length and the capacity of the slice.  
A short declaration can also be performed using <tt>[[Go Slices#make.28.29|make()]]</tt>. <tt>make()</tt> takes the length and the capacity of the slice.  


===Short Declaration with a Slice Expression===
====Short Declaration with a Slice Expression====


The slices can also be created with the "slice" expression applied to an array:
The slices can also be created with the "slice" expression applied to an array:
Line 102: Line 101:
* <tt>a[:]</tt> is equivalent with <tt>a[0:len(a)]</tt>
* <tt>a[:]</tt> is equivalent with <tt>a[0:len(a)]</tt>


===Three-Index Slice Expression===
====Three-Index Slice Expression====


The third index specified with the slice expression ''restricts the capacity'' of the newly created slice.
The third index specified with the slice expression ''restricts the capacity'' of the newly created slice.
Line 133: Line 132:
</pre>
</pre>


=<tt>nil</tt> Slices and Empty Slices=
==<tt>nil</tt> Slices and Empty Slices==


Declaring a slice without initializing it creates a <tt>nil</tt> slice - the slice variable is initialized with <tt>nil</tt>. This is common behavior for [[Go_Concepts_-_The_Type_System#Reference_Types|reference types]]:
Declaring a slice without initializing it creates a <tt>nil</tt> slice - the slice variable is initialized with <tt>nil</tt>. This is common behavior for [[Go_Concepts_-_The_Type_System#Reference_Types|reference types]]:
Line 157: Line 156:
Regardless of whether a <tt>nil</tt> or empty slice is used, the built-in functions <tt>append()</tt>, <tt>len()</tt> and <tt>cap()</tt> work the same.
Regardless of whether a <tt>nil</tt> or empty slice is used, the built-in functions <tt>append()</tt>, <tt>len()</tt> and <tt>cap()</tt> work the same.


=Slice Operators and Functions=
==Slice Operators and Functions==


==Indexing Operator==
===Indexing Operator===


Indexing operator <tt>[[Go Concepts - Operators#.5B.5D|[]]]</tt> works in the same way as with arrays. The indexing operator can be used to access and change values of individual elements.
Indexing operator <tt>[[Go Concepts - Operators#.5B.5D|[]]]</tt> works in the same way as with arrays. The indexing operator can be used to access and change values of individual elements.
Line 165: Line 164:
A slice an only access indexes up to its length, an attempt to access an element outside the slice's length will cause a runtime error. If the slice's 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 <tt>[[#append.28.29|append()]]</tt>) and an attempt to access them via the index operator will also cause a runtime error.
A slice an only access indexes up to its length, an attempt to access an element outside the slice's length will cause a runtime error. If the slice's 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 <tt>[[#append.28.29|append()]]</tt>) and an attempt to access them via the index operator will also cause a runtime error.


==Slice Length==
===Slice Length===


<tt>[[Go Built-In Functions Length and Capacity#len.28.29|len()]]</tt> returns the length of the slice.
<tt>[[Go Built-In Functions Length and Capacity#len.28.29|len()]]</tt> returns the length of the slice.


==Slice Capacity==
===Slice Capacity===


<code>[[Go_Functions#cap.28.29|cap()]]</code> returns the length of the underlying array.
<code>[[Go_Functions#cap.28.29|cap()]]</code> returns the length of the underlying array.


==<tt>make()</tt>==
===<tt>make()</tt>===


The <tt>[[Go Built-In Function make|make()]]</tt> function creates the slice and the underlying array.
The <tt>[[Go Built-In Function make|make()]]</tt> function creates the slice and the underlying array.
Line 190: Line 189:
Note that <tt>make()</tt> returns the slice instance, not a pointer.
Note that <tt>make()</tt> returns the slice instance, not a pointer.


==<tt>append()</tt>==
===<tt>append()</tt>===


<tt>append()</tt> adds element at the end of the slice, increasing its length, and, if necessary, the capacity:
<tt>append()</tt> adds element at the end of the slice, increasing its length, and, if necessary, the capacity:
Line 213: Line 212:
</pre>
</pre>


===<tt>append()</tt> as variadic function===
====<tt>append()</tt> as variadic function====


<tt>append()</tt> is a variadic function, it accepts multiple elements to be appended to the slice:
<tt>append()</tt> is a variadic function, it accepts multiple elements to be appended to the slice:
Line 232: Line 231:
Note the use of ellipsis (...) when passing the <tt>args...</tt> variadic argument to <tt>append()</tt>. More on variadic functions is available here [[Go_Concepts_-_Functions#Varidic_Functions|Variadic Functions]].
Note the use of ellipsis (...) when passing the <tt>args...</tt> variadic argument to <tt>append()</tt>. More on variadic functions is available here [[Go_Concepts_-_Functions#Varidic_Functions|Variadic Functions]].


==<tt>copy()</tt>==
===<tt>copy()</tt>===


<pre>
<pre>
Line 240: Line 239:
The function copies all the source elements over the corresponding elements in the destination, overwriting the destination. If the lengths of the slices are not the same, the shortest one will be used.
The function copies all the source elements over the corresponding elements in the destination, overwriting the destination. If the lengths of the slices are not the same, the shortest one will be used.


==Slice Expression==
===Slice Expression===


See [[#Short_Declaration_with_a_Slice_Expression|Short Declaration with a Slice Expression]] above.
See [[#Short_Declaration_with_a_Slice_Expression|Short Declaration with a Slice Expression]] above.


==Iterating over Slices==
===Iterating over Slices===
<blockquote style="background-color: #f9f9f9; border: solid thin lightgrey;">
<blockquote style="background-color: #f9f9f9; border: solid thin lightgrey;">
:[[Go Keyword range|<tt>range</tt> Keyword]]
:[[Go Keyword range|<tt>range</tt> Keyword]]
</blockquote>
</blockquote>


=Passing a Slice's Elements to a Variadic Function=
==Passing a Slice's Elements to a Variadic Function==


<blockquote style="background-color: #f9f9f9; border: solid thin lightgrey;">
<blockquote style="background-color: #f9f9f9; border: solid thin lightgrey;">
Line 255: Line 254:
</blockquote>
</blockquote>


=Multidimensional Slices=
==Multidimensional Slices==


<font color=red>'''TODO''' Go in Action page 100.</font>
<font color=red>'''TODO''' Go in Action page 100.</font>

Revision as of 16:14, 24 August 2023

External

Internal

Go Language

Overview

TO DISTRIBUTE

External

Internal

Overview

A slice is a reference type that implements a dynamic array. Slices are indexable, and they have a variable length. They are always associated with an underlying array, and the slice length cannot be longer than the underlying array - but it can be shorter. The slice's capacity is equal to the length on the underlying array. The index operator does not work beyond the capacity of the slice, but the slice can be expanded beyond the length of the underlying array by creating a new, longer underlying array - and consequently a new slice - with append().

Lexically, a slice type is a reference type. The slice instances must be initialized before attempting to use into them, either by using the make() function or a slice literal, otherwise you will get a runtime error, because a zero value for a slice is nil. More on nil slices: nil Slices and Empty Slices.

Unlike arrays, which are values and problematic to pass as function arguments, slices can be easily be passed as values - their memory footprint is very small, and when passed as values, only the slices are copied, not the underlying array. Also, when passing slices we don't have to deal with pointers and complicated syntax.

Implementation Details

The slices are three-field data structures that contain the metadata needed to manipulate the underlying array.

Slice.png

Accessing the Slice's Underlying Array

TODO, process this: http://stackoverflow.com/questions/25551082/how-would-you-access-the-underlying-array-passed-to-a-function-expecting-an-empt

Declaration

Long Declaration

A slice declaration is similar to an array's except the length is not specified. The slice is created with a zero length if no literal is specified.

var s []int

A slice declaration and initialization with a slice literal:

var s []int = []int {1, 2, 3}

Short Declaration

Short Declaration with Literals

A short declaration using a slice literal. The declaration is similar to declaring an array, except that the brackets do not contain the length:

s := []int{1, 2, 3}

The above declaration sets the length and capacity to 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}

Short Declaration with make()

A short declaration can also be performed using make(). make() takes the length and the capacity of the slice.

Short Declaration with a Slice Expression

The slices can also be created with the "slice" expression applied to an array:

<array_identifier>[<low>:<high>]

Example:

var a [5]int
b := a[1:4]

The "low" index is the index where to start the slice and "high" is the index where to end the new slice: the new slice will not contain 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

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]

nil Slices and Empty Slices

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

For a nil slice, fmt.Printf("%p", s) prints 0x0. The underlying data structures are initialized as follows: the array pointer is initialized to nil, the length is initialized to 0 and the capacity is initialized to 0.

A nil slice is different from an empty slice:

s := []int{}
s := make([]int, 0)

For an empty slice, fmt.Printf("%p", s) prints a pointer: 0x19d730. An empty slice points to a zero length array. The length is initialized to 0 and the capacity is initialized to 0.

Regardless of whether a nil or empty slice is used, the built-in functions append(), len() and cap() work the same.

Slice Operators and Functions

Indexing Operator

Indexing operator [] works in the same way as with arrays. The indexing operator can be used to access and change values of individual elements.

A slice an only access indexes up to its length, an attempt to access an element outside the slice's length will cause a runtime error. If the slice's 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.

Slice Length

len() returns the length of the slice.

Slice Capacity

cap() returns the length of the underlying array.

make()

The make() function creates the slice and the underlying array.

<slice_identifier> := make([]<slice_element_type>, <slice_length>, [capacity])
s := make([]int, 5) // the length and capacity are equal
s1 := make([]int, 5, 10)

It is not allowed to create a slice with a capacity smaller than its length, the compiler will throw an error.

Note that make() returns the slice instance, not a pointer.

append()

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.

copy()

copy(dest_slice, source_slice)

The function copies all the source elements over the corresponding elements in the destination, overwriting the destination. If the lengths of the slices are not the same, the shortest one will be used.

Slice Expression

See Short Declaration with a Slice Expression above.

Iterating over Slices

range Keyword

Passing a Slice's Elements to a Variadic Function

Variadic Functions

Multidimensional Slices

TODO Go in Action page 100.