Is it better to use a vector containing pointers, or a vector of values (to avoid heap fragmentation)?

Question

I'm aware of the many articles on avoiding heap fragmentation. My question has to do with specifically what happens when we use a vector to store data:

class foo{
public:
std::vector<bar>; // Or I can have std::vector<bar*>
};

I have no problem using new or delete (I don't have memory leaks, and it is very clear to me when a bar is not used and I can call delete when necessary). But with regarding to heap fragmentation, which is better ? Does this make a stack overflow more likely ?

EDIT: I don't actually have any new information to add. I just wanted to thank everyone, and say that I've found that any question that is tagged with C++ seems to attract so many knowledgeable helpful people. Its really quite nice. Thank you.

Answer 1

The std::vector guarantees, that it's contents will be stored in continuous memory. If you store objects in your vector, then each object will be next to each other in a big chunk of memory, but if you put pointers to the vector, which point to objects created with new, then each object will be in random places in memory.

So the first version (storing objects, not pointers) is better for both avoiding heap fragmentation and utilizing the cache.

Answer 2

TL;DR, unless you have a good reason, with sound measurements, always favour using a vector with value types.

I would argue for the std::vector<bar> form. Unless you have other (measured) reasons why, the guaranteed contiguous memory of vector with a value type is a better idea. When the vector allocates a contiguous block of memory, the objects will be laid out in memory next to each other (with some reserve). This allows the host system and runtime a better chance to avoid fragmentation. Allocating the objects individually may result in fragmentation since you do not control where they are allocated.

I note your concerns around the stack; vector has a small stack allocation so this shouldn't be a problem, the "usual" allocator std::allocator uses new to allocate memory for the vector on the heap.

Why should a vector always be favoured? Herb Sutter goes into some detail about this; http://channel9.msdn.com/Events/Build/2014/2-661 with supporting graphs, diagrams, explanations etc. from around the 23:30 mark and he picks up Bjarne's material at around the 46:00 mark.

Answer 3

OP seems to have a basic misunderstanding about what std::vector does: It allocates a contiguous block of memory on the heap, you do not need to worry about your stack-space when using vector! So whenever you do not really need to store anything but the objects them self, just put them in your vector and you are good.

So std::vector<bar> appears to be the right choice in your case. Also, don't worry about heap fragmentation prematurely, let the compiler worry about that. (But you should worry about feeding pre-fetcher, that is why std::vector<bar> should be your standard choice to store anything.)

Answer 4

Use a vector of pointers in the following cases:

• Bar is a base class and you want to store instances of derived classes in the vector.
• Bar doesn't have an appropriate copy/move constructor or it is prohibitively expensive.
• You want to store pointers to objects in the vector elsewhere, and you may change the capacity of the vector (for example, due to resize or push_back). If the objects are stored by value, old pointers will become invalid when the capacity changes.
• You want some elements in the vector to be "empty", (which can be represented by null pointers), and it's not practical to store dummy, unused instances of Bar in the vector by value instead.

If you do need pointers, I strongly suggest using smart pointers.

In other cases, you should prefer to store objects by value, as it is usually more efficient.