go 没有内置动态数组吗？

Question

我刚刚开始学习go，我正在研究数据结构。我习惯于使用像listinpython或std::vectorin这样的动态数组C++，但在go. 动态数组的优点是添加新元素的时间复杂度为 O(1)，索引的时间复杂度为 O(1)。

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

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

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

Answer 1

起初我以为slice是这样，但是 [n] 我意识到当我使用append函数时，整个切片都被复制，因此它是一个 O(N) 操作，而不是动态数组中的 O(1)。这是不正确的。根据Go 编程语言规范，append检查支持切片的数组的容量，如果支持数组中没有足够的空间，则仅分配新内存（复制切片）。[链接] 我在规范中没有看到任何内容指定应该分配多少内存，但根据您链接到的博客文章，新的内存块将是切片当前大小的 1.5 倍。即是，一个再分配后/复制插入装置，下一个Ñ / 2的插入将不会需要重新分配/复制。整体效果是摊销 O(1) 时间。这与您在其他语言（list在 Python 中，std::vector在 C++ 中）中提到的示例所使用的方法相同。因此，切片正是您所需要的。