Remove and adding elements to array in GO lang

Question

I have 2 arrays declared as : var input []string and var output []string .

The input array is filled with some IDs initially. Output array is NULL.

After every iteration I want to remove a random element from input array and add it to output array.

At the end all the elements in output array will be same as input array (but with different ordering(indexing)).

for index := 0; index < len(input); index++ {
    if !visited[index] {
        //do something
    }
}
output[#iteration index] = input[current index]

When I try to do this, I get array out of bounds error.

Solution 1

For the output array you need to use append or allocate it with an initial capacity to match the size of input.

// before the loop
output := make([]string, len(input))

would be my recommendation because append causes a bunch of needless reallocations and you already know what capacity you need since it's based on the input.

The other thing would be:

output = append(output, input[index])

But like I said, from what I've observed append grows the initial capacity exponentially. This will be base 2 if you haven't specified anything which means you're going to be doing several unneeded reallocations before reaching the desired capacity.

Solution 2

You could find some useful tricks at golang/SliceTricks.

Since the introduction of the append built-in, most of the functionality of the container/vector package, which was removed in Go 1, can be replicated using append and copy.

Here are the vector methods and their slice-manipulation analogues:

a = append(a, b...)

b = make([]T, len(a))
copy(b, a)
// or
b = append([]T(nil), a...)

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

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

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]

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

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

a = append(a[:i], append([]T{x}, a[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)
copy(s[i+1:], s[i:])
s[i] = x

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

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

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

a = append(a, x)

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

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

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

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)
    }
}

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:

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