How is memory managment in stl stacks / deques implemented?

[Daniel]

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

 

[Ivan Vecerina]

: 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.

 

[mlimber]

: 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