英文:
does append() always extend minimal capacity needed?
问题
当学习切片时，我有一个疑问：append()函数是否总是扩展最小所需容量？
a := make([]byte, 0)
a = append(a, 1, 2, 3)
cap(a) == 3 // 这个表达式总是成立吗？
// 或者这个假设可能不成立，因为append()函数的底层实现没有指定。
英文:
When learning slice, I have this doubt: does append() always extend minimal capacity needed?
a := make([]byte, 0)
a = append(a, 1, 2, 3)
cap(a) == 3 // will this be always true?
// or the assumption may not hold since the underlying implementation of append()
// is not specified.
答案1
得分: 3
不，在这种情况下不能保证。规范中说：
append(s S, x ...T) S // T 是 S 的元素类型
> 如果 s 的容量不足以容纳额外的值，append 会分配一个新的、足够大的切片，以适应现有切片元素和额外值。因此，返回的切片可能引用不同的底层数组。
（强调是我的）
在你的情况下，任何容量 >= 3 都足够大，所以你可以依赖 cap >= 3，但不能依赖 cap == 3。
当然，在这种情况下，你可以假设容量不会是 1e6 或 1e9 或 1e12。然而，具体的扩容（分配新的支持数组）策略故意没有详细说明，以允许编译器开发人员对这个机制进行一些实验。
英文:
No, it's not guaranteed in this case. The specifications say:
append(s S, x ...T) S // T is the element type of S
> If the capacity of s is not large enough to fit the additional values, append allocates a new, sufficiently large slice that fits both the existing slice elements and the additional values. Thus, the returned slice may refer to a different underlying array.
(Emphasizes mine)
In your case, clearly any capacity >= 3 is sufficiently large, so you can rely on cap >= 3, but you cannot rely on cap == 3.
Of course you can assume cap in this case will not be, say 1e6 or 1e9 or 1e12. However, the exact enlarging (allocating new backing array) strategy is intentionally not specified in every detail to allow the compiler guys to experiment with some knobs attached to this mechanism.
答案2
得分: 2
我要补充的是，它不仅不能保证切片的容量等于长度，事实上，对于较大的长度，结果切片的容量几乎从不等于长度。
append()被推广为vector包的替代品。为了做到这一点，追加的复杂度必须与vector包中的复杂度相匹配，这意味着追加一个元素的摊销复杂度必须为O(1)。尽管这种复杂度在语言规范中没有被保证，但它必须对于当前在Go社区中使用append()的模式来高效工作。
为了使append()的摊销复杂度为O(1)，每次空间不足时，它必须按照当前容量的固定百分比扩展容量。例如，容量加倍。想一想，如果每次空间不足时都加倍容量，只有当长度恰好是2的幂次方时，长度和容量才能相等（假设它最初是2的幂次方），这种情况并不常见。
英文:
I would add that, not only does it not guarantee that the capacity of the slice would be equal to the length, in fact, for large lengths, it would almost never be the case where the resulting slice would have capacity would equal the length.
append() is promoted as the replacement to the vector package. In order to do this, the complexity of appending must match the complexity in the vector package, which means that appending an element must have amortized O(1) complexity. Although this complexity is not guaranteed in the language specification, it must be true for the patterns for which append() is used now in the Go community to work efficiently.
In order for append() to be amortized O(1), it must expand the capacity by a fixed percentage of the current capacity each time it runs out of space. For example, doubling in capacity. Think about it, if it doubles in capacity every time it runs out, the length and capacity can only be the same if the length is exactly a power of 2 (assuming it started out as a power of 2), which is not frequent.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论