473,320 Members | 1,958 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

stl deque multiple push_back & remove_front

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

Aug 10 '06 #1
9 6039
toton wrote:
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

Aug 10 '06 #2

Mi*************@tomtom.com wrote:
toton wrote:
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.
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.
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.
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?
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.
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
HTH,
Michiel Salters
Aug 10 '06 #3
"toton" <ab*******@gmail.comwrote in message
news:11**********************@75g2000cwc.googlegro ups.com...
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
Aug 10 '06 #4
toton wrote:
>
Mi*************@tomtom.com wrote:
>toton wrote:
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.
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.

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.
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
Aug 10 '06 #5

Kai-Uwe Bux wrote:
toton wrote:

Mi*************@tomtom.com wrote:
toton wrote:
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.
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.
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.
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.
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.
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
Aug 10 '06 #6
P.J. Plauger wrote:
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

Aug 10 '06 #7

mlimber wrote:
P.J. Plauger wrote:
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.
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.
Cheers! --M
Aug 10 '06 #8
toton wrote:
mlimber wrote:
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?
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...sandbox/boost/

Cheers! --M

Aug 10 '06 #9

mlimber wrote:
toton wrote:
mlimber wrote:
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?

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...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...
Cheers! --M
Aug 11 '06 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

7
by: Jenny | last post by:
Hi, I have a class foo which will construct some objects in my code. some of the objects store int values into the data deque, while others store float values to the deque. template <class...
0
by: toton | last post by:
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...
8
by: Gernot Frisch | last post by:
std::deque<intd; d.push_front(13); int* p13 = &d.begin(); d.push_front(1); d.push_back(2); Can I be safe, that p13 points to 13? I mean, unless I erase the 13, of course.
1
by: Homeworkboy | last post by:
Can anyone help me with this program? Look at the bottom of this program for help methods: /*1. Make a program that uses numbers from 1 to 100 including each ends which puts the even...
15
by: Juha Nieminen | last post by:
I'm sure this is not a new idea, but I have never heard about it before. I'm wondering if this could work: Assume that you have a common base class and a bunch of classes derived from it, and...
12
by: arnuld | last post by:
It works fine. any advice on making it better or if I can improve my C++ coding skills: /* C++ Primer - 4/e * * Chapter 9 - Sequential Containers * exercise 9.18 - STATEMENT * ...
8
by: t | last post by:
The stack container adaptor uses deque as its default underlying sequential container. I don't understand why since we only add elements and remove elements from one side of a stack. Why isn't...
1
by: Donos | last post by:
Hello I have the following declaration in my code, ****************************************************************** struct mHandleObj { HANDLE h; };
2
by: subramanian100in | last post by:
In ISO/IEC 14882:2003 document, in the section '23.2.1.3 deque modifiers', the following is mentioned: iterator insert(iterator position, const T& x); void insert(iterator position, size_type...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.