CODEWITHSUNDEEP
goslice
Timmmm
Timmmm

Reputation: 96556

Efficiently inserting a slice into another slice

In Go you can insert a slice into the middle of another slice like this:

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

However, as I understand it that will first append a[i:] to b by copying it to the end of b (and potentially reallocating b, and then copy that whole slice to a, again potentially reallocating it.

This seems like there is an extra copy and allocation to what you really need. In C++ I'd do it something like this (I mean... without using insert obviously).

// Reserve enough space in `a` for `a` and `b`.
a.reserve(a.size() + b.size());

// Move the second half of `a` to the end.
std::copy(a.begin() + i, a.end(), a.begin() + i + b.size());

// Copy `b` into the middle.
std::copy(b.begin(), b.end(), a.begin() + i);

Is there a similar way to do this in Go?

Upvotes: 2

Views: 214

Answers (1)

Thundercat
Thundercat

Reputation: 120941

Here's a translation to Go assuming a slice of int:

// Reserve space for the combined length of the slices
c := make([]int, len(a)+len(b))

// Copy the first part of a to the beginning
copy(c, a[:i])

// Copy the last part of a to the end
copy(c[i+len(b):], a[i:])

// Copy b to the middle
copy(c[i:], b)

playground example

To take advantage of a's capacity, do this:

if cap(a) < len(a)+len(b) {
    // Not enough space, allocate new slice
    c := make([]int, len(a)+len(b))

    // Copy the first part of a to the beginning
    copy(c, a[:i])

    // Copy the last part of a to the end
    copy(c[i+len(b):], a[i:])

    a = c
} else {
    // reslice to combined length
    a = a[:len(a)+len(b)]

    // copy the last part of a to the end
    copy(a[i+len(b):], a[i:])

}
// copy b to the middle
copy(a[i:], b)

playground example

Upvotes: 6

Related Questions