Re: [Boost-users] [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@yahoo.com> 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@gmail.com> To: Jan Gaspar <jano_gaspar@yahoo.com>; 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 <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
This is because iterator returned by end() has a special value. Actually it does not point to the internal buffer - it is just a marker. And it does not change. iterator end() { return iterator(this, 0); } Standard does not say anything about assert(a != b) must pass. Jan ----- Original Message ---- From: David Baird <dhbaird@gmail.com> To: Jan Gaspar <jano_gaspar@yahoo.com> 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<jano_gaspar@yahoo.com> 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@gmail.com> To: Jan Gaspar <jano_gaspar@yahoo.com>; 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 <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
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@gmail.com> To: Jan Gaspar <jano_gaspar@yahoo.com> 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<jano_gaspar@yahoo.com> 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@gmail.com> To: Jan Gaspar <jano_gaspar@yahoo.com>; 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 <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
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<jano_gaspar@yahoo.com> 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@gmail.com> To: Jan Gaspar <jano_gaspar@yahoo.com> 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<jano_gaspar@yahoo.com> 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@gmail.com> To: Jan Gaspar <jano_gaspar@yahoo.com>; 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 <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
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 <dhbaird@gmail.com> To: Jan Gaspar <jano_gaspar@yahoo.com> 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<jano_gaspar@yahoo.com> 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@gmail.com> To: Jan Gaspar <jano_gaspar@yahoo.com> 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<jano_gaspar@yahoo.com> 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@gmail.com> To: Jan Gaspar <jano_gaspar@yahoo.com>; 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 <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
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@yahoo.com> 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 <dhbaird@gmail.com> To: Jan Gaspar <jano_gaspar@yahoo.com> 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<jano_gaspar@yahoo.com> 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@gmail.com> To: Jan Gaspar <jano_gaspar@yahoo.com> 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<jano_gaspar@yahoo.com> 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@gmail.com> To: Jan Gaspar <jano_gaspar@yahoo.com>; 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 <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
participants (1)
-
David Baird -
Jan Gaspar