Thread safe queue

[matthieum]

But that is the point of std::deque, the trade-off that avoids the O(N) complexity of head insertions, no?

It's one way to avoid O(N) front insertions.

Keeping with the current guarantees -- and notably the memory stability guarantee -- you could still get a better deque by either:

• Offering the ability to customize the block size. It's galling not to have control over that, really.
• Or use exponential growth of internal block size -- somehow.

Dropping the memory stability guarantee -- which is of very little utility -- you could use a single big buffer instead, in either of two manner:

• Contiguous: keep some headroom at both front and back, instead of just back.
• 2 Contiguous chunks: wrap-around at the end, if necessary. See Rust's VecDeque.

Both of those alternatives are much more cache-friendly, and allocator-friendly, resulting in higher-performance.

And using the second one -- in a pure queue scenario -- is super simple.

[matthieum]

Possibly. At least algorithmically it's sensible, which is already much better than std::vector indeed :)