使用嵌套的`append会导致副作用吗？

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切片。我用一些调试代码（请参见下文）对函数进行了一些修改，还发现了一种不会导致相同行为的解决方法（注释的代码）。

[我非常怀疑这是由引用传递而不是被复制而引起的（我将newSets的元素附加到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（如果非零）则由两部分组成：slice header指向某个后备数组并带有当前长度和容量，以及backing array。当append执行其工作时，可以选择：

在适当位置修改支持数组，并返回一个新的切片标头，以重新使用现有支持数组，或者
• 创建新的支持数组，将原始值复制到新的支持数组，并返回使用新的支持数组的新切片头。

每当append

副本

支持数组时，您的代码就会起作用。每当它re-uses后备数组时，您的代码可能会起作用，也可能不会起作用，这取决于某些其他slice头是否正在使用同一后备数组。例如，假设您的后备数组的长度为5，并且现有切片标头之一读取“长度1，容量5”，而后备数组的元素0保持为零。即，现有条带头h包含[0]。现在您呼叫append(h, 1)。 append操作将重新使用后备数组，并将1放入第二个元素，并返回一个包含h1的新切片头[0, 1]。现在，您将h

again

追加到2之后，制作一个包含h2的两元素切片[0, 2]。但是这将重复使用h1所使用的相同的后备数组，所以现在h1也拥有[0, 2]。要解决该问题而又不修改太多算法，您需要：

总是复制的append的变体，或
• 总是复制的
• 将一个整数附加到一个整数切片上的>]的变体。

后者更简单：

func setPlusInt(set []int, n int) []int {
    return append(append([]int(nil), set...), n)
}

这使您可以替换现有代码的一行。

（（我做了另一个小改动here，并添加了足够的内容以在Go Playground中提供一个可行的示例。]

（（另一种解决方案是设置每个自己的片头，以不提供额外的容量，因此append必须始终进行复制。我没有说明此方法。）