Boost logo

Boost :

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
> 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, gregod at, cpdaniel at, john at