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: David Baird (dhbaird_at_[hidden])
Date: 2009-07-27 15:18:53

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<jano_gaspar_at_[hidden]> 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_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
>>>
>>>
>>>
>>>
>>>
>>
>>
>>
>>
>>
>
>
>
>
>