Efficient container for different derived classes in C++

Question

When programming games, I used to store all game Objects in a std::vector with initialized and fixed size. Recently I felt the need for some inheritance among the game object classes.

So lets assume I have like 40 classes derived from my class Enemy. If I want to store objects/instances of those classes in a vector, I only have the option of storing them as vector Enemy* right? So the only thing thats contiguously allocated are the pointers, right? So I still will have a lot of cache misses when those need to be dereferenced, right?

Is there any "best practice" way, of storing derived classes in coniguous allocated memory, so that looping through them takes the minimum amount of time?

Answer 1

Boost just accepted a library for exactly this purpose: poly_collection. In particular, you are looking for base_collection

Internally, it uses a number of vectors, one per (derived) type, while providing an interface close to standard containers.

This article by its author provides some design background and a comparison to other solutions, like a vector of unique_ptr. The advantage is two-fold: first, by not using pointers and dynamic memory allocation per element you have better memory locality, and second, grouping elements of the same type together, you help branch prediction and instruction cache for virtual member functions.