Golang SliceTricks, documented

This is a fork of the SliceTricks page of the golang wiki, but with documentation for each of the "tricks." I believe that documentation has been omitted because the names refer to the old container/vector, but that package no longer exists in the standard library, so you can't find it on godoc. I created this by referring to this archive.org cache, (TODO: find git commit).

AppendVector

a = append(a, b...)

AppendVector appends the entire vector x to the end of this vector.

Copy

b = make([]T, len(a))
copy(b, a)
// or
b = append([]T(nil), a...)
// or
b = append(a[:0:0], a...)  // See https://github.com/go101/go101/wiki

Cut

a = append(a[:i], a[j:]...)

Cut deletes elements i through j-1, inclusive.

Delete

a = append(a[:i], a[i+1:]...)
// or
a = a[:i+copy(a[i:], a[i+1:])]

Delete deletes the i'th element of the vector. The gap is closed so the old element at index i+1 has index i afterwards.

Delete without preserving order

a[i] = a[len(a)-1] 
a = a[:len(a)-1]

NOTE If the type of the element is a pointer or a struct with pointer fields, which need to be garbage collected, the above implementations of Cut and Delete have a potential memory leak problem: some elements with values are still referenced by slice a and thus can not be collected. The following code can fix this problem:

Cut

copy(a[i:], a[j:])
for k, n := len(a)-j+i, len(a); k < n; k++ {
	a[k] = nil // or the zero value of T
}
a = a[:len(a)-j+i]

Delete

copy(a[i:], a[i+1:])
a[len(a)-1] = nil // or the zero value of T
a = a[:len(a)-1]

Delete without preserving order

a[i] = a[len(a)-1]
a[len(a)-1] = nil
a = a[:len(a)-1]

Expand

a = append(a[:i], append(make([]T, j), a[i:]...)...)

Insert j elements at position i.

Extend

a = append(a, make([]T, j)...)

Insert j elements at the end of a vector.

Insert

a = append(a[:i], append([]T{x}, a[i:]...)...)

Insert inserts into the vector an element of value x before the current element at index i.

NOTE The second append creates a new slice with its own underlying storage and copies elements in a[i:] to that slice, and these elements are then copied back to slice a (by the first append). The creation of the new slice (and thus memory garbage) and the second copy can be avoided by using an alternative way:

Insert

s = append(s, 0 /* use the zero value of the element type */)
copy(s[i+1:], s[i:])
s[i] = x

InsertVector

a = append(a[:i], append(b, a[i:]...)...)

InsertVector inserts into the vector the contents of the vector b such that the 0th element of b appears at index i after insertion.

Push

a = append(a, x)

Push appends x to the end of the vector.

Pop

x, a = a[len(a)-1], a[:len(a)-1]

Pop deletes the last element of the vector, returning it as x.

Push Front/Unshift

a = append([]T{x}, a...)

Pop Front/Shift

x, a = a[0], a[1:]

Additional Tricks

Filtering without allocating

This trick uses the fact that a slice shares the same backing array and capacity as the original, so the storage is reused for the filtered slice. Of course, the original contents are modified.

b := a[:0]
for _, x := range a {
	if f(x) {
		b = append(b, x)
	}
}

For elements which must be garbage collected, the following code can be included afterwards:

for i := len(b); i < len(a); i++ {
	a[i] = nil // or the zero value of T
}

Reversing

To replace the contents of a slice with the same elements but in reverse order:

for i := len(a)/2-1; i >= 0; i-- {
	opp := len(a)-1-i
	a[i], a[opp] = a[opp], a[i]
}

The same thing, except with two indices:

for left, right := 0, len(a)-1; left < right; left, right = left+1, right-1 {
	a[left], a[right] = a[right], a[left]
}

Shuffling

Fisher–Yates algorithm:

Since go1.10, this is available at math/rand.Shuffle

for i := len(a) - 1; i > 0; i-- {
    j := rand.Intn(i + 1)
    a[i], a[j] = a[j], a[i]
}

Batching with minimal allocation

Useful if you want to do batch processing on large slices.

actions := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
batchSize := 3
var batches [][]int

for batchSize < len(actions) {
    actions, batches = actions[batchSize:], append(batches, actions[0:batchSize:batchSize])
}
batches = append(batches, actions)

Yields the following:

[[0 1 2] [3 4 5] [6 7 8] [9]]

In-place deduplicate (comparable)

import "sort"

in := []int{3,2,1,4,3,2,1,4,1} // any item can be sorted
sort.Ints(in)
j := 0
for i := 1; i < len(in); i++ {
	if in[j] == in[i] {
		continue
	}
	j++
	// preserve the original data
	// in[i], in[j] = in[j], in[i]
	// only set what is required
	in[j] = in[i]
}
result := in[:j+1]
fmt.Println(result) // [1 2 3 4]

fordhurley/slicetricks.md