Re: [boost] compact_vector (was optvect)

From: tholenst_at_[hidden]
Date: 2000-07-24 02:25:04

Greg Colvin writes:
 > Thanks for the good work.
 > 
 > Reading the motivating paper you reference at
 > http://daisy.uwaterloo.ca/~eddemain/papers/WADS99a/
 > I see that the authors claim that their data structures can
 > be easily extended to handle a deque interface.  

Yes, they write that.  They also write that details can be looked at
in their technical report.  The technical report is not yet available, 
but I have a premature version.  There they describe a completely
different technique to implement a deque.  It seems to me that this
technique is probably slower and needs more memory, but I am no way
sure of it.  It probably has to be implemented, if you want to know
it.  However, with the other methods, elements are moved in memory.

 > So I wonder whether it would degrade the speed of your
 > implementation to provide a deque interface?  
It would be a different implementation.

 > The authors also say that they
 > would like to see their ideas incorporated into the standard
 > C++ library.  So I also wonder if we should make contact with
 > the authors for their input?
I already contacted the libstdc++-v3 group.  But vector will
(probably) soon require all elements to be allocated in one chunk.
So compact_vector is no way to go.

 > Looking at your performance numbers I had to wonder why your
 > operator[] was so much faster than the deque you tested, and
 > why your push_back was so much slower.  Is it fundamental to
 > the data structures used, or an accident of implementation?

With the operator[], I guess this is a bug in the libstdc++-v3
implementation.  I don't see a reason why this should be slower in a
deque.

The push_back seems logical to me.  A push_back operation in a deque
is much more easy than in a compact_vector, because compact_vector
needs to update more information than a deque.

Thomas