std::deque implementation seems non-optimal for use with std::queue

[Joachim Achtzehnter <joachima at netacquire dot com>]

With std::deque being the default implementation of std::queue it would 
be useful if the implementation was optimized for repeated push at one 
end and pop at the opposite end.

For example, if such a queue was kept at approximately constant size one 
would hope to avoid further heap allocations once a certain amount of 
allocations have occurred. If the array of pointers to blocks was 
managed as a circular buffer it would not be necessary to perform any 
further heap allocations once all blocks are allocated.

The libstdc++ implementation of std::deque does not seem to work this 
way (at least in v4.7.3). A program that repeatedly pushes and pops, for 
example with always either 1 or 2 elements contained in the queue, seems 
to encounter repeated allocations and deallocations from the underlying 
std::deque.

I've seen another implementation of std::deque, which does use a 
circular buffer. With this implementation a std::queue whose size 
remains limited does run without further heap allocations once the 
elements have cycled around the circular buffer once.

Are there significant drawbacks to the circular buffer approach that 
argue against its use for std::deque? Or would this be a worthwhile 
improvement to consider?

Thanks,

Joachim

--
joachima@netacquire.com http://www.netacquire.com