Date: 2000-07-24 02:25:04
Greg Colvin writes:
> Thanks for the good work.
> Reading the motivating paper you reference at
> 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
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk