没有内置的动态数组吗？

Question

我刚开始接受go,我正在审视数据结构.我习惯拥有像listin python或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).

这是不正确的.

每转到编程语言规范,append将检查备份片阵列的容量,并且只分配新的内存(复制片),如果有没有足够的空间支持数组英寸 [ link ]我没有在规范中看到任何指定它应该分配多少内存的内容,但是根据您链接到的博客文章,新的内存块将是切片当前大小的1.5倍.这意味着,中,再分配/复制插入后,下一个Ñ/2的插入将不会需要重新分配/复制.总体效果是摊销O(1)时间.这与您在其他语言中提到的示例(list在Python中,std::vector在C++中)使用的方法相同.

因此,切片正是您所需要的.