Menu
The VecDeque documentation says that it uses a growable ring buffer as implementation.
How does it work internally?
push_back and pop_front), when is the shifting done? Each time I call pop_front? When the internal buffer reaches a critical size?
541
A circular queue is essentially a queue with a maximum size or capacity which will continue to loop back over itself in a circular motion. Ring Buffers are common data structures frequently used when the input and output to a data stream occur at different rates. Circular Queues offer a quick and clean way to store FIFO data with a maximum size.
A Ring Buffer is implemented using a fixed-size array that wraps around at the boundaries. Apart from the array, it keeps track of three things: and the end of the array – the point at which the buffer wraps around to the start of the array The mechanics of how a ring buffer handles these requirements vary with the implementation.
The “default” usage of this type as a queue is to use push_back to add to the queue, and pop_front to remove from the queue. extend and append push onto the back in this manner, and iterating over VecDeque goes front to back. Since VecDeque is a ring buffer, its elements are not necessarily contiguous in memory.
The ring buffer's first-in first-out data structure is useful tool for transmitting data between asynchronous processes. Here's how to bit bang one in C without C++'s Standard Template Library. The ring buffer is a circular software queue.
TL;DR:
The VecDeque has 2 internal indices: one for the head and one for the tail. When you push or pop things into/from the VecDeque, either the head or tail is incremented/decremented accordingly.
Let's see what happen where there is one call to push_back and pop_front.
T H
Before [o o o o . . . . ]
T H
After [. o o o o . . . ]
You just wrap the buffer around. The buffer is now split in two parts.
H T
Before [. . . . o o o o ]
H T
After [o . . . . o o o ]
When the internal buffer is filled and you push another thing, you have three scenarios described in the code:
The buffer only grows.
T H
Before [o o o o o o o . ]
T H
After [o o o o o o o . . . . . . . . . ]
After the buffer grows, the head is moved after the tail.
H T
Before [o o . o o o o o ]
T H
After [. . . o o o o o o o . . . . . . ]
After the buffer grows, the tail is moved to the end of the buffer.
H T
Before [o o o o o . o o ]
H T
After [o o o o o . . . . . . . . . o o ]
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With