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

27 Jul 2009

      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