Go Slices: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
(Replaced content with "=TODEPLETE= {{Internal|Go_Slices_TODEPLETE|Go Slices TODPLETE}}")
Tag: Replaced
Line 1: Line 1:
=External=
=TODEPLETE=
* https://go.dev/ref/spec#Slice_types
{{Internal|Go_Slices_TODEPLETE|Go Slices TODPLETE}}
* https://blog.golang.org/slices
* https://github.com/golang/go/wiki/SliceTricks
 
=Internal=
* [[Go_Language#Slices|Go Language]]
* [[Go Arrays]]
* [[Go_Package_slices|Package <tt>slices</tt>]]
 
=Overview=
A slice is a contiguous "window" on an underlying [[Go_Arrays#Overview|array]]. In Go, slices are [[#Passing_Slices_as_Arguments|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:
* <span id='Pointer'></span>The '''pointer''', indicates the start of the slice in the underlying array. It points to the first element , <font color=darkkhaki>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?</font>
* <span id='Length'></span>The '''length''' is the number of elements in the slice. The length is read with function <code>[[#len.28.29|len()]]</code>. <code>[[#append.28.29|append()]]</code> places the new element after the last element counted within the current length, at the index <code>len(s)</code>.
* <span id='Capacity'></span>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|pointer]]. The capacity is read with function <code>[[#cap.28.29|cap()]]</code>. 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 <code>[[#append.28.29|append()]]</code>.
 
[[Image: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 [[Go_Language#Reference_Type|reference type]].
 
=Passing Slices as Arguments=
 
<span id='Slice_Performance'></span>Unlike arrays, which [[Go_Arrays#Arrays_are_Values|are values]] and, given the fact that [[Go_Functions#Arg_Passing|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. Note that slice variables are '''not''' [[Go_Language#.28No.29_Reference_Variables|reference variable]], no two different slices may point to the same slice instance, but the slice values are small and they can be copied fast, which make them suitable to be passed as 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 [[Go_Arrays#Pass_by_Reference|complicated syntax]]:
 
<syntaxhighlight lang='go'>
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]
}
</syntaxhighlight>
 
=Printing Slices=
<syntaxhighlight lang='go'>
s := make([]int, 0, 3)
fmt.Println("slice", s)
fmt.Printf("slice %v\n", s)
</syntaxhighlight>
The calls are equivalent.
 
=Declaration=
A slice is declared with the following notation:
<syntaxhighlight lang='go'>
var <var_name> []<type>
</syntaxhighlight>
<syntaxhighlight lang='go'>
var s []int
</syntaxhighlight>
This declaration is similar to an array's except the length is not specified. Note that this declaration will create a <code>nil</code> slice. See [[#Empty_Slice_and_nil_Slice|Empty Slice and <tt>nil</tt> Slice]] below.
 
A slice may be declared on a previously declared array. The slice is declared using the following brackets and colon notation:
<syntaxhighlight lang='go'>
<array_variable_name>[<index_of_the_first_array_element_in_slice>:<index_of_the_first_array_element_outside_slice>]
</syntaxhighlight>
 
<syntaxhighlight lang='go'>
colors := [...]string{"red", "blue", "green", "yellow", "black", "white", "purple"}
s := colors[0:3]
</syntaxhighlight>
 
A slice may be declared, using a [[#Literal|slice literal]] so it creates the underlying array. When a slice is declared with a literal (see [[#Literals|Literals]] below for an example), the slice points to the start of the newly created array, and its [[#Length|length]] is equal with its [[#Capacity|capacity]].
 
=Literals=
The following declaration, which uses a composite literal, initializes a slice. We know it's a slice and not an array because the type declaration uses <code>[]</code> (undetermined length) and not <code>[...]</code> or <code>[7]</code>, which, because of their specific length or the <code>...</code> token, signal that they represent an array.
<syntaxhighlight lang='go'>
s := []string{"red", "blue", "green"}
println(len(s)) // prints 3
println(cap(s)) // prints 3
</syntaxhighlight>
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:
<syntaxhighlight lang='go'>
s := []int{9: 0}
</syntaxhighlight>
 
=Initialization=
The idiomatic way to initialize a slice with a [[#Literal|slice literal]] is:
<syntaxhighlight lang='go'>
s := []int{7, 17, 37}
</syntaxhighlight>
 
The idiomatic way to initialize an empty slice is to use a <code>nil</code> slice:
<syntaxhighlight lang='go'>
var s []int
</syntaxhighlight>
A <code>nil</code> slice works with <code>[[#append.28.29|append()]]</code>. For more details see [[#Empty_Slice_and_nil_Slice|Empty Slices and <tt>nil</tt> Slices]] below.
 
To initialize a non-empty slice, the underlying array can also be used in the initialization syntax:
<syntaxhighlight lang='go'>
a := [...]int{7, 17, 37, 47, 57}
b := a[1:4]
</syntaxhighlight>
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 <code>high - low</code>. However, the capacity of the new slice will be determined by the boundary of the shared underlying array, so it will be <code>len(underlying_array) - low</code>. The same result is yielded by <code>cap(a) - low</code>.
 
[[Image:SliceExpression.png]]
==<span id='Slice_Initialization_with_make'></span>Initialization with <tt>make()</tt>==
Slices can also be initialized using the [[Go_Functions#Built-in_Functions|built-in function]] <code>[[Go_Functions#make.28.29|make()]]</code>:
<syntaxhighlight lang='go'>
make([]<element_type>, <length>, [capacity])
</syntaxhighlight>
Idiomatic:
<syntaxhighlight lang='go'>
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
</syntaxhighlight>
<code>make()</code> 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 <tt>nil</tt> Slice=
<span id='Nil_Slice'></span>Declaring a slice without initializing it creates a <code>nil</code> slice. The slice variable is initialized with <code>nil</code>. This is common behavior for [[Go_Language#Reference_Type|reference types]].
<syntaxhighlight lang='go'>
var s []int
fmt.Printf("%p\n", s) // will display 0x0
</syntaxhighlight>
A <code>nil</code> slice can be used with <code>[[#append.28.29|append()]]</code>.
 
If the initialization statement invokes <code>make()</code>, it will create an empty slice:
<syntaxhighlight lang='go'>
s := make([]int, 0)
fmt.Printf("%p\n", s) // will display something else than 0x0
</syntaxhighlight>
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 <code>nil</code> or an empty slice, the built-in functions <code>append()</code>, <code>len()</code> and <code>cap()</code> work consistently.
 
==Test <tt>nil</tt> Slice==
<syntaxhighlight lang='go'>
var s []string
 
if s == nil {
  ...
}
</syntaxhighlight>
 
Note that a <code>s</code> is not actually a <code>nil</code> pointer, it points to a non-nil structure in memory that has a <code>nil</code> array pointer. <font color=darkkhaki>Prove that. The semantics of <code>==</code> in this case is modified to match the nil slice semantics, not the nil pointer</font>.
 
==Test Empty Slice==
 
=Operators=
==Indexing Operator <tt>[]</tt>==
<font color=darkkhaki>Start by describing [i] then the other forms, below.</font>
 
 
Slice elements can be read and written with the indexing operator <code>[[Go_Language#Indexing_Operator|[]]]</code>.
<syntaxhighlight lang='go'>
colors := [...]string{"red", "blue", "green", "yellow"}
s := colors[0:3]
println(s[1]) // prints "blue"
s[1] = "fuchsia"
println(s[1]) // prints "fuchsia"
</syntaxhighlight>
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 <code>[[#append.28.29|append()]]</code>) and an attempt to access them via the index operator will also cause a runtime error.
 
The syntax <code>s[i:i]</code> is legal, as long as <code>i</code> is an index between 0 and the capacity (inclusive). The syntax means a zero length slice that starts at <code>i</code>. <code>len()</code> function on that slice will return 0. If an <code>i</code> value larger than the capacity is used, the runtime throws an error similar to:
<font size=-1>
panic: runtime error: slice bounds out of range [:4] with capacity 3
</font>
===<tt>[:]</tt>===
 
<tt>a[:]</tt> is equivalent with <tt>a[0:len(a)]</tt>
 
===<tt>[i:]</tt>===
 
<tt>a[i:]</tt> is equivalent with <tt>a[i:len(a)]</tt>.
 
If <code>i</code> falls immediately after the right edge of the slice (for example, <code>i</code> is 3 for a slice of length 3) the expression returns an empty slice. If  <code>i</code> goes beyond the very edge, we get a runtime error "slice bounds out of range"
 
===<tt>[:i]</tt>===
<tt>a[:i]</tt> is equivalent with <tt>a[0:i]</tt>
===<tt>[i:j]</tt>===
===Last Element of a Slice===
<syntaxhighlight lang='go'>
s := []string{...}
 
s[len(s)-1] // only works for non-empty slices
</syntaxhighlight>
For empty slices, the above panics, so test it explicitly.
 
===Three-Index Slice Expression <tt>[low:high:high_for_capacity]</tt>===
 
The third index specified with the slice expression ''restricts the capacity'' of the newly created slice.
 
<pre>
new_slice_identifier := old_slice_identifier[low:high:high_for_capacity]
</pre>
 
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:
 
<pre>
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
</pre>
 
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 <tt>b[0]="x"</tt> 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 <tt>append()</tt> operation creates a new underlying array, thus completely detaching the slices - which is a good thing. See [[#Slices_Share_Memory|"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:
 
<pre>
b := a[low, high, high]
</pre>
 
Example:
 
<pre>
b := a[2, 5, 5]
</pre>
 
=Functions=
==<span id='Slice_Length'></span><tt>len()</tt>==
<code>len()</code> is a [[Go_Functions#len.28.29|built-in function]] that returns the [[#Length|length]] of a slice.
 
==<span id='Slice_Capacity'></span><tt>cap()</tt>==
<code>cap()</code> is a [[Go_Functions#cap.28.29|built-in function]] that returns the [[#Capacity|capacity]] of a slice.
 
==<tt>make()</tt>==
<code>make()</code> is a [[Go_Functions#cap.28.29|built-in function]] that can be used to make new slices. See  [[#Slice_Initialization_with_make|Initialization]] above.
==<tt>append()</tt>==
<span id='NJUL'></span><font color=darkkhaki>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</font>
 
<code>append()</code> is a [[Go_Functions#cap.28.29|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.
<syntaxhighlight lang='go'>
//
// 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
 
</syntaxhighlight>
 
<code>append()</code> works well with [[#Nil_Slice|<code>nil</code> slices]].
 
==<tt>copy()</tt>==
<syntaxhighlight lang='go'>
target_slice = make([]..., len(source_slice)) // this will ensure that source_slice elements will be copied
copy(target_slice, source_slice)
</syntaxhighlight>
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.
 
=<span id='Iterating_over_Slices'></span>Iterating through Slices=
Use the <code>[[Go_Keyword_range|range]]</code> [[Go_Language#Keywords|keyword]]. <code>[[Go_Keyword_range|range]]</code> allows to iterate by indices, values or both.
Iterate by indices:
<syntaxhighlight lang='go'>
for i := range s {
  fmt.Printf("index: %d\n", i)
}
</syntaxhighlight>
 
Iterate by values:
<syntaxhighlight lang='go'>
for _, e := range s {
  fmt.Printf("element value: %d\n", e)
}
</syntaxhighlight>
Iterate by both indices and values:
<syntaxhighlight lang='go'>
for i, e := range s {
  fmt.Printf("index: %d, element value: %d\n", i, e)
}
</syntaxhighlight>
=Sorting=
There are sorting functions provided by the  <code>[[Go Package slices#Sorting|slices]]</code> package. The <code>[[Go Package sort#Overview|sort]]</code> package also provides sorting, but the <code>sort</code> documentation mentions that the <code>slice</code> sorting functions run faster.
 
{{Internal|Go_Package_slices#Sorting|Sorting with the <tt>slices</tt> Package}}
=Testing Existence in Slice=
<font color=darkkhaki>TODO</font>
 
=TO DISTRIBUTE=
<font color=darkkhaki>
==Overlapping Slices==
<span id="Slices_Share_Memory"></span>{{Note|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 [[Go_Slices#Three-Index_Slice_Expression|Three-index Slice Expression]] below.}}
 
==append() TO DEPLETE==
 
<tt>append()</tt> adds element at the end of the slice, increasing its length, and, if necessary, the capacity:
 
<pre>
<new_slice_identifier> := append(<old_slice_identifier>, <new_element>)
</pre>
 
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|"slices share memory" note]].
{{Note|The function always creates a new slice instance, don't expect that a lateral effect will change your input slice.}}
Example:
 
<pre>
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
</pre>
 
===<tt>append()</tt> as variadic function===
 
<tt>append()</tt> is a variadic function, it accepts multiple elements to be appended to the slice:
 
<pre>
s2 := append(s, 1, 2, 3, 4, 5)
</pre>
 
When we want to pass the variadic arguments of an enclosing function, we need to use this syntax:
 
<pre>
func enclosing(args ...int) {
  ...
  s = append(s, args ...)
}
</pre>
 
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]].
 
==Passing a Slice's Elements to a Variadic Function==
{{Internal|Go_Concepts_-_Functions#Varidic_Functions|Variadic Functions}}
==Multidimensional Slices==
Go in Action page 100.

Revision as of 16:31, 15 August 2024

TODEPLETE

Go Slices TODPLETE
Retrieved from "https://kb.novaordis.com/index.php?title=Go_Slices&oldid=112168"