当前位置: 动力学知识库 > 问答 > 编程问答 >

go - Remove slice element within a for

问题描述:

An idiomatic method to remove an element i from a slice a, preserving the order, seems to be:

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

I was wondering which would be the best way to do it inside a loop. As I understand, it is not possible to use it inside a range for:

for i := range a { // BAD

if conditionMeets(a[i]) {

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

}

}

However it is possible to use len(a). [EDIT: this doesn't work, see answers below]

for i := 0; i < len(a); i++ {

if conditionMeets(a[i]) {

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

}

}

Is there a better or more idiomatic way than using len or append?

网友答案:

Your proposed solution is incorrect. The problem is that when you remove an element from a slice, all subsequent elements are shifted. But the loop doesn't know that you changed the underlying slice and loop variable (the index) gets incremented as usual, even though in this case it shouldn't because then you skip an element.

And if the slice contains 2 elements which are right next to each other both of which need to be removed, the second one will not be checked and will not be removed.

So if you remove an element, the loop variable has to be decremented manually! Let's see an example: remove words that start with "a":

func conditionMeets(s string) bool {
    return strings.HasPrefix(s, "a")
}

Solution (try it with all other examples below on the Go Playground):

a := []string{"abc", "bbc", "aaa", "aoi", "ccc"}
for i := 0; i < len(a); i++ {
    if conditionMeets(a[i]) {
        a = append(a[:i], a[i+1:]...)
        i--
    }
}
fmt.Println(a)

Output:

[bbc ccc]

Or better: use a downward loop and so you don't need to manually increment the variable, because in this case the shifted elements are in the "already processed" part of the slice.

a := []string{"abc", "bbc", "aaa", "aoi", "ccc"}
for i := len(a) - 1; i >= 0; i-- {
    if conditionMeets(a[i]) {
        a = append(a[:i], a[i+1:]...)
    }
}
fmt.Println(a)

Output is the same.

Alternate for many removals

If you have to remove "many" elements, this might be slow as you have to do a lot of copy (append() does the copy). Imagine this: you have a slice with 1000 elements; just removing the first element requires copying 999 elements to the front. Also many new slice descriptors will be created: every element removal creates 2 new slice descriptors (a[:i], a[i+1:]) plus a has to be updated (the result of append()). In this case it might be more efficient to copy the non-removable elements to a new slice.

An efficient solution:

a := []string{"abc", "bbc", "aaa", "aoi", "ccc"}
b := make([]string, len(a))
copied := 0
for _, s := range(a) {
    if !conditionMeets(s) {
        b[copied] = s
        copied++
    }
}
b = b[:copied]
fmt.Println(b)

This solution allocates a slice with the same length as the source, so no new allocations (and copying) will be performed. This solution can also use the range loop. And if you want the result in a, assign the result to a: a = b[:copied].

Output is the same.

In-place alternate for many removals (and for general purposes)

We can also do the removal "in place" with a cycle, by maintaining 2 indices and assigning (copying forward) non-removable elements in the same slice.

One thing to keep in mind is that we should zero places of removed elements in order to remove references of unreachable values so the GC can do its work. This applies to other solutions as well, but only mentioned here.

Example implementation:

a := []string{"abc", "bbc", "aaa", "aoi", "ccc"}
copied := 0
for i := 0; i < len(a); i++ {
    if !conditionMeets(a[i]) {
        a[copied] = a[i]
        copied++
    }
}
for i := copied; i < len(a); i++ {
    a[i] = "" // Zero places of removed elements (allow gc to do its job)
}
a = a[:copied]
fmt.Println(a)

Output is the same. Try all the examples on the Go Playground.

分享给朋友:
您可能感兴趣的文章:
随机阅读: