RE: [boost] Optimal Time and Space Vector

From: Bill Wade (bill.wade_at_[hidden])
Date: 2000-05-04 08:40:17

> From: Daniel Heck [mailto:dheck_at_[hidden]]
> Sent: Thursday, May 04, 2000 7:40 AM
> To: boost_at_[hidden]
> Subject: Re: [boost] Optimal Time and Space Vector
>
>
> Hi,
>
> > Below, I summarize the advantages and disadvantages of optvect:
> >
> >  + Worst Case O(1) push_back, pop_back, operator[]
> >  + Always O(sqrt(n)) wasted space
> >  + Elements are not copied in memory if you don't move it
> >
> >  - Element access is slower
> >  - Elements are not stored in one chunk
>
> Only one question: How does your class compare to the standard deque<>
> class? It seems optvec and deque are quite similar in their advantages and
> disadvantages...

A typical deque will have O(N) worst-case push_back.  However the techniques
described in http://daisy.uwaterloo.ca/~eddemain/papers/WADS99a/ could be
applied to make worst-case deque push-back O(1).

A typical deque has O(N) wasted space.  I believe the paper claims that the
techniques described can be used to meet std::deque requirements (O(1)
random access and push at either end), but with only O(sqrt(N)) extra space.
However, details aren't given in this paper, and the results may require
that existing elements sometimes be moved (which would violate an std::deque
requirement).

Element access is slower than with a traditional deque.  You can probably
iterate through this structure as fast (or faster) than you can iterate
through a deque (especially when N is large), but that would require
relatively large iterators (about 4 pointers/iterator).  I haven't looked at
Thomas Holenstein's code to see what (if any) iterators he provided.

Thomas, thanks for bringing this interesting data structure to our
attention.