By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,413 Members | 1,017 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,413 IT Pros & Developers. It's quick & easy.

How is memory managment in stl stacks / deques implemented?

P: n/a
Hi,

I have a question regarding the memory managment in stl stacks. I want
to use stacks to store a very large amount of numbers (some millions),
thus I'm interested in how the stack behaves when it has to increase
its memory.
>From what I read in the stl-documentation
http://www.sgi.com/tech/stl/stack.html, the stacks default underlying
container is a deque that has amortized constant time insertion and
removal of elements.

I'd like to know, how this is in detail implemented. If anybody knows
also how much memory is averagely wasted.
Thanks and regards,

Daniel Stengler

Jul 10 '06 #1
Share this Question
Share on Google+
2 Replies


P: n/a
"Daniel" <da***@gmx.chwrote in message
news:11**********************@b28g2000cwb.googlegr oups.com...
: I have a question regarding the memory managment in stl stacks. I want
: to use stacks to store a very large amount of numbers (some millions),
: thus I'm interested in how the stack behaves when it has to increase
: its memory.
:
: >From what I read in the stl-documentation
: http://www.sgi.com/tech/stl/stack.html, the stacks default underlying
: container is a deque that has amortized constant time insertion and
: removal of elements.
:
: I'd like to know, how this is in detail implemented. If anybody knows
: also how much memory is averagely wasted.

A classic implementation of std::deque allocates its storage
as fixed-size memory blocks:

dequePtr -- array of pointers -- fixed-size item array
to memory chunks -- fixed-size item array...

This means that no element copies are needed when using
push/pop-_-front/back - but some insertions may incur the
allocation overhead for a new array of items (and, rarely,
overhead for reallocating the array of pointers).

Memory waste is also typically low, with only one pointer
per allocated memory block/item array.

This said, actual performance details will depend on the
specific of the platform you are using. Some library
implementations allow you to specify the size of the
item array -- you might also want to look into this.
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
Brainbench MVP for C++ <http://www.brainbench.com
Jul 10 '06 #2

P: n/a
Ivan Vecerina wrote:
"Daniel" <da***@gmx.chwrote in message
news:11**********************@b28g2000cwb.googlegr oups.com...
: I have a question regarding the memory managment in stl stacks. I want
: to use stacks to store a very large amount of numbers (some millions),
: thus I'm interested in how the stack behaves when it has to increase
: its memory.
:
: >From what I read in the stl-documentation
: http://www.sgi.com/tech/stl/stack.html, the stacks default underlying
: container is a deque that has amortized constant time insertion and
: removal of elements.
:
: I'd like to know, how this is in detail implemented. If anybody knows
: also how much memory is averagely wasted.

A classic implementation of std::deque allocates its storage
as fixed-size memory blocks:

dequePtr -- array of pointers -- fixed-size item array
to memory chunks -- fixed-size item array...

This means that no element copies are needed when using
push/pop-_-front/back - but some insertions may incur the
allocation overhead for a new array of items (and, rarely,
overhead for reallocating the array of pointers).

Memory waste is also typically low, with only one pointer
per allocated memory block/item array.

This said, actual performance details will depend on the
specific of the platform you are using. Some library
implementations allow you to specify the size of the
item array -- you might also want to look into this.
If the OP knows the (max) size of the stack, he could use a std::vector
instead and utilize std::vector<>::reserve() to prevent reallocation
and copying on insertion. Vectors support push_back() and pop_back()
operations and would work as a stack without the std::stack adapter.
(std::stack supports using vector instead of a std::deque, but there is
no interface to access the underlying container through which one could
call std::vector<>::reserve().)

Cheers! --M

Jul 10 '06 #3

This discussion thread is closed

Replies have been disabled for this discussion.