Re: [boost] Optimal Time and Space Vector

From: Thomas Holenstein (tholenst_at_[hidden])
Date: 2000-05-05 06:01:01

Hi,

 > 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...

I think most of the differences are described in Bill's answer.
Especially the point that a deque has worst-case O(N) push_back.
(With a very low constant!) If this is actually important in practice
remains to be seen.

Also the wasted space is O(N), asymptotically.  Here, too, it actually
remains to be seen if this is of practical importance.  I will make
some statistcs about this.  I will plot the used heap space
depending on the actual size of the container.

Bill writes:
 > 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.  

Actually, details about this are given in the technical report.  The
technical report is not yet available, but in the preview copy I have,
they describe it quite differently.

 > Element access is slower than with a traditional deque.  

Currently its much slower.  I should use assembler instructions to
compute the most significant bit set, instead I use a hack.

 > 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.

Thats about the iterators provided.  However, currently they use
integers, but this has to be changed to pointers, I can see this.

Tim says:
 > 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
Actually optvect comes from "(asymptotically) optimal vector", because
you cannot do any better asymptotically.  However, I like
compact_vector better.  But I will think about this later.  Maybe
someone has an even better proposal

Thomas