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

[Jonathan Wakely <jwakely dot gcc at gmail dot com>]

On 22 January 2014 01:52, Joachim Achtzehnter wrote:
> After looking at the implementation some more, it does seem to use a
> circular buffer of sorts, so I was wrong about this point, but there are
> still ongoing heap allocations. These seem to happen because it is freeing a
> node as soon as elements migrate to the next node in the circular buffer.
>
> This means I need to slightly adjust my question. If I understand correctly,
> the problem is that the implementation is too eager to free its nodes. C++11
> has added shrink_to_fit, which was probably intended as a way to allow
> implementations to avoid deallocation, while still providing a way to
> reclaim space, although only by explicit request. The standard still doesn't
> seem to specify enough to guarantee that there won't be ongoing allocations
> even when the contents of a queue remains bounded.

shrink_to_fit() was added purely as standard way to do "the
copy-and-swap idiom", it was not intended to affect how std::deque is
implemented.

The primary use case of std::deque is as std::deque, not std::queue.
However, there could be advantages for both if we retained up to one
free node for future use.  That would require some "cleverness" to do
without increasing the size of the std::deque objects though.

Note that if you want to recycle nodes you can already do so, by
providing a custom allocator.

> Are there any plans to change the current behaviour?

No, I don't think so.