How much memory does a stack take?

Question

I'm writing a sort algorithm where I can only use stacks. By increasing the amount of stacks, I can do the sort with less operations.

Anyway, say I have a dataset of 10 integers. What would be the difference in memory for the following (with std::stack):

• an array of stacks of size 2 (5 integers per stack)
• an array of size 10 (1 integer per stack)
• an array of size 20 (1 integer each in 10 stacks, 10 stacks are empty)

Also, how much memory does an empty stack of int take? Would it just be an extra int pointer?

Please treat this question as an academic one. I know there are better ways of solving this problem, but I can only use stacks.

Answer 1

The most obvious answer is: it all depends. In reality, there are some things that can be said.

All of the containers incur a modest amount of overhead, of the order of (perhaps) a couple of pointers and a couple of integers, at most. You can find out how much if you really want to know, but it will be constant and quite small, depending on the implementation.

Where the C++ standard helps you is that it places requirements on the storage part of the container. Because iterators are (more or less) equivalent to pointers, stack elements are placed at consecutive memory locations with the same alignment as an array of the same items. You can predict this part.

And where it lets you down again is that there is no limit on the amount of 'slack' space. The container might contain 5 elements and have enough space for 500. This will again depend on the implementation.

So it all depends. You'll just have to try it and see.

Answer 2

The size of std::stack depends on the particular implementation of std::stack and the underlying container (which by default is std::deque).

(See also: std::deque memory use; What the heque is going on with the memory overhead of std::deque?; https://stackoverflow.com/a/5559774/257568; etc).