Statically allocating array of inherited objects

Question

The title of this question is pretty convoluted, so I'll try to frame it with an example. Let's say that I have an abstract base class, with a number of classes which inherit from it. In the example below I've only shown two inherited classes, but in reality there could be more.

class Base {
public:
  Base();
  virtual ~Base() = 0;
/// Other methods/members
};

class SmallChild: public Base {
public:
  SmallChild();
  ~SmallChild();
/// Other methods/members such that sizeof(SmallChild) < sizeof(LargeChild)
};

class LargeChild : public Base {
public:
  LargeChild();
  ~LargeChild();
/// Other methods/members such that sizeof(LargeChild) > sizeof(SmallChild)
};

I need to implement a container which stores up to N inherited objects. These objects need to be created/destroyed at runtime and placed in the container, but due to constraints in the project (specifically that it's on embedded hardware), dynamic memory allocation isn't an option. The container needs to have all of its space statically allocated. Also, C++11 is not supported by the compiler.

There was only one way I could think to implement this. To reference the N objects, I'd first need to create an array of pointers to the base class, and then to actually store the objects, I'd need to create a buffer large enough to store N copies of the largest inherited object, which in this case is LargeChild

Base * children[N];
uint8_t childBuffer[N * sizeof(LargeChild)];

I could then distribute the pointers in children across childBuffer, each separated by sizeof(LargeChild). As objects need to be created, C++'s "placement new" could be used to place them at the specified locations in the array. I'd need to keep track of the type of each object in childBuffer in order to dereference the pointers in children, but this shouldn't be too bad.

I have a few questions regarding this entire setup/implementation:

1. Is this a good approach to solving the problem as I've described it? I've never implemented ANYTHING like this before, so I have no idea if I'm way out to lunch here and there's a much easier way to accomplish this.

2. How much of this can be done at compile-time? If I have M types of inherited classes (SmallChild, LargeChild, etc.) but I don't know their size in relation to each other, how can I determine the size of childBuffer? This size depends on the size of the largest class, but is there a way to determine this size at compile-time? I can imagine some preprocessor macros iterating through the classes, evaluating sizeof and finding the maximum, but I have very little experience with this level of preprocessor work and have no idea what this would look like. I can also imagine this being possible using templates, but again, I don't have any experience with compile-time template sorcery so I'm only basing this on my intuition. Any direction on how to implement this would be appreciated.

Answer 1

Do you need to be able to dealocate the objects? If not, it may be easier to override operator new. I refer to this:

void* operator new (std::size_t size) throw (std::bad_alloc);

All your overrides would allocate memory from a sinle large buffer. How much memory to allocate is specified by the size parammeter.

This way you should be able to just say

children[i] = new SmallChild();

Edit: if you do need to deallocate, you need more complex data structures. You may end up re-implementing the heap anyway.

Answer 2

If the set of objects is fully static (set at build time and doesn't change at runtime), the usual approach is to use a set of arrays of each derived class and build up the 'global' array with pointers into the other arrays:

static SmallChild small_children[] = {
    { ...initializer for first small child... },
    { ...initializer for second small child... },
    ...
};
static LargeChild large_children[] = {
    { ...initializer for first large child... },
    ...
};
Base *children[N] = { &small_children[0], &small_children[1], &large_children[0], ....

This can be tricky to maintain if there are children being added/removed from the build frequently, or if the order in the children array is important. It may be desirable to generate the above source file with a script or build program that reads a description of the children needed.

Answer 3

Your approach is interesting, given your constraints (i.e. no use of dynamic allocation).

In fact you are managing on your own way a kind of array of union anyChild { smallChild o1; largeChild o2; ... }; The sizeof(anyChild) would give you the largest block size you are looking for.

By the way, there could be a risk of dangling pointers in you approach, as long as all objects have not been created with the the placement new, or if some of them are deleted through explicit call of their destructor.

Answer 4

if you put your derived types into a union:

    union Child{
        SmallChild asSmallChild;
        LargeChild asLargeChild;
    }

Then the union will automatically be of the sizeof the largest type. Of course, now you have a new problem. What type is represented in the union? You could give yourself a hint in the base Class, or you could instead make Child a struct which contains a hint and then the union inlined within. For examples look at components made by Espressif for ESP32 on the githubs, lots of good union uses there.

Anyways, when you go to allocate, if you allocate an array of the union'ed type it will make an array of largest children... because that's what unions do.