切片使用不当会导致意想不到的副作用

Question

我有以下函数可以生成给定数组的所有子集。

这个想法很简单 - 我从一个包含空集（切片）的结果数组开始，对于输入数组中的每个元素，nums遍历所有先前生成的集合，将其当前元素nums添加到其中，并将生成的新集合添加回结果数组。没有什么特别有趣的。

func subsets(nums []int) [][]int {

  result := [][]int{{}}

  for _, n := range nums {

    newSets := [][]int{}

    for _, set := range result {

      newSets = append(newSets, append(set, n))

    }

    result = append(result, newSets...)

  }

  return result

}

问题是使用append(newSets, append(set, n))会破坏result切片，切片是其中set的成员。我用一些调试代码（见下文）稍微修改了该函数，还找到了一个不会导致相同行为的解决方法（注释代码）。

我非常怀疑这是由通过引用传递而不是被复制的东西引起的（我正在附加newSetsto的元素result）。问题是我找不到它。:( 我从不改变循环中的结果，它遍历它。我也使用newSets每个循环的新实例。所以我不确定是什么原因造成的。请告知。:)

func subsets(nums []int) [][]int {

  result := [][]int{{}}

  for _, n := range nums {

    newSets := [][]int{}

    var before, after []int

    for _, set := range result {

      lastResultIdx := len(result)-1

      if lastResultIdx > 0 {

        before = make([]int, len(result[lastResultIdx]))

        copy(before, result[lastResultIdx])

      }

      //ns := []int{}

      //for _,v := range set {

      //  ns = append(ns, v)

      //}

      //ns = append(ns, n)

      //newSets = append(newSets, ns)

      newSets = append(newSets, append(set, n))

      if lastResultIdx > 0 {

        after = result[lastResultIdx]

        if before[len(before)-1]!=after[len(after)-1] {

          fmt.Println(n, "before", before, "after", after)

        }

      }

    }

    result = append(result, newSets...)

  }

  return result

}

func main() {

  subsets([]int{0, 1, 2, 3, 4})

}

Answer 1

问题在这里：append(newSets, append(set, n))问题不在于它是嵌套追加。问题是您假设append(set,n)将返回一个新切片。情况并非总是如此。切片是数组的视图，当您向切片添加新元素时，如果添加未导致数组重新分配，则返回的切片与您传入的切片相同，但len字段递增。因此，当您浏览结果数组时，您正在修改已经存在的元素，同时再次添加它们，就好像它们是不同的结果一样。要解决这个问题，当您获得 的元素时result，创建一个新切片，将 的元素复制result到其中，追加新元素，然后将新切片添加到result.

Answer 2

问题很简单：append接受一个切片参数[]T——对于某些类型T——当然还要加上要附加的元素，然后返回一个[]T结果。但是[]T，如果非零，则由两部分组成：指向某个后备数组并携带当前长度和容量的切片头，以及后备数组。它什么append时候工作，它有一个选择：就地修改后备数组，并返回一个新的切片头，它重用现有的后备数组，或者创建一个新的后备数组，将原始值复制到新的后备数组，并返回一个使用新后备数组的新切片头。每当append 复制后备数组时，您的代码都会起作用。每当它重新使用后备数组时，您的代码可能会或可能不会工作，这取决于其他切片标头是否使用相同的后备数组。例如，假设您的支持数组的长度为 5，并且现有切片标头之一读取“长度 1，容量 5”，支持数组的元素 0 为零。也就是说，现有的切片头h包含[0]. 现在你打电话append(h, 1)。追加操作重新使用后备数组并放入1第二个元素并返回一个新的切片头h1，其中包含[0, 1]. 现在你h 再次获取，追加2，并制作一个包含 的二元素h2切片[0, 2]。但这重用了与重用相同的支持数组，h1因此现在h1也适用[0, 2]。要在不大量修改算法的情况下解决问题，您需要：append总是复制的变体，或将一个 int 附加到始终复制的 int 切片的一种变体。后者更简单：func setPlusInt(set []int, n int) []int {     return append(append([]int(nil), set...), n)     }它使您可以替换现有代码的一行。（我在这里做了另一个微不足道的更改，并添加了足够的内容以在 Go Playground 中提供一个工作示例。）（另一种解决方案是设置您自己的每个切片标头以不提供额外容量，因此append必须始终复制。我没有说明这种方法。）