RE: [boost] Optimal Time and Space Vector

From: Tim Sharrock (tim_at_[hidden])
Date: 2000-05-04 09:09:15

> From: Daniel Heck [mailto:dheck_at_[hidden]]
> > 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...

For large collections they are probably similar, but the design goal
of low wasted space is not explicit in deque, so the "page size" may
well be optimised for speed not size. In the STL that is supplied with
VC++6, for example, the page size seems to be typically 4096 bytes.

If your application has a few large deques that is fine, if you have many
thousands of short ones it is not....

I certainly feel the lack of space-optimised collections, so some boost
additions in this area would be most welcome.

I would perhaps suggest though, that "compact_vector" might be a better
name for this proposal, as it is optimised *differently* to std::vector,
rather than in all respects

Tim
-- 
Tim Sharrock   (tjsharrock_at_[hidden])