最佳向量数据结构？

Question

3

可能重复：支持O（1）随机访问和最坏情况下O（1）附加的数据结构？我曾经在StackOverflow上看到过一个关于证明为最优的“向量”（“数组列表”）数据结构的答案，如果我没记错的话，它会将元素延迟复制到更大的向量上，这样每次向量重新分配时就不会造成巨大的暂停。

我记得它需要O(sqrt(n))的额外空间进行簿记，并且答案链接到了一篇发表的论文，但仅此而已... 我正在极力搜索它（你可以想象搜索“最优向量”之类的内容对我毫无帮助）。

我该在哪里找到这篇论文？

- user541686

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

我认为你提到的那篇论文是Brodnik等人的“最优时间和空间可调整数组”。他们的数据结构使用了你在问题中提到的惰性复制动态数组作为组装该结构的基本模块。这里有Stack Overflow上的一个旧问题，描述了惰性复制数据结构，可能有助于更好地理解它的工作原理。

希望这能帮到你！