Re: [Boost-users] [Boost.CircularBuffer] begin()/end() arithmetic not working out quite right

Awesome! Thanks for the link to the specs. Unfortunately, looks like circular_buffer is not the way to go for me :-( I guess the picture is okay. I just got caught completely off guard. I thought I knew what I was doing when I jumped in (i.e. thinking the iterators would resemble std::vector), but then it turned out that my assumptions were wrong. This is just a thought, but I think there could be benefit for an alternative version of circular_buffer which supports iterators like std::vector. Thanks for the info, -David On Mon, Jul 27, 2009 at 1:32 AM, Jan Gaspar wrote:

Hi David,

here is the link to the containers library as defined by standard:

http://www.csci.csusb.edu/dick/c++std/cd2/lib-containers.html

The picture in the documentation is just descriptive (how else would you draw a circular buffer). It doesn't say anything about its internal implementation.

I'm afraid the way you want to use a circular buffer, this implementation is not applicable.

But have a look at the Bounded Buffer example

http://www.boost.org/doc/libs/1_39_0/libs/circular_buffer/doc/circular_buffe...

This is the right way how to use circular_buffer in procuder/consumer scenario.

Regards,

Jan

----- Original Message ---- From: David Baird To: Jan Gaspar Cc: boost-users@lists.boost.org Sent: Saturday, 25 July, 2009 22:25:46 Subject: Re: [Boost.CircularBuffer] begin()/end() arithmetic not working out  quite right

Hmmm, well, I think I understand what you are saying.  But it seems counter-intuitive to me that end() will always remain constant and that begin() will always move back.  Even this graphic here seems to indicate that end() moves:

   http://www.boost.org/doc/libs/1_39_0/libs/circular_buffer/doc/circular_buffe...    (from http://www.boost.org/doc/libs/1_39_0/libs/circular_buffer/doc/circular_buffe...)

Unfortunately, that makes it hard to use circular_buffer in some of our applications.  But I might be mistaken...

It seems that circular_buffer works great for this scenario:

   for(i = buf.begin(); i= buf.end(); ++i) { ... }

But my application is a little bit different from that.  Essentially, we have a serial data stream that is being observed by several processes.  There is one producer and many consumers.  Each consumer has its own iterator.  Our code is akin to this:

   // Make SIZE sufficiently large to obviate overflows:    const int SIZE = 1024;    char buf[SIZE];    int tail = 0;    int i1 = 0;    int i2 = 0;

   // Producer process:    while (true) { buf[tail++ % SIZE] = c; ... }

   // Consumer process 1:    while (true) {        while (tail != i1) { c = buf[i1++ % SIZE]; ... }    }

   // Consumer process 2:    while (true) {        while (tail != i2) { c = buf[i2++ % SIZE]; ... }    }

At first glance, this seemed like a perfect application for Boost::circular_buffer.  But when I delved in further, I just couldn't get the iterators to work out right in circular_buffer.  I thought that something like this would be appropriate, but yet this does not work:

   const int SIZE = 1024;    typedef circular_buffer<char> buf_type;    buf_type buf(size);

   buf_type::iterator i1 = buf.begin();    buf_type::iterator i2 = buf.begin();

   // Producer process:    while (true) { buf.push_back(c); ... }

   // Consumer process 1:    while (true) {        // i1 will always equal buf.end(), despite .push_back() being called       // ...thus, this fails:        while (buf.end() != i1) { c = *i1++; ... }    }

   // Consumer process 2:    while (true) {        while (buf.end() != i2) { c = *i2++; ... }    }

Do you think I am exceeding the intended application scope for circular_buffer here?

I don't know where to find the specifications for the semantics of begin()/end().  Can you direct me towards a link?  i've tried searching for things like "C++ container concepts" but that didn't yield any precise details about how begin()/end() should be affected by operations like push_back().  If I had to make a wild guess, I would guess that it actually isn't specified somewhere :-/

Thanks, David

On Wed, Jul 22, 2009 at 3:31 PM, Jan Gaspar wrote:

...

Ah ... one more thing ... I made a mistake in my previous reply.

...

you just cannot rely on this. I don't think standard says anything about begin() moving forward after push_back(). Correct me if I'm wrong.

should be read as

"you just cannot rely on this. I don't think standard says anything about end() moving forward after push_back(). Correct me if I'm wrong."

Sorry about the confusion.

Jan

----- Original Message ---- From: David Baird To: Jan Gaspar Cc: boost-users@lists.boost.org Sent: Wednesday, 22 July, 2009 22:30:13 Subject: Re: [Boost.CircularBuffer] begin()/end() arithmetic not working out  quite right

Hi Jan,

Thanks for your reply and sorry for taking so long to respond.

I am a bit confused by your response.  I never did expect begin() to move forward after push_back().  In my original post, what I said is that I expect begin() will remain constant and that **end() will move forward** each time push_back() is called.

My main question is this: why does end() remain constant when push_back() is called on a circular_buffer?  In other words, why does this assertion fail?:

  circular_buffer<int> buf(8);   circular_buffer<int>::iterator a;   circular_buffer<int>::iterator b;   a = buf.end();   buf.push_back(1);   b = buf.end();   assert(a != b); // fails

If I use an STL vector instead of circular_buffer, I get exactly the results I expect (as along as I call .reserve() on it prior, so that iterators are not invalidated by a realloc).

-David

On Thu, Jun 11, 2009 at 1:58 AM, Jan Gaspar wrote:

...

Hi David,

you just cannot rely on this. I don't think standard says anything about begin() moving forward after push_back(). Correct me if I'm wrong.

The way how it is implemented is that if the circular_buffer is empty begin() returns the same iterator as end().

There is also a note about iterator invalidation for push_back(): "Does not invalidate any iterators with the exception of iterators pointing to the overwritten element."

It means iterator 'a' in your first example will point to the same element as it was before calling push_back() - which is end(). This explains the behaviour you are describing.

Regards,

Jan

----- Original Message ---- From: David Baird To: Jan Gaspar ; boost-users@lists.boost.org Sent: Thursday, 11 June, 2009 1:01:54 Subject: [Boost.CircularBuffer] begin()/end() arithmetic not working out quite  right

Hi,

Firstly, thanks for the work on a circular buffer.  This is very useful since many of my applications require it.  I am having a problem though...

I am using Boost 1.38.0.  When I call push_back(), the iterator math makes it appear that begin() moves backwards and end() remains constant.  (Based on other STL libraries, I expect that begin() will remain constant and end() will keep advancing as I call push_back()).

In other words, this assertion fails (but I expect it to succeed):

   circular_buffer<int> buf(8);    circular_buffer<int>::iterator a;    circular_buffer<int>::iterator b;    a = buf.begin();    buf.push_back(1);    b = buf.begin();    assert(a == b); // Fails!!

Also, this code fails too (but I expect it to succeed):

   circular_buffer<int> buf(8);    circular_buffer<int>::iterator a;    circular_buffer<int>::iterator b;    a = buf.end();    buf.push_back(1);    b = buf.end();    assert(a != b); // Also fails!

Below is a full example that you can compile and try out:

#include #include

int main () {    typedef boost::circular_buffer<int> buf_type;    // Instead of "end" moving ahead, "begin" is moving backwards when //    // using "push_back".    {        buf_type buf1(1024);        buf_type::iterator a;        buf_type::iterator b;        a = buf1.end();        buf1.push_back(1);        buf1.push_back(2);        b = buf1.end();        printf ("%d\n", a == b);        // >>>        // got: 1        // expected: 0        printf ("%d, %d\n", a-buf1.begin(), b-buf1.begin());        // >>>        // got: 2, 2        // expected: 0, 2    }    {        buf_type buf2(1024);        buf_type::iterator c;        buf_type::iterator d;        c = buf2.begin();        buf2.push_back(1);        buf2.push_back(2);        d = buf2.begin();        printf ("%d\n", c == d);        // >>>        // got: 0        // expected: 1        // (i.e. "begin()" is not still pointing to first item!!        // This is incorrect, isn't it?)        printf ("%d, %d\n", buf2.end()-c, buf2.end()-d);        // >>>        // got: 0, 2        // expected: 2, 2    }    return 0; }

Thanks, David