[boost] Re: Review Request: cyclic_buffer
I'm afraid I'm asking somebody else to do work here though. I've got a resizing circular buffer (Metrowerks::cdeque has shipped with CodeWarrior for years), but I'm not at liberty to share the source. I'm busy too, on my agenda is a 2-dimensional circular buffer concept - which led me to revisit boost, and start lurking on gmane.comp.lib.boost.devel. I think if Jan goes ahead with non-autoresizing circular_buffer, I might use that as a basis for my 2-dimensional variant. (A 2d sliding window caching kind of problem) With Jan's permission/blessing obviously Perhaps better not to infringe on Metrowerks unless absolutely no consensus can be formed by patient debate... :-) The conceptual process here has been a big help for me to crystalise some aspects of circular buffers, I genuinely think that circular_buffer and circular_deque would both be worthy additions to boost, once refined. ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: Review Request: cyclic_buffer
deque is more expensive than a resizing circular buffer in both performance and code size. One also can not control *when* deque will allocate as one can with a resizing circular buffer. In a nutshell, a resizing circular buffer is often a better deque than std::deque is. ;-( A resizing circular buffer is absolutely awesome when plugged into std::queue. If your queue on average doesn't constantly grow, a resizing circular buffer is efficient, predictable and safe. A std::deque in std::queue will likely continually rellocate buffers as it drops one off one end and adds one to the other (and at annoyingly unpredictable times if you're doing real-time). Howard, I can see the appeal here in using a circular buffer in this manner, while at the same time I'm cooling against the compromise of insert auto-resizes, while push doesn't which seems inconsistant. Given that we both seem to have a real-time orientation, we're probably not so far apart in our thinking. Perhaps we simply need to make a distinction between a circular_buffer and a circular_deque which are only different in terms of resizing semantics. Each provides different characteristics, and stand independently as boost containers. Code re-use by itself doesn't seem to be a good enough reason to mix the concepts and overload the namespace unnecessarily. One idea that came to my mind was to have forward insertion, backward insertion to resolve the question of semantics of arbitrary insertion into a circular_buffer. insert() pushes rightmost items forwards, overwriting leftmost items as necessary. rinsert() pushes leftmost items backwards, overwriting rightmost items as necessary. Likewise for the circular_deque which would reallocate as necessary to accomodate any kind of insertion - items would never be implicitly lost by a circular_deque. Nigel ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Review Request: cyclic_buffer
On Thursday, June 12, 2003, at 12:43 PM, Nigel Stewart wrote: I can see the appeal here in using a circular buffer in this manner, while at the same time I'm cooling against the compromise of insert auto-resizes, while push doesn't which seems inconsistant. Given that we both seem to have a real-time orientation, we're probably not so far apart in our thinking. Perhaps we simply need to make a distinction between a circular_buffer and a circular_deque which are only different in terms of resizing semantics. Each provides different characteristics, and stand independently as boost containers. Code re-use by itself doesn't seem to be a good enough reason to mix the concepts and overload the namespace unnecessarily. I'm beginning to think you're correct. An informed process would be to create both containers, and adapt both types to the other, and measure the results. I'm afraid I'm asking somebody else to do work here though. I've got a resizing circular buffer (Metrowerks::cdeque has shipped with CodeWarrior for years), but I'm not at liberty to share the source. And my schedule is tight enough that even higher priority things are slipping right now, so I can't donate cycles to a non-resizing variant to compare to. One idea that came to my mind was to have forward insertion, backward insertion to resolve the question of semantics of arbitrary insertion into a circular_buffer. insert() pushes rightmost items forwards, overwriting leftmost items as necessary. rinsert() pushes leftmost items backwards, overwriting rightmost items as necessary. Likewise for the circular_deque which would reallocate as necessary to accomodate any kind of insertion - items would never be implicitly lost by a circular_deque. This sounds very interesting for the non-resizing version. I think for the resizing version, the insert should simply minimize the elements that it is going to move. Either way, all pointers and iterators must be considered invalidated (unlike the non-resizing variant with insert and rinsert). In my mind, when you insert into the middle of a resizing circular buffer, the behavior (mental model) is very deque-like, except of course for the ability to predict whether it will require a reallocation or not. -Howard ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Review Request: cyclic_buffer
Hi all Cyclics! I want to summarize what we have till now. What should be changed in the proposed cyclic_buffer. - Rename to circular_buffer. - Add push_front() and pop_front(). - resize() to behave similarly to vector::resize(). - change_capacity() becomes again change_capacity(). I think the name change_capacity best reflects what the method really does. The vector::reserve() can only increase the capacity, never decrease - which may be confusing. And at last the circular_buffer is not vector so it can have different methods from vector. - insert() will always increase the size and possibly can increase the capacity (if not sufficient). Regards, Jan ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: Review Request: cyclic_buffer
Hey, I'm keen on a circular argument... :-) - Rename to circular_buffer. Agree. - Add push_front() and pop_front(). Agree. - resize() to behave similarly to vector::resize(). Agree. That means items will be lost from the right end, if necessary. Or, capacity will be increased, if necessary. - change_capacity() becomes again change_capacity(). I think the name change_capacity best reflects what the method really does. The vector::reserve() can only increase the capacity, never decrease - which may be confusing. And at last the circular_buffer is not vector so it can have different methods from vector. set_capacity()? Agree. Make it clear in the documentation about how change_capacity()/set_capacity() is different to reserve() because of the possibility of data being removed to fit the specified capacity. A std::vector::reserve call is a hint, while a circular_buffer::change_capacity/set_capacity is a hard limit. - insert() will always increase the size and possibly can increase the capacity (if not sufficient). Agree. We should document that circularity (and related constant-time guarantees) applies to push/pop, but not insert. (or erase?) This strikes me as a good compromise. For one thing, it leaves the door open to inserting in a manner that resizes the capacity. (Except for the problem that if the buffer is full, every insert will require O(n) time) --- The thread in relation to automatic resizing has not yet settled, but I would suggest going ahead and doing a rev while that one settles down. --- If you think there is a meaningful way that I can help you out over the weekend, let me know. (Linux, Cygwin, MSVC 6, 7, Solaris, etc...) Regards, Nigel Stewart ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: Review Request: cyclic_buffer
This strikes me as a good compromise. For one thing, it leaves the door open to inserting in a manner that resizes the capacity. (Except for the problem that if the buffer is full, every insert will require O(n) time) I later realised an important point: insert will be O(n) anyway, given the need to make room for the inserted items. So, it seems that allowing automatic resizing in this case does not cost anything in terms of performence implications. ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
RE: [boost] Re: Review Request: cyclic_buffer
| -Original Message- | From: [EMAIL PROTECTED] | [mailto:[EMAIL PROTECTED] Behalf Of Nigel Stewart | Sent: Wednesday, June 11, 2003 2:03 AM | To: [EMAIL PROTECTED] | Subject: [boost] Re: Review Request: cyclic_buffer | | The generally accepted concept of a circular buffer | is a fixed size contiguous memory buffer. Following | the principle of least surprise a circular_buffer | should not decide to resize itself. On the Keep It Simple Sir principle, I agree with this. Indeed, I think that most uses specifically require a fixed at construction size, and I suspect the code will be smaller, faster and correcter if this is the specification. Paul Paul A Bristow, Prizet Farmhouse, Kendal, Cumbria, LA8 8AB UK +44 1539 561830 Mobile +44 7714 33 02 04 Mobile mailto:[EMAIL PROTECTED] mailto:[EMAIL PROTECTED] ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Review Request: cyclic_buffer
On Wednesday, June 11, 2003, at 05:55 PM, Dave Gomboc wrote: Why is a deque inadequate? deque is more expensive than a resizing circular buffer in both performance and code size. One also can not control *when* deque will allocate as one can with a resizing circular buffer. In a nutshell, a resizing circular buffer is often a better deque than std::deque is. ;-( A resizing circular buffer is absolutely awesome when plugged into std::queue. If your queue on average doesn't constantly grow, a resizing circular buffer is efficient, predictable and safe. A std::deque in std::queue will likely continually rellocate buffers as it drops one off one end and adds one to the other (and at annoyingly unpredictable times if you're doing real-time). -Howard ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Review Request: cyclic_buffer
Hi Howard!
I like your idea. But (referring to the Nigel Stewart's posting) what would you
propose for the insert? Should I not provide it?
Jan
Howard Hinnant wrote:
In article [EMAIL PROTECTED], Alisdair Meredith
[EMAIL PROTECTED] wrote:
| The one true circular buffer template is a nigh impossible goal,
| because it means so many things to different people.
snip
| I would certainly like the documentation to explain the tradeoffs made
| in the implementation, and why this particular variation was chosen as
| most appropriate for the general case.
Indeed! Excellent post!
Perhaps container adaptors could be applied to a sufficiently
generalized circular buffer.
What is the one true queue? There isn't one. It is best a container
adaptor (policy based if you prefer). I suspect that a more general
circular buffer, restricted by various adaptors, might serve more uses
with less code.
The circular buffer I've needed (and coded) fits none of aforementioned
descriptions. But it is a circular buffer nonetheless.
For my money, the general circular buffer is one that exists in a
contiguous array, but with an arbitrary begin and end within that
array, capable of wrapping around the end of the physical memory:
+---+---+---+---+---+---+---+---+---+---+
| 4 | 5 | | | | | 0 | 1 | 2 | 3 |
+---+---+---+---+---+---+---+---+---+---+
^ ^
| |
endbegin
Constant time push/pop_front, constant time push/pop_back. When begin
and end collide, reallocation automatically happens vector-like.
This data structure can be efficiently coded with a 4-word data
structure. For example: data_ptr, capacity, size, begin_ptr (there
are other variations that also only take 4 words).
From this you can write adaptors to constrain capacity, have push_back
overwrite front(), throw an exception on size() exceeding capacity(),
or whatever else you need to do.
You can't adapt any other std::container to do this job because vector
is the only one with capacity, but vector doesn't have a constant time
push/pop_front. But I believe you can adapt the above described
container to meet the needs of other circular buffer requirements.
For example:
template class T, class Container = general_cyclic_bufferT
class my_cyclic_buffer
{
public:
// typedefs ...
my_cyclic_buffer(size_type cap) {c.reserve(cap);}
reference operator[](size_type n) {return c[n];}
// etc.
void push_back(const value_type x)
{
if (capacity() != 0)
{
if (c.size() == c.capacity())
c.pop_front();
c.push_back(x);
}
}
change_capacity(size_type new_cap)
{
if (new_cap c.capacity())
c.reserve(new_cap);
else if (new_cap c.capacity())
{
c.erase(c.begin(), c.begin() + c.size() - new_cap);
Container tmp(c); // assumes tmp.capacity() == c.size()
c.swap(tmp);
}
}
// etc.
private:
Container c;
};
--
Howard Hinnant
Metrowerks
___
Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
--
Jan Gaspar | [EMAIL PROTECTED]
Whitestein Technologies | www.whitestein.com
Panenska 28 | SK-81103 Bratislava | Slovak Republic
Tel +421(2)5930-0734 | Fax +421(2)5443-5512
___
Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Review Request: cyclic_buffer
For the general container I propose that insert reallocates if size()
would exceed capacity (invalidating all iterators, pointers and
references). And if size() does not exceed capacity, all iterators,
pointers and references are still invalidated, unless the insert
happens at one end or the other, in which case no pointers or
references are invalidated (iterators still are invalidated). I would
expect a quality implementation to minimize the number of elements that
need to be shifted.
insert in general should have the basic exception safety guarantee.
But when inserting only one element at either end, the strong guarantee
is in place. Also if the value_type's copy constructor and assignment
operator do not throw, then the strong guarantee is in place.
For any given adaptor, I think you could restrict or eliminate insert
as appropriate for that model.
-Howard
On Tuesday, June 10, 2003, at 05:20 AM, Jan Gaspar wrote:
Hi Howard!
I like your idea. But (referring to the Nigel Stewart's posting) what
would you
propose for the insert? Should I not provide it?
Jan
Howard Hinnant wrote:
In article [EMAIL PROTECTED], Alisdair Meredith
[EMAIL PROTECTED] wrote:
| The one true circular buffer template is a nigh impossible goal,
| because it means so many things to different people.
snip
| I would certainly like the documentation to explain the tradeoffs
made
| in the implementation, and why this particular variation was chosen
as
| most appropriate for the general case.
Indeed! Excellent post!
Perhaps container adaptors could be applied to a sufficiently
generalized circular buffer.
What is the one true queue? There isn't one. It is best a container
adaptor (policy based if you prefer). I suspect that a more general
circular buffer, restricted by various adaptors, might serve more uses
with less code.
The circular buffer I've needed (and coded) fits none of
aforementioned
descriptions. But it is a circular buffer nonetheless.
For my money, the general circular buffer is one that exists in a
contiguous array, but with an arbitrary begin and end within that
array, capable of wrapping around the end of the physical memory:
+---+---+---+---+---+---+---+---+---+---+
| 4 | 5 | | | | | 0 | 1 | 2 | 3 |
+---+---+---+---+---+---+---+---+---+---+
^ ^
| |
endbegin
Constant time push/pop_front, constant time push/pop_back. When begin
and end collide, reallocation automatically happens vector-like.
This data structure can be efficiently coded with a 4-word data
structure. For example: data_ptr, capacity, size, begin_ptr (there
are other variations that also only take 4 words).
From this you can write adaptors to constrain capacity, have
push_back
overwrite front(), throw an exception on size() exceeding capacity(),
or whatever else you need to do.
You can't adapt any other std::container to do this job because vector
is the only one with capacity, but vector doesn't have a constant time
push/pop_front. But I believe you can adapt the above described
container to meet the needs of other circular buffer requirements.
For example:
template class T, class Container = general_cyclic_bufferT
class my_cyclic_buffer
{
public:
// typedefs ...
my_cyclic_buffer(size_type cap) {c.reserve(cap);}
reference operator[](size_type n) {return c[n];}
// etc.
void push_back(const value_type x)
{
if (capacity() != 0)
{
if (c.size() == c.capacity())
c.pop_front();
c.push_back(x);
}
}
change_capacity(size_type new_cap)
{
if (new_cap c.capacity())
c.reserve(new_cap);
else if (new_cap c.capacity())
{
c.erase(c.begin(), c.begin() + c.size() - new_cap);
Container tmp(c); // assumes tmp.capacity() == c.size()
c.swap(tmp);
}
}
// etc.
private:
Container c;
};
--
Howard Hinnant
Metrowerks
___
Unsubscribe other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost
--
Jan Gaspar | [EMAIL PROTECTED]
Whitestein Technologies | www.whitestein.com
Panenska 28 | SK-81103 Bratislava | Slovak Republic
Tel +421(2)5930-0734 | Fax +421(2)5443-5512
___
Unsubscribe other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost
___
Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: Review Request: cyclic_buffer
Constant time push/pop_front, constant time push/pop_back. When begin and end collide, reallocation automatically happens vector-like. Another point to consider: Constant time push/pop can not be combined with std::vector automatic re-allocation due to the linear cost of copying into the realloc'd buffer. Given that circular buffers are often used in the context of real-time applications, it seems to be consistant that push/pop from each end should be truely constant time, and as a consequence the the capacity is never implicitly changed unless explicitly requested via reserve() or resize(). So as a proposed design criteria: circular_buffer - provides guaranteed O(1) push/pop - provides O(n) arbitrary insertion - provides O(n) manual capacity and size management in contrast to vector - provides (amortized) O(1) push_back/pop_back O(n) in reallocation case - provides O(n) arbitrary insertion - provides O(n) manual capacity and size management (The implication for real-time uses of circular_buffer is that only push and pop are allowed in time-critical code.) This I think is a resounding case against re-allocation, and reflected in the broader understanding of what circular buffers are commonly used for. A re-allocating circular_buffer should therefore only be an adaptor or variant, but can not provide proper O(1) push/pop, so is missing this critical feature of a true circular_buffer. ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Review Request: cyclic_buffer
On Tuesday, June 10, 2003, at 10:48 AM, Jan Gaspar wrote: insert in general should have the basic exception safety guarantee. But when inserting only one element at either end, the strong guarantee is in place. I think the strong guarantee can reached only in case the cyclic_buffer is not full (if there is no reallocation). You can do it with push_back/front too regardless. vector::push_back has the strong guarantee. If you're using copy semantics (which I would expect instead of move semantics), you basically have to build a whole new vector in a temp (with the push_back), and then swap it in when everything is set (just describing the realloc branch here). If you're looking ahead to use move semantics to perform this operation, it is a little more tricky, but not too much. In fact it is easier with cyclic_buffer than it is with vector! :-) You have to push_back the new element into the temporary first. If it throws, the temporary cleans up the new buffer. If it doesn't, *then* move the old data over (move must be nothrow). -Howard ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Review Request: cyclic_buffer
On Tuesday, June 10, 2003, at 11:33 AM, Nigel Stewart wrote: Constant time push/pop_front, constant time push/pop_back. When begin and end collide, reallocation automatically happens vector-like. Another point to consider: Constant time push/pop can not be combined with std::vector automatic re-allocation due to the linear cost of copying into the realloc'd buffer. Given that circular buffers are often used in the context of real-time applications, it seems to be consistant that push/pop from each end should be truely constant time, and as a consequence the the capacity is never implicitly changed unless explicitly requested via reserve() or resize(). Clearly there is a need for what you are describing. And clearly there is a need for what I am describing. And clearly there are a few more closely related needs. My opinion is that it is much easier to adapt a reallocating circular buffer to a non-reallocating one than vice-versa. It is non-trivial to get a reallocating circular buffer correct with respect to exception safety, iterator/pointer invalidation, possible optimizations for types with trivial assign and copy, etc. I would rather get the detailed, complicated work encapsulated in the container, and then have relatively simple adaptors a-la std::stack and std::queue. An adapted construct-time-fixed-capacity circular buffer is no more inefficient or dangerous than a native container version. And the adaptor is simple to write. And because the adaptor is simple to write, there can be a different adaptor for every different need. insert doesn't make sense? Hide it. It will never even be instantiated. Don't want to reallocate? Override push_back to check for size()==capacity() and then perform your favorite action (overwrite front, throw an exception, burn the toast, whatever). Can only afford a reallocation if not at interrupt time? Not a problem. etc. -Howard ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: Review Request: cyclic_buffer
Nigel Stewart wrote: To summarise: Possible resize policies: i. Capacity is fixed at compile time. ii. Capacity is fixed at construction time. iii.Capacity can be manually managed by client code. iv. Capacity is allowed to grow automatically. (ala std::vector) Possible insert handling policies: I. Insert into full buffer results in no change. II. Insert into full buffer results in overwriting opposite end. Insertion into arbitrary position overwrites beginning, if necessary. III.Insert into full buffer results in exception. Possible resize to smaller capacity policies: 1. Keep left-most items. (ala std::vector) 2. Keep right-most items. The general gist of some random googling on circular buffers: - Automatic resizing does not appear to be common. - No established convention in relation to arbitrary insert. - No established convention in relation to resizing to smaller capacity. Another distinction might be 'black box / white box', i.e. whether you have public access to the iterators. If you are merely using a fixed, circular buffer to stop your queue/stack reallocating, you may want to hide them. This is a relatively minor detail. Something I would address in a policy-based implementation, but not in the 'best generalisation for common cases'. -- AlisdairM ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: Review Request: cyclic_buffer
Hi Howard, Constant time push/pop can not be combined with std::vector automatic re-allocation due to the linear cost of copying into the realloc'd buffer. Clearly there is a need for what you are describing. And clearly there is a need for what I am describing. And clearly there are a few more closely related needs. The generally accepted concept of a circular buffer is a fixed size contiguous memory buffer. Following the principle of least surprise a circular_buffer should not decide to resize itself. To overwrite items at the opposite end seems to bother some, (it is a feature, or a bug?) it certainly seems to be the generlly accepted concept of what a circular buffer does. (Unless the insertion fails, or the thread is blocked until space becomes available) Another reason against reallocation is the possibility that two threads could utilise a circular_buffer from each end in a producer/consumer model, without the need for explicit locking. Having one thread decide to move everything elsewhere in memory would appear to exclude this style of use. Another reason against reallocation is that except for resize() and reserve() circular buffer manipulation is _guaranteed_ to succeed, no memory allocations occur which could possibly fail. My opinion is that it is much easier to adapt a reallocating circular buffer to a non-reallocating one than vice-versa. I don't agree, apart from the reasoning above. What is the problem with intercepting push and insert and reserving larger amounts of memory as necessary? I would rather get the detailed, complicated work encapsulated in the container, and then have relatively simple adaptors a-la std::stack and std::queue. We should aim to capture the true concept of a circular buffer, perhaps. (It will be interesting to see where all this leads to, in the end...) Cheers, Nigel Stewart ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: Review Request: cyclic_buffer
Bo Persson wrote: Instead of dropping elements when the buffer is full, we might also consider waiting or throwing a failure. The one true circular buffer template is a nigh impossible goal, because it means so many things to different people. A policy based approach would probably yield all the desirable combinations of behaviour, but policy-based containers seem a hard sell due to complexity of learning the interface. The question of what to do when pushing new values into a full container seems to be the key question though, and most likely to yield to the policy approach. One question that needs answering is what problem is the container solving? Last time I needed a circular buffer, I wanted fixed size (at compile time) storing data samples (PODs or floats) Using a fixed buffer solved any memory fragmentation issues with extended running. In my case I simply wanted to overwrite the oldest data sample as new samples arrived, as I was simply storing 4 minutes of data for viewing. Values wound never be popped, merely overwritten. In this case, boost::arrayN would make a good base container. Many other use-cases suggested over the evolution of this proposal have made good cases for std::vector and std::deque. Sometimes the buffer is always full (eg my example above) in other cases comitted size varies as items are push/popped. Max size may be configured at compile-time, or run-time. I would certainly like the documentation to explain the tradeoffs made in the implementation, and why this particular variation was chosen as most appropriate for the general case. -- AlisdairM ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: Review Request: cyclic_buffer
Alisdair Meredith [EMAIL PROTECTED] skrev i meddelandet news:[EMAIL PROTECTED] Bo Persson wrote: Instead of dropping elements when the buffer is full, we might also consider waiting or throwing a failure. The one true circular buffer template is a nigh impossible goal, because it means so many things to different people. Yes, sure. I just reacted to the suggested names cyclic_buffer and circular_buffer, which means slightly different things to me. In one case we have a cycle, like in your case with a few minutes of samples. The latest n samples are interesting, the older ones can be discarded. Another use for a circular (not cyclic :-) buffer is for the producer-consumer case, where some objects are queued temporarily. Here we can have the buffer wrap around at the ends, so we don't have to move any objects after a pop_front(). We can redefine the front position instead. If you run in a circle, you don't have an end case. Bo Persson [EMAIL PROTECTED] ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: Review Request: cyclic_buffer
Ok, ok, but what with insert? What element should be removed: the first or the last one? And why the first approach or the latter. Indeed, that's an issue. Let's look at the possibilities: (I'm speaking here about left/right or begin/end, rather than order in which items were inserted in FIFO fashion) 1. Shift everything after pos along to the right, overwriting the frontmost items if necessary. 2. Shift everything before pos along to the left, overwriting the backmost items if necessary. 3. Disallow insertions that don't fit in the available capacity, only push_front() and push_back() can utilise the cyclic characteristic of the container. 4. Disallow insert completely. Pros and cons: 1. + Most consistant with std::vector semantics. + Consistency with resize() semantics (rightmost items lost when shrinking) 2. - Counter intuitive(?) 3. - Forces client code to be capacity aware and do extra handling. 4. - Consistency with other containers that support insert() I would lean towards (1), since if (2) is desired then the client code could swap which ends they push and pop from. (3) and (4) don't seem satisfactory from a completeness point of view. This would allow use as a LIFO (last-in, last-out) with fixed sized event horizon. (As an example.) The best example I can suggest an undo buffer, such as in a text editor, which should have a stack-like behaviour but need not store an indefinite history. I agree that a circular_buffer can't be all things to all applications, but a generic general purpose container with a concise and rational behaviour should be possible. We should look at ways that other policy could possibly be layered on top of a generic circular_buffer. (One experiment would be whether std::stack and std::queue would behave sensibly as circular_buffer adaptors.) Let's explore these before deciding that more containers or more elaborate policy aspects are necessary to solve the vast majority of uses. Cheers, Nigel ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: Review Request: cyclic_buffer
In article [EMAIL PROTECTED], Alisdair Meredith
[EMAIL PROTECTED] wrote:
| The one true circular buffer template is a nigh impossible goal,
| because it means so many things to different people.
snip
| I would certainly like the documentation to explain the tradeoffs made
| in the implementation, and why this particular variation was chosen as
| most appropriate for the general case.
Indeed! Excellent post!
Perhaps container adaptors could be applied to a sufficiently
generalized circular buffer.
What is the one true queue? There isn't one. It is best a container
adaptor (policy based if you prefer). I suspect that a more general
circular buffer, restricted by various adaptors, might serve more uses
with less code.
The circular buffer I've needed (and coded) fits none of aforementioned
descriptions. But it is a circular buffer nonetheless.
For my money, the general circular buffer is one that exists in a
contiguous array, but with an arbitrary begin and end within that
array, capable of wrapping around the end of the physical memory:
+---+---+---+---+---+---+---+---+---+---+
| 4 | 5 | | | | | 0 | 1 | 2 | 3 |
+---+---+---+---+---+---+---+---+---+---+
^ ^
| |
endbegin
Constant time push/pop_front, constant time push/pop_back. When begin
and end collide, reallocation automatically happens vector-like.
This data structure can be efficiently coded with a 4-word data
structure. For example: data_ptr, capacity, size, begin_ptr (there
are other variations that also only take 4 words).
From this you can write adaptors to constrain capacity, have push_back
overwrite front(), throw an exception on size() exceeding capacity(),
or whatever else you need to do.
You can't adapt any other std::container to do this job because vector
is the only one with capacity, but vector doesn't have a constant time
push/pop_front. But I believe you can adapt the above described
container to meet the needs of other circular buffer requirements.
For example:
template class T, class Container = general_cyclic_bufferT
class my_cyclic_buffer
{
public:
// typedefs ...
my_cyclic_buffer(size_type cap) {c.reserve(cap);}
reference operator[](size_type n) {return c[n];}
// etc.
void push_back(const value_type x)
{
if (capacity() != 0)
{
if (c.size() == c.capacity())
c.pop_front();
c.push_back(x);
}
}
change_capacity(size_type new_cap)
{
if (new_cap c.capacity())
c.reserve(new_cap);
else if (new_cap c.capacity())
{
c.erase(c.begin(), c.begin() + c.size() - new_cap);
Container tmp(c); // assumes tmp.capacity() == c.size()
c.swap(tmp);
}
}
// etc.
private:
Container c;
};
--
Howard Hinnant
Metrowerks
___
Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: Review Request: cyclic_buffer
Jan, I'm looking forward to the opportunity of having a close look at your cyclic_buffer. But for now, a few perhaps shallow comments... 1. How about push_front()? (in std::list style) And pop_front()? For the sake of generality. The vague concept I have in mind is some kind of sliding window algorithm that could be moving either left or right, using a circular buffer as a cache. (Currently pondering a 2D version of a circular buffer, anyone come across such a beast?) 2. How about reserve(..) and resize(..)? Shouldn't change_capacity be called reserve, like vector? Shouldn't max_size be called capacity, like vector? One context I which I've made happy use of a circular buffer is for storing history in the form of a 3D trail for moving particles. It's handy to allow the GUI to adjust the size of trails dynamically. Semantics of resize should probably follow vector: 1. The capacity is implicitly adjusted to fit the requested size. (Optional to explicitly manage capacity in addition to size) 2. Items are lost from the end if the container is to be shrunk. (Oops, just noticed that resize is in one part of the documentation, but not the non-doxygen page). For your reference, my somewhat more modest circular buffer: http://www.nigels.com/glt/doc/classcbuffer.html I am new to boost, but liking it very, very much... Cheers, Nigel Stewart The cyclic buffer implementation and documentation (cyclic_buffer.zip) can be found at: http://groups.yahoo.com/group/boost/files/ ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Review Request: cyclic_buffer
Hi Nigel! Quoting Nigel Stewart [EMAIL PROTECTED]: Jan, I'm looking forward to the opportunity of having a close look at your cyclic_buffer. But for now, a few perhaps shallow comments... 1.How about push_front()? (in std::list style) And pop_front()? For the sake of generality. Imagine you have a cyclic buffer which is full. When you add (push_back or insert) a new item into this buffer the first (oldest) item will be removed. I want to emphasize the oldest. So if you want to push_front an item you want to add the oldest one. But as soon as you add it the item will be removed because it is the oltest item in the buffer. The buffer's content won't change. (The same is valid for inserting at the beginning of the cyclic buffer.) This is the reason why I didn't encompassed push_front in the implementation. If there is no push_front then it is not logical to have pop_front. You can use erase(begin) instead. The vague concept I have in mind is some kind of sliding window algorithm that could be moving either left or right, using a circular buffer as a cache. (Currently pondering a 2D version of a circular buffer, anyone come across such a beast?) 2.How about reserve(..) and resize(..)? Shouldn't change_capacity be called reserve, like vector? If you look more closely at the documentation you will find out that change_capacity is different from reserve. The capacity can be also decreased; by reserve not. Shouldn't max_size be called capacity, like vector? max_size in the vector is the largest possible size, not the reserved capacity. One context I which I've made happy use of a circular buffer is for storing history in the form of a 3D trail for moving particles. It's handy to allow the GUI to adjust the size of trails dynamically. Semantics of resize should probably follow vector: 1. The capacity is implicitly adjusted to fit the requested size. (Optional to explicitly manage capacity in addition to size) 2. Items are lost from the end if the container is to be shrunk. Are you sure you want to lost the items at the end ? Not at the beginning (the oldest) ? BTW if you change_capacity in order to shrunk the container the oldest items will be removed. (Oops, just noticed that resize is in one part of the documentation, but not the non-doxygen page). Thank you for this! For your reference, my somewhat more modest circular buffer: http://www.nigels.com/glt/doc/classcbuffer.html I am new to boost, but liking it very, very much... Cheers, Nigel Stewart The cyclic buffer implementation and documentation (cyclic_buffer.zip) can be found at: http://groups.yahoo.com/group/boost/files/ ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
[boost] Re: Review Request: cyclic_buffer
Hi Jan, 1. How about push_front()? (in std::list style) And pop_front()? Imagine you have a cyclic buffer which is full. When you add (push_back or insert) a new item into this buffer the first (oldest) item will be removed. Ahh, I see that your conceptualisation is based on age, or order of insertion. Mine was more circular- list oriented: Adding to the front would overwite the backmost item if the buffer is already full. Being a circle, the buffer slides either left or right, as needed. In the case that the buffer is full and items are alternatively added to the front and back, nothing much happens. Admittedly, a special case. Perhaps our concepts are incompatible. Looking at Knuth's coverage of Circular Lists, insertion is allowed at both ends. Knuth also mentions FIFO (first-in first-out) lists as being sometimes called circular stores. There seems to be no particular implication of circular meaning one way or the other, based on Knuth. So the issue here seems to be whether a cyclic_buffer should be circular-list-like or FIFO-like. Given that there is already a queue container adapter, perhaps it's worth listing some applications of cyclic_buffer that depend on either circular-list-like or FIFO-like semantics. Could a queue adaptor using a cyclic_buffer instead of a deque provide the explicitly FIFO-like mode of operation? (While leaving cyclic_buffer to be circular-list-like?) Semantics of resize should probably follow vector: 1. The capacity is implicitly adjusted to fit the requested size. http://www.sgi.com/tech/stl/Vector.html vector::resize Inserts or erases elements at the end such that the size becomes n. (I think a developer may find it surprising for a cyclic_buffer::resize to be clamped to the capacity.) 2. Items are lost from the end if the container is to be shrunk. Are you sure you want to lost the items at the end ? Not at the beginning (the In the FIFO-view, the leftmost/oldest should be removed, agreed. In the circular-list view, it is not so obvious - so follow vector and erase the rightmost... :-) Have a nice weekend, I'm off to the country side... Nigel ___ Unsubscribe other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
