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?

Chadwick

I think he's talking about class instances. That seemed clear to me. – Menis

I meant objects of those classes. Instances. The things which are created during runtime and are allocated. – Chadwick

use pointer to base class inside the vector, or if its fit better, some kind of smart pointers. – Fivespot

I think storing them in a vector<enemy*> would be exactly what you're looking for. Vectors seem to be c++'s best practice tool for iteration and storage. And since they are pointers, it's the same as a vector<long> so that's good too. – Mosul

pointer to base class is exactly the example I gave above, but asked, if I can avoid using pointers, because I want to loop through the objects as fast as possible, and would like to have something close to the efficiency of a contiguously allocated vector. – Chadwick

Pointers are probably the fastest way to do it anyways. It takes 1 assembly instruction to load a value from a pointer – Mosul

If you want to call virtual methods of derived objects you have to use pointers anyway... and iterating over different sized objects instead over pointers to objects is slower, because you need a list for this. Allocating the objects in a linear space can be done simply by "new at" operator. – Fivespot

I personally would go with std::vector<std::unique_ptr<Enemy>> by default - so you don't have to worry about the memory management yourself. – Mindymine

There are several approaches but they are all technically quite complex. I strongly recommend that you start with vector<unique_ptr<Enemy>> and benchmark. If you do need to go this route, this simplest/most feasible approach with such a large number of derived classes, is to use a custom allocator to ensure that all of the Enemies get constructed in a contiguous block of memory. You would still use a vector of unique_ptr's just with a custom deleter, and use some other function instead of make_unique. – Mechanist

Possible duplicate of In which scenario do I use a particular STL container? – Locoism

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.

Wizardry

It's not clear at all that anything is more optimal if you group elements of the same type. In many scenarios, there is a strong relationship between objects allocated close together in time. In others, it's important only to have all objects of derived types stored together, with no need for grouping. Then objects may live forever, and all be deallocated together - then, an arena would perform better. As with most things, you have to profile when performance matters, and poly_collection may perform the best of the alternatives, or not quite. – Aprilaprile

Answer 2

What about this?

struct alignas(...) Base {};
struct Derived1 : Base {};
struct Derived2 : Base {};

int main()
{
    std::vector<Base> v(2);
    new (&v[0]) Derived1();
    new (&v[1]) Derived2();
    return 0;
}

Placement new does the trick. It works with polymorphism. The alignas is to ensure the vector contains objects of the same size. Replace the ... by a number (power of 2) such that instances of both Derived1 and Derived2 fit in the vector. If sizeof(Derived1) returns 16 and sizeof(Derived2) returns 24, you would need a alignas(32).

EDIT

As @KubaOber stated, alignas is not designed to manage allocation sizes, but only for positioning the object in memory. A better way to achieve your goal is using std::variant. Something like this:

int main()
{
    std::vector<std::variant<Derived1, Derived2>> v;
    v.emplace_back(Derived1());
    v.emplace_back(Derived2());

    for (const auto& e : v)
        std::visit(VisitPackage(), e);

    return 0;
}

where VisitPackage could be something like this:

struct VisitPackage
{
    void operator()(const Derived1&) { std::cout << "Derived 1.\n"; }
    void operator()(const Derived2&) { std::cout << "Derived 2.\n"; }
};

Durr

The only thing this achieves is that you have to manually manage the sizes and alignment, and you may be over-aligning as well, since alignas was never meant to manage allocation sizes, only positioning of the object in memory. – Aprilaprile

Basically, what you did is a hacked together std::vector<std::variant<Base, Derived1, Derived2>> :) – Aprilaprile

True lol. But the std::visit needs to cover all the cases. Anyways, I agree with your comment on alignas. – Durr