Should a list of objects be stored on the heap or stack?

Question

I have an object(A) which has a list composed of objects (B). The objects in the list(B) are pointers, but should the list itself be a pointer? I'm migrating from Java to C++ and still haven't gotten fully accustomed to the stack/heap. The list will not be passed outside of class A, only the elements in the list. Is it good practice to allocate the list itself on the heap just in case?

Also, should the class that contains the list(A) also be on the heap itself? Like the list, it will not be passed around.

Answer 1

The stack is always simplest. Unfortunately it has one big drawback - you have to know the number of elements ahead of time.

Answer 2

You're better off storing a list, if it can grow, on the heap. Since you never know what the runtime stack will be, overflow is a real danger, and the consequences are fatal.

If you absolutely know the upper bound of the list, and it's small compared to the size of your stack, you can probably get away with stack allocating the list.

Answer 3

I work in environments where the stack can be small and heap fragmentation needs to be avoided, so I'd use these rules:

• If the list is small and a known fixed size, stack.

• If the list is small and an unknown fixed size, you can consider both the heap and alloca(). Using the heap would be a fine choice if you can guarantee that your function doesn't allocate anything on the heap during the duration your allocation is going to be on there. If you can't guarantee this, you're asking for a fragment and alloca() would be a better choice.

• If the list is large or will need to grow, use the heap. If you can't guarantee it won't fragment, we tend to have some recourses for this built into our memory manager such as top-down allocations and separate heaps.

Most situations don't call for people to worry about fragmentation, in which case they'd probably not recommend the usage of alloca.

With respect to the class containing the list, if it's local to the function scope I would put it on the stack provided that the internal data structures are not extremely large.

Answer 4

Bear in mind that

1. The list would only be on the stack if Object-A was also on the stack
2. Even if the list itself is not on the heap, it may allocate its storage from the heap. This is how std::list, std::vector and most C++ lists work – the reason is that stack-based elements cannot grow.
3. These days most stacks are around 1mb, so you'd need a pretty big list of pretty big objects before you need to worry about it. Even if your stack was only about 32kb you could store close to eight thousand pointers before it would be an issue.

IMO people new to the explicit memory management in C/C++ can have a tendency to overthink these things.

Unless you're writing something that you know will have thousands of sizable objects just put the list on the stack. Unless you're using giant C-style arrays in a function the chances are the memory used by the list will end up in the heap anyway due to #1 and #2 above.

Answer 5

What do you mean by "list". If it's std::list (or std::vector or any other STL container) then it's not going to be storing anything on the stack so don't worry.

If you're in any doubt, look at sizeof(A) and that tells you how much memory it will use when it's on the stack.

But ... the decision should mainly be based on the lifetime of the object. Stack-based objects are destroyed as soon as they go out of scope.