go - go 没有内置的动态数组吗？

Question

我刚刚开始学习 go，我正在复习数据结构。我习惯于使用动态数组，例如 python 中的 list 或 C++ 中的 std::vector，但我在 go 中看不到任何类似的东西。动态数组的优点在于添加新元素的时间复杂度为 O(1)，索引的时间复杂度为 O(1)。

起初我以为slice就是它，但后来我意识到当我使用append时函数，整个 slice 被复制，因此它是一个 O(N) 操作，而不是动态数组中的 O(1)。

然后我遇到了list但这是一个双向链表，这意味着索引是 O(N)，而不是 O(1)。

我是否缺少我正在寻找的数据结构？

Answer 1

First I thought that slice is it, but the[n] I realized that when I used append function, the whole slice is being copied, and then therefore it is an O(N) operations as opposed to O(1) in dynamic array.

这是不正确的。

根据 The Go Programming Language Specification，append 检查支持 slice 的数组的容量，并且仅在内存不足时分配新内存(复制 slice )后备阵列中的房间。 [ link ] 我在规范中没有看到任何指定应分配多少内存的内容，但根据您链接到的博客文章，新内存块将是 slice 当前大小的 1.5 倍。这意味着，在重新分配/复制插入之后，接下来的 n/2 次插入将不需要需要重新分配/复制。整体效果被分摊到 O(1) 时间。这与您在其他语言中提到的示例使用的方法相同(Python 中的 list，C++ 中的 std::vector)。

所以， slice 正是您所需要的。