STL deque: keep minimum size

Question

I am using an STL deque structure and at each iteration of my algorithm, I am removing n elements from the front and adding n elements at the end. So, basically, my deque size never changes and I am doing millions of iterations.

Is there a way to ensure that the memory size does not change (or at least does not go down) during its lifetime? Perhaps due to the underlying implementation of the deque perhaps this is unavoidable but I wanted to make sure.

What you're looking for is a circular buffer or ring buffer. std::deque doesn't implement this, and your scenario will most certainly require allocations and deallocations frequently. Have a look at Boost.Circular Buffer - If you don't like boost, or want to implement your own circular buffer, the documentation is still worth reading. It explains how such a buffer works. It can be implemented with std::vector pretty easily. — leemes
@Luca See my recent comment edit. No, not STL per se, but boost, which is "quasi-pre-standard" in some parts. — leemes
The idea to use vector as the base for a circular buffer implementation is to use it "as a ring". So you don't remove elements from the beginning, but you simply "rotate" the start index. This makes space at the end to append new elements. That means, the indexing in the circular buffer and that to the vector have a varying offset. Read the documentation of Boost.Circular Buffer and you know what I mean. — leemes
@Luca you do not have to remove elements from vector, you can replace them with empty elements for example, then just keep iterator to head and tail. — Slava
You could certainly implement a circular buffer using any number of base containers, but vector will be the most efficient. Don't start with deque. — Mark Ransom

shreyans800755 shreyans800755 · Accepted Answer · 2018-06-10T21:57:46

No, you can't always expect that behaviour. Those are implementation specific details. I don't think there is any specification in the standard that mandates this behaviour.

However, there's another solution. You can use circular buffer in boost. (Docs: https://www.boost.org/doc/libs/1_67_0/doc/html/circular_buffer.html) It provides one of the most optimised implementation for the exact functionality that you require. It will allocate the memory on construction with the given size(because its constant as you mentioned). And on calling and pop_{front/back}, it doesn't deallocate the memory nor does it allocate on push_{front/back}. It just shifts the begin and end iterator to point to appropriate member.

So, all the operations that you require will be O(1). It also provides spatial locality and thus making traversal quite fast.

STL deque: keep minimum size

1 Answers