stl deque multiple push_back & remove_front

[toton]

Hi,
I am looking for a circular buffer solution ( a fixed buffer) , where
the elements can be pushed back & removed front. It looks stl deque
can be a solution. my question is,
1) circular buffer is random access? (i.e implemented over array and
not linked list)
2) if I reserve the required space & do push_back & remove_front so
that total memory doesn't exceed the reserved amount, will the internal
pointers will wrap, or the memory will physically move?
3) if it physically move, any stl container for a circular buffer
exists (i need a resize option also) ?
4) if memory don't physically move, i.e can implement a circular
buffer, what is the result of resize with lesser size? will it remove
the oldest push backs, or from the end of memory?

thanks

 

[Michiel.Salters]

Hi,
I am looking for a circular buffer solution ( a fixed buffer) , where
the elements can be pushed back & removed front. It looks stl deque
can be a solution. my question is,
1) circular buffer is random access? (i.e implemented over array and
not linked list)

First: "circular buffer" refers to a particular implementation
technique
of LIFO queues. std::deque uses a different implementation.
std::deque has random access, yes. You don't need it, because you will
be using only push_back and pop_front. It is not implemented over an
array, though. Your assumption that array and list are the only two
choices is wrong.

2) if I reserve the required space & do push_back & remove_front so
that total memory doesn't exceed the reserved amount, will the internal
pointers will wrap, or the memory will physically move?

You can't reserve the space. Memory can't physically move - it's in
your
computer soldered to a circuit board You shouldn't care how deque
manages its memory.

3) if it physically move, any stl container for a circular buffer
exists (i need a resize option also) ?

See previous, it's a don't care.

4) if memory don't physically move, i.e can implement a circular
buffer, what is the result of resize with lesser size? will it remove
the oldest push backs, or from the end of memory?

Depends on how you resize, obviously. The normal resize( ) method
preserves an initial subsequence (remove from end) but you can also
call erase( ) or pop_front( ) to resize the deque. In that case you can
also remove an initial subsequence. std::deque supports fast removal
on both sides, just not in the middle.

HTH,
Michiel Salters

 

[toton]

First: "circular buffer" refers to a particular implementation
technique
of LIFO queues. std::deque uses a different implementation.
std::deque has random access, yes. You don't need it, because you will
be using only push_back and pop_front. It is not implemented over an
array, though. Your assumption that array and list are the only two
choices is wrong.

array stores its elements next in memory fashion (thus random access is
possible) may not be array in C++ sense. linked list stores the pointer
to the next element, and hence random access is not possible (but
insertion & deletion are first) . and there can be mixed
implementation, like several array connected with linked list. I wanted
to know is deque is array implementation or not( now I confirmed, it
is) .
I need random access. However I will do insertion at back & deletion at
front (or otherway). Note, i had never mentioned circular queue, I am
saying about circular buffer.

You can't reserve the space. Memory can't physically move - it's in
your
computer soldered to a circuit board You shouldn't care how deque
manages its memory.

I hope u have understood the meaning. I am not that kind of full to ask
whether the memory will move from chicago to boston! What I wanted to
know, will it do several memory allocation & deallocation when i do
multiple push_back & pop_front, and the number of elements are less
than reserved size,or will wrap the front and back pointer over the
allocated memory.
I need to care how deque chooses memory. One should choose a particular
container based on its implementation. Thats why there are so many
containers ... otherwise one raw array wont be sufficient?

See previous, it's a don't care.


Depends on how you resize, obviously. The normal resize( ) method
preserves an initial subsequence (remove from end) but you can also
call erase( ) or pop_front( ) to resize the deque. In that case you can
also remove an initial subsequence. std::deque supports fast removal
on both sides, just not in the middle.

If a person asks a question, don't make a full of it. I am also a
programmer, and know little programming. Its my request.
thanks

 

[Kai-Uwe Bux]

array stores its elements next in memory fashion (thus random access is
possible) may not be array in C++ sense. linked list stores the pointer
to the next element, and hence random access is not possible (but
insertion & deletion are first) . and there can be mixed
implementation, like several array connected with linked list. I wanted
to know is deque is array implementation or not( now I confirmed, it
is) .
I need random access. However I will do insertion at back & deletion at
front (or otherway). Note, i had never mentioned circular queue, I am
saying about circular buffer.

C++ has no notion of a circular buffer. So if you feel misunderstood, maybe
you should define your terms for us.

I hope u have understood the meaning. I am not that kind of full to ask
whether the memory will move from chicago to boston! What I wanted to
know, will it do several memory allocation & deallocation when i do
multiple push_back & pop_front, and the number of elements are less
than reserved size,or will wrap the front and back pointer over the
allocated memory.
I need to care how deque chooses memory. One should choose a particular
container based on its implementation. Thats why there are so many
containers ... otherwise one raw array wont be sufficient?

Nope: one should choose the containers based upon the (complexity)
guarantees given by the standard. Everything else is up to the vendor of
your library and not topical here. All we can tell you is that deque has
random access iterators and offers (amortized) constant time insertion and
removal at either end. That is what the standard tells you. If you are not
happy with that, you will have to contact the vendor of the implementation
you are using. Keep in mind that details of your platform are off-topic in
this group.


[snip]


Best

Kai-Uwe Bux

 

[P.J. Plauger]

I am looking for a circular buffer solution ( a fixed buffer) , where
the elements can be pushed back & removed front. It looks stl deque
can be a solution. my question is,
1) circular buffer is random access? (i.e implemented over array and
not linked list)

Yes, a circular buffer based on deque is random access. A circular
buffer based on list would be only bidirectional access.

2) if I reserve the required space & do push_back & remove_front so
that total memory doesn't exceed the reserved amount, will the internal
pointers will wrap, or the memory will physically move?

deque doesn't support the member function reserve. (Only string and
vector have a reserve.) But that's not a big deal -- the deque will
grow as needed, and with reasonable time complexity -- until it gets
big enough.

Whether the pointers wrap, however, depends on the implementation.
The original H-P/SGI STL did not, so the container was continually
reworking the entire pointer table as you push and pop elements from
your circular queue. Our (Dinkumware's) implementation wraps just
the way you'd like. IIRC, Howard Hinnant made the Metrowerks deque
behave the same way. But in general, you can't count on this desirable
behavior when using deque as a circular queue.

3) if it physically move, any stl container for a circular buffer
exists (i need a resize option also) ?

IIRC, Metrowerks also provides a nonstandard circular buffer as an
extension. But deque should almost certainly meet your needs quite
well, particularly if it maintains a circular queue of pointers (as
ours does).

4) if memory don't physically move, i.e can implement a circular
buffer, what is the result of resize with lesser size? will it remove
the oldest push backs, or from the end of memory?

resize is not an issue with deque, as I explained above.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

 

[toton]

C++ has no notion of a circular buffer. So if you feel misunderstood, maybe
you should define your terms for us.

circular buffer is a common concept in mathematics of programming, C++
std library hadnt defined it. But I had already mentioned what is
needed for it, in the form of the questions.

Nope: one should choose the containers based upon the (complexity)
guarantees given by the standard. Everything else is up to the vendor of
your library and not topical here. All we can tell you is that deque has
random access iterators and offers (amortized) constant time insertion and
removal at either end. That is what the standard tells you. If you are not
happy with that, you will have to contact the vendor of the implementation
you are using. Keep in mind that details of your platform are off-topic in
this group.

But if an allocator allocated memory once at a time, and other at a
chunk, they are different.
Similarly, if one one wraps the pointer, and other one allocated &
deallocates memory they are different. They are very much different
concept. C++ may not have defined them.
They are not any way related to underlying platform.
P.J. Plauger has clerified the issue, which I had asked.
I hadn't asked any platform detail. Also it is not the question being
happy or unhappy, its whether I can use it for the purpose of circular
buffer or not.
as of it looks, there is no way to allocate memory at prior and use it,
also it doesn't support capacity() or reserve(). Thus it can't be used
for an efficient circular buffer, which is the heart of circular
buffer.
Concept wise a similar class exists in Thinking in C++, called Ring,
but it is implemented over linked list (i.e stl list) .

[snip]


Best

Kai-Uwe Bux

 

[mlimber]

IIRC, Metrowerks also provides a nonstandard circular buffer as an
extension. But deque should almost certainly meet your needs quite
well, particularly if it maintains a circular queue of pointers (as
ours does).

Yes they did. Search for cdeque and Howard Hinnant and you'll find lots
of information about it, but methinks the implementation is only
available to Metrowerks customers. The OP might consider Boost's
circular_buffer which has been accepted but is still in the sandbox.

Cheers! --M

 

[toton]

Yes they did. Search for cdeque and Howard Hinnant and you'll find lots
of information about it, but methinks the implementation is only
available to Metrowerks customers. The OP might consider Boost's
circular_buffer which has been accepted but is still in the sandbox.

Boost 1.33 seems not have it. Also I am not finding it in online boost
documents. Is the class name is circular_buffer ? Can you provide the
link?

thanks.

 

[mlimber]

Boost 1.33 seems not have it. Also I am not finding it in online boost
documents. Is the class name is circular_buffer ? Can you provide the
link?

As I said, it has been accepted, but it is in the Boost sandbox, not in
a released version yet. You can get the code from the CVS repository:

http://boost-sandbox.cvs.sourceforge.net/boost-sandbox/boost-sandbox/boost/

Cheers! --M

 

[toton]

As I said, it has been accepted, but it is in the Boost sandbox, not in
a released version yet. You can get the code from the CVS repository:

http://boost-sandbox.cvs.sourceforge.net/boost-sandbox/boost-sandbox/boost/

Thanks.
boost circular_buffer has a large interdepe ndency for allocators,
iterators and other thing. Not finding a way to use it without
including a lot other templates!
In the meantime found one implementation at
http://www.goodliffe.net/cbuf.html
Looks perfectly ok. uses std library only .
Thanks again...