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.

What is a stack for you? Do you mean the C/C++ call stack or do you have a data stucture or class in mind? — harper, Apr 06 '14 at 11:27
It's impossible to answer, because it very obviously depend on the particular implementation of `std::stack` that you are using. — Matthieu M., Apr 06 '14 at 12:08
Ahk. It was the visual C++ one, but anyway I understand now. Sorry for the stupid question guys! — Amir, Apr 06 '14 at 12:24

score 1 · Answer 1 · edited May 23 '17 at 11:57

1

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

edited May 23 '17 at 11:57

Community

1
1

answered Apr 06 '14 at 11:44

ArtemGr

11,684
3
52
85

The answer is pretty clear, the size is implementation depended. The links are a bonus. And I think that your comment adds nothing to the discussion. – ArtemGr Apr 06 '14 at 12:18

score 1 · Accepted Answer · answered Apr 06 '14 at 12:03

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.

How much memory does a stack take?

2 Answers2