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

Subject: Re: [Boost-users] [Boost.CircularBuffer] begin()/end() arithmetic not working out quite right
From: Jan Gaspar (jano_gaspar_at_[hidden])
Date: 2009-07-27 03:32:01

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_buffer.html#examples

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

Regards,

Jan





----- Original Message ----
From: David Baird <dhbaird_at_[hidden]>
To: Jan Gaspar <jano_gaspar_at_[hidden]>
Cc: boost-users_at_[hidden]
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_buffer.png
    (from http://www.boost.org/doc/libs/1_39_0/libs/circular_buffer/doc/circular_buffer.html)

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<jano_gaspar_at_[hidden]> 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 <dhbaird_at_[hidden]>
> To: Jan Gaspar <jano_gaspar_at_[hidden]>
> Cc: boost-users_at_[hidden]
> 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<jano_gaspar_at_[hidden]> 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 <dhbaird_at_[hidden]>
>> To: Jan Gaspar <jano_gaspar_at_[hidden]>; boost-users_at_[hidden]
>> 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 <boost/circular_buffer.hpp>
>> #include <stdio.h>
>>
>> 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
>>
>>
>>
>>
>>
>
>
>
>
>