Re: Optimal time and space vector class

[Raja R Harinath <harinath at cs dot umn dot edu>]

Thomas Holenstein <tholenst@iiic.ethz.ch> writes:
> Hello,
> 
>  > I'd like to take a look at this. Can you provide more information?
>  > - how did you test it?
>  > - how does the current implementation compare?
>  > - what kind of space/speed differences are there?
> I'm still working on it. I will provide all this information ASAP
> 
>  > - is it exception-safe, according to the Standard requirement?
>  > - does it use allocators properly?
>  > - does it conform to the amortized-constant allocation time requirement?
>  > - does it take advantage of the empty-base space optimization supported
>  >       under -fnew-abi?
> I hope so.  Probably not right now...
> 
>  > Also, does it still use a continious block of memory [...]?
> Definitely not.  This obiviously is not possible with the worst case
> O(1) push_back method.  On the other hand, elements are never copied
> in memory.

From what I could make out of the paper, the non-contiguous memory was
required to assure O(sqrt(n)) extra space.  

The same paper provides a way to maintain O(1) push_back with O(n)
extra space (w/ a very large constant).  The technique basically
stands the amortized analysis of "doubling" on its head, and
effectively executes the operations paid for by the insert _with_ the
insert.  This however requires maintaining a double length buffer
along with the current buffer, and switching to it on overflow.

- Hari
-- 
Raja R Harinath ------------------------------ harinath@cs.umn.edu
"When all else fails, read the instructions."      -- Cahn's Axiom
"Our policy is, when in doubt, do the right thing."   -- Roy L Ash