Optimal vector data structure?
Possible duplicate:
Data structure supporting O (1) random access and worst-case O (1) append?
I recently saw an answer on StackOverflow regarding a supposedly optimal data structure vector
("array list") which, if I recall correctly, lazily copied the elements onto a larger vector so that it doesn't cause a huge pause every time the vector is reallocated.
I remember that it needed O (sqrt (n)) extra space for bookkeeping, and that the answer was related to the article posted, but about that ... I find it very difficult to find it (you can imagine that searches such as optimal vector, they don't give me anywhere).
Where can I find the document?
source to share
I think the article you are linking to is Volatile Arrays in Optimal Time and Space by Brodnik et al. Their data structure uses the lazy copy dynamic array that you mentioned in your question as the building block for assembling this structure. There is this old Stack Overflow question describing a lazy copy data structure, which might be helpful to better understand how it works.
Hope this helps!
source to share