Discussion:
circular_buffer: rotate() vs erase_begin() for scalars
(too old to reply)
Robert Dailey
2017-01-18 18:00:10 UTC
Permalink
I'm using circular_buffer to represent a FIFO queue of bytes:

boost::circular_buffer<std::uint8_t> m_queue;

When I read bytes from the "front", I simply do:

m_queue.erase_begin(num_read_bytes);

I do so because the documentation for erase_begin() specifically
mentions constant time performance for scalar types since no
destructor needs to be called.

However, I feel that rotate() better expresses what I'm trying to do.
Is there a reason to prefer one over the other for scalar types?
Robert Dailey
2017-01-24 15:28:18 UTC
Permalink
On Wed, Jan 18, 2017 at 12:00 PM, Robert Dailey
Post by Robert Dailey
boost::circular_buffer<std::uint8_t> m_queue;
m_queue.erase_begin(num_read_bytes);
I do so because the documentation for erase_begin() specifically
mentions constant time performance for scalar types since no
destructor needs to be called.
However, I feel that rotate() better expresses what I'm trying to do.
Is there a reason to prefer one over the other for scalar types?
Would it be possible to get some feedback on this?
Maarten de Vries
2017-01-25 10:37:49 UTC
Permalink
Post by Robert Dailey
On Wed, Jan 18, 2017 at 12:00 PM, Robert Dailey
Post by Robert Dailey
boost::circular_buffer<std::uint8_t> m_queue;
m_queue.erase_begin(num_read_bytes);
I do so because the documentation for erase_begin() specifically
mentions constant time performance for scalar types since no
destructor needs to be called.
However, I feel that rotate() better expresses what I'm trying to do.
Is there a reason to prefer one over the other for scalar types?
Would it be possible to get some feedback on this?
​It sounds to me that what you want is erase_begin(). Rotate does not
remove the ​
​read bytes​ but puts them at the end of the sequence. It seems unlikely
that that is what you want.

That said, rotate is not guaranteed to be constant time. If the circular
buffer is not full it has to move elements around. The exact time
complexity can be found in the documentation. Look for "complexity" at
http://www.boost.org/doc/libs/1_63_0/doc/html/boost/circular_buffer.html#idp47282880-bb
.

Kind regards,
Maarten de Vries
Robert Dailey
2017-01-25 15:16:50 UTC
Permalink
Post by Robert Dailey
On Wed, Jan 18, 2017 at 12:00 PM, Robert Dailey
Post by Robert Dailey
boost::circular_buffer<std::uint8_t> m_queue;
m_queue.erase_begin(num_read_bytes);
I do so because the documentation for erase_begin() specifically
mentions constant time performance for scalar types since no
destructor needs to be called.
However, I feel that rotate() better expresses what I'm trying to do.
Is there a reason to prefer one over the other for scalar types?
Would it be possible to get some feedback on this?
It sounds to me that what you want is erase_begin(). Rotate does not remove
the
read bytes but puts them at the end of the sequence. It seems unlikely that
that is what you want.
That said, rotate is not guaranteed to be constant time. If the circular
buffer is not full it has to move elements around. The exact time complexity
can be found in the documentation. Look for "complexity" at
http://www.boost.org/doc/libs/1_63_0/doc/html/boost/circular_buffer.html#idp47282880-bb
Thank you very much for the response! The boost docs are very
difficult to navigate and understand, so I definitely missed the
details you described. I will continue using erase_begin().

Loading...