> 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 l
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. Give
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 circ
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
--
Date: Thu, 12 Jun 2003 02:36:10 +1000
From: Nigel Stewart <[EMAIL PROTECTED]>
To: [EMAIL PROTECTED]
Subject: [boost] Re: Review Request: cyclic_buffer
Message-ID: <[EMAIL PROTECTED]>
In-Reply-To: <[EMAIL PROTECTED]>
References: <[EMAIL PROTEC
| -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 circu
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
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
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
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
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 all
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
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
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
Hi Howard!
Howard Hinnant wrote:
> 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
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 o
The circular buffer I've needed (and coded) fits none of aforementioned
descriptions. But it is a circular buffer nonetheless.
I have been scratching around various bookshelves
in search of a definitive coverage of FIFO, LIFO,
circular lists, circular buffers, etc. I certainl
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
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.
| I would certainly like the documentation to explain the tradeoffs made
| in the implementation
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
"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,
> beca
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 a
"Nigel Stewart" <[EMAIL PROTECTED]> skrev i meddelandet
news:[EMAIL PROTECTED]
> >> So the issue here seems to be whether a cyclic_buffer
> >> should be circular-list-like or FIFO-like.
> >
> > I designed the cyclic_buffer mainly for adding the elements at the
end of the
> > container and automa
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.
Jan
Nigel Stewart wrote:
> >> So the issue here seems to be whether a cyclic_buffer
> >> should be circular-list-like or FIFO-like.
> >
> > I designed the cyclic_b
So the issue here seems to be whether a cyclic_buffer
should be circular-list-like or FIFO-like.
I designed the cyclic_buffer mainly for adding the elements at the end of the
container and automatic removal of elements from the beginning - it is just plain
FIFO, nothing else.
(Please excuse
Hi Nigel,
Nigel Stewart wrote:
>
> 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
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
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 t
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 s
29 matches
Mail list logo
