Dynamic array slice for Golang data structure

Dynamic array slice

Slice, also known as dynamic array, relies on array implementation to facilitate expansion and transfer, and is more flexible than array in actual use. But because it is flexible, it is more likely to make mistakes in practice, and the best way to avoid mistakes is to understand how it is implemented.

Features quick reference

Initialize the

There are several ways to declare and initialize slices:

Variable declarations
literal
Use the built-in make() function
Cut from slices and arrays

Variable declarations

Sliced variables are declared in this way, just like other types of variables. The value of the variable is zero. For sliced variables, zero is nil

var s []int
Copy the code

literal

You can also initialize a slice using a literal. It’s important to understand that an empty slice is a slice whose length is empty and whose value is not nil.

When declaring a slice of length 0, it is recommended to use variable declarations to get a nil slice rather than an empty slice because nil slices do not require memory allocation.

S1 :=[]int{} // empty section s2:=[]int{1,2,3} // section with length 3Copy the code

Built-in function make()

The built-in function make() creates slices that are initialized to zero values of the corresponding type.

You are advised to specify the length and estimate the space, which can effectively reduce memory allocation and copy times during slice expansion.

S1: = make (int [], 12) / / s2: specify length = make int [], (10100) / / specified length and spaceCopy the code

Cut out

Slices can be created based on arrays and slices. It is important to understand that slices share the underlying space with the original array or slice, and modifying slices will affect the original array or slice.

The slice expression [LOW :high] represents the range of left closed and right open [low,high), and the cut length is high-low.

Array: = [5] int {1, 2, 3, 4, 5} s1: = array (2-0) / / for s2: from the array = s1 (1-0) / / from taking FMT. Slice the Println (s1) / / [1, 2] FMT. Println (s2) / / [1]Copy the code

Alternatively, the built-in function new(), which works for any type, can also create slices:

S := *new([]int) //Copy the code

Slicing operation

The built-in function append() is used to append elements to slices:

S: = make (int [], 0) / / initialization section s = append (s, 1) / / add a element s = append (s, 2 and 4) / / s = append add multiple elements (s, int [] {5, 6}...). Println(s) //[1,2,3,4,5,6]Copy the code

When the slice space is insufficient, Append () creates a new large-capacity slice first and returns the new slice after adding elements.

The built-in functions len() and cap() are used to query the length and capacity of slices respectively. Since the nature of slices is a structure, and the length and capacity of slices are directly stored in the structure, the time complexity of these two functions is O(1).

Realize the principle of

Slice relies on arrays. The underlying arrays are shielded from users. When the underlying arrays are insufficient, they can be automatically reallocated and new slices can be produced.

The data structure

The source code package in SRC/runtime/slice. Go: slice slice data structures are defined:

Type slice struct {array unsafe.Pointer // len int // cap int // size}Copy the code

Slice is clear in terms of data structure. Array Pointers point to the underlying array, len to the length of the array, and CAP to the capacity of the underlying array.

Slicing operation

Create slice using make()

When using make() to create slice, you can specify both the length and the size. An array is allocated when creating slice, and the length of the array is the size.

For example, the slice structure created by the slice := make([]int, 5, 10) statement looks like this:

The length of the slice is 5, that is, the subscripts of slice[0] to slice[4] can be used to operate the elements in the slice. The capacity value is 10, which indicates that the reserved memory can be used to add new elements in the slice until the reserved memory is insufficient.

Create slice using arrays

When slice is created using arrays, slice shares some memory with the original array

For example, the slice structure created by the slice := array[5,7] statement looks like this:

Slicing starts from array[5] and ends in array[7] (excluding 7), that is, the length of the slice is 2, and the memory behind the array is used as the reserved memory of the slice, that is, capacity is 5.

Arrays and arrays’ slices share the underlying storage space, which is something you need to pay extra attention to when using them. If a slice is created from an array, operations on the slice affect the original array, and if multiple slices are created from the same array, operations on one slice affect other slices.

Slice capacity

When append is used to append elements to slice, if the slice space is insufficient, it triggers slice expansion, which in effect reallocates a larger slice, copies the data from the original slice into the new slice, returns the new slice, and appends the data after expansion.

For example, when an additional element is appended to a slice with a capacity of 5 and a length of 5, capacity expansion occurs, as shown below:

The capacity expansion operation is only concerned with the capacity. The original slice data will be copied to the new slice, and append will append the data after the expansion. As can be seen in the figure above, after expansion, len is still 5, but cap is changed from 5 to 10, and the data of the original slice is copied to the new slice. Capacity expansion follows the following basic rules:

If the original slice capacity is less than 1024, the new slice capacity will be doubled
If the original slice capacity is greater than or equal to 1024, the new slice capacity will be expanded by 1.25 times

Based on this rule, element types and memory allocation rules are considered, and the actual extended values are tweaked. You can see from this basic rule that Go is thinking about slice’s performance and space utilization.

When slicing is small, a large expansion speed is adopted to avoid frequent expansion and reduce the number of memory allocation times and the cost of data copy
When the slice is large, a smaller expansion speed is adopted, mainly to avoid wasting space

The implementation of adding an element to slice using append() is as follows:

Slice. Len++ returns slice
The capacity of the original slice is insufficient. Expand the slice first and obtain a new slice after the expansion
Append the new element to the new slice, slice.len++, returning the new slice

Slice a copy

When using the built-in function copy() to copy two slices, the data of the original slice will be copied one by one into the array pointed to by the target slice. The number of copies depends on the minimum length of the two slices. If the target slice capacity is insufficient, expansion will not occur.

summary

Each slice points to an underlying array
Each slice holds the length and capacity of the current slice
Time complexity of slice length calculated by Len () is O(1)
The time complexity of calculating slice capacity by cat() is O(1).
When you pass a slice through a function, you do not copy the entire slice because the slice itself is just a structure
Capacity expansion may occur when append() is used to add elements to slices, and new slices will be generated after capacity expansion

Here are a few programming tips worth noting:

If the capacity can be estimated during the creation of a slice, specify it as much as possible to avoid capacity expansion during the process of adding elements and improve performance
The Copy() function determines the actual number of copied elements during slice Copy. The length of the target slice may be insufficient, resulting in data loss
Use multiple slicing operations on the same array with caution to avoid read/write conflicts

Slice expression

Slice expressions can generate substrings based on a string, or slices from an array or slice. The Go language provides two expressions:

Array [low: high]
Extended expression: array[low: high: Max]

Simple expression

The most common expression is a simple expression of the form array[low: high]. If a is an array or a slice, this expression will cut the array elements in the range [low: High] and generate a new slice. If array is a string, the expression is slightly special in that it generates a string instead of a slice.

The length of the slice generated by the simple expression is high-low. For example, we use a simple expression to slice array and generate a new slice B:

Array :=[5]int{1,2,3,4,5} b := a[1:4]Copy the code

At this time, the length of section B obtained is 3, and the elements are:

b[0] ==2 
b[1] ==3 
b[2] ==4 
Copy the code

Underlying array sharing

According to the data structure of slices introduced earlier, we know that each slice contains three elements:

Type slice struct {array unsafe.Pointer // len int // cap int // size}Copy the code

It is important to note that slices generated using simple expressions share the underlying array with either the original array or the slice. The generation logic of a new slice can be expressed using the following pseudocode:

b.array = &array[low]
b.len = high - low
b.cap = len(a) = low
Copy the code

The boundary issue

If the object that the simple expression cuts is a string or an array, the values of low and high in the expression A [low: high] must satisfy the following relationship

0 <= low <= high < len(a)
Copy the code

If the object of a simple expression slice is a slice, then the maximum value of low and high in the expression A [low: high] can be the capacity of A, not the length of a:

a <= low <= high <= cap(a)
Copy the code

Cut the string

The expression a[low: high] creates a new slice when applied to an array, a slice, and a new string when applied to a string, not a slice.

This is due to the type difference between String and Slice, where slice supports random reads and writes while String does not.

The default value

In a[low: high], both low and high can be omitted for convenience.

The default value of low is 0, while the default value of high is the length of the object on which the expression is applied

A: [high] is equivalent to a [0: high] a [0:] is equivalent to a [0: len (a)] a [:] is equal to a [0: len (a)]Copy the code

Extended expression

Slices generated by simple expressions share the underlying array with the original array or slices, avoiding copying elements, saving memory space, and bringing the risk of read/write conflicts.

The new slice B (b := a[low: high]) not only reads and writes elements between a[low] and a[high-1], but also overwrites a[high] and subsequent elements when adding a new element x using the append(b,x) function. Such as:

A: = [5] int {1, 2, 3, 4, 5} : b = a (1:4) b = append (b, 0) / / at this point a [4] will be changed from 5 to 0Copy the code

Overlaying a[HIGH] and subsequent elements with a new slice can be unexpected, with disastrous results.

The Go team was aware of this risk early on, and in Go1.2 provided an expression to limit the capacity of new slices, called an extended expression:

a[low : high : max]
Copy the code

Max in the extended expression is used to limit the capacity of newly generated slices. The capacity of the new slice is max-low. The relationship between low, high and Max in the expression should be as follows:

o <= low <= high <= max <= cap(a)
Copy the code

For an array of length 10, the topology of the new slice generated by slicing two elements using the extended expression is shown below:

If you use a simple expression, the size of the slice in the figure above is 5, whereas if you use an extended expression, the size of the slice is limited to 2.

Extended expressions are common in low-level code, such as the Go source code. The slice generated by the extended expression has a limited storage capacity, and when append() is used to append elements to the slice, a new slice is created without overwriting the array or slice.

The a[low: high: Max] in the extended expression can only be omitted, and its default value is 0. This is different from simple expressions.

If high or Max is missing, a compilation error will occur.

summary

Slice expressions are divided into simple expressions A [low, high] and extended expressions A [low: high: Max].
Simple expressions generate new slices when applied to arrays, slices, and new strings when applied to strings
Extended expressions work only on arrays and slices, not strings

Dynamic array slice for Golang data structure