3

Possible Duplicate:
A data structure supporting O(1) random access and worst-case O(1) append?

I saw an answer a while ago on StackOverflow regarding a provably optimal vector ("array list") data structure, which, if I remember correctly, lazily copied elements onto a larger vector so that it wouldn't cause a huge pause every time the vector reallocated.

I remember it needed O(sqrt(n)) extra space for bookkeeping, and that the answer linked to a published paper, but that's about it... I'm having a really hard time searching for it (you can imagine that searches like optimal vector are getting me nowhere).

Where can I find the paper?

4

1 回答 1

2

我认为您所指的论文是Brodnik 等人的“Resizable Arrays in Optimal Time and Space” 。他们的数据结构使用您在问题中提到的惰性复制动态数组作为构建此结构的构建块。Stack Overflow 上有一个较早的问题，描述了延迟复制数据结构，这可能有助于更好地了解它的工作原理。

希望这可以帮助！

于 2013-01-26T20:14:30.573 回答