A vector-like polymorphic container to store objects from a type hierarchy in contiguous memory

Normally, in order to have a polymorphic collection, we store pointers to a base class:

std::vector v;          // or std::vector>
v.push_back(new derived{});    // problem: value is stored in a galaxy far far away

There are a couple of issues with this approach:

• The std::vector instance does not manage the lifetime of the polymorphic types. They must be allocated elsewhere.

• The instances are not allocated contiguously; there are no standard library facilities that provide contiguous storage for any type in an inheritance hierarchy.

• Since objects can be stored in arbitrary memory locations, there is a cache miss performance hit associated to containers of pointers (such as linked lists).

Ideally, one would be able to simply declare the following:

polymorphic_vector v;
v.push_back(derived_a{}); // some type that derives from base; ensured through templates
v.push_back(derived_b{}); // another type that derives from base; different size, alignment

In order to do something like:

for (auto& b : v)
{
    b.polymorphic_function(); // some polymorphic function
}

The container should ensure the following:

• Able to store any type that derives from the specified base class, including any type that can be added to the type hierarchy in the future.

• Values that are added to the container are stored in contiguous memory and respect alignment.

• The container is said to own the objects that it contains, unlike a vector of pointers.

What follows is my implementation of polymorphic_vector_base: a class that handles all memory management (alignment, storing types in contiguous memory, resizing, etc.).

Implementation

The vtable_t structure contains type information necessary for operations and data in order to store multiple types in generic fashion.

• Alignment and size data members are required to prevent memory overwrites and to maintain alignment.

• Function pointers to the proper destructor/move/copy operations are kept gen

This is some really nifty code. I'd be curious to see the full implementation and whether there were any improvements since this question was posted. :)

[code] make_aligned

Is there a reason for this to be a macro instead of an inline function?

[code] malloc

std::malloc() is allowed to return nullptr if given a size of zero (e.g. the default capacity). On such implementations the polymorphic_vector_base constructor will always throw a bad_alloc when called with a capacity of zero.

[design] sections_

At the moment, the sections_ / erase algorithm doesn't seem quite correct or useful.

As I understand it: erasing an object results in an unused gap in the container memory. In a normal vector, we'd copy / move the following objects backwards to fill the gap. But since we're storing objects of different types, the next object may be larger than the object removed. If so, we can't move it into the gap because we'd be overwriting part of the memory it already occupies.

Thus a section describing the gap is added. So if another object is erased at that point, we can reuse the memory.

However...

In polymorphic_vector_base::destroy(), all the sections from the one belonging to the current handle to the end of the vector are erased. But, in polymorphic_vector_base::transfer() only the first section encountered is re-added. So in this code:

pv.push_back(derived_b{ { 1, 2, 3 } }); // size 20
pv.push_back(derived_a{ "abc" }); // size 32
pv.push_back(derived_b{ { 1, 2, 3 } }); // size 20
pv.push_back(derived_a{ "abc" }); // size 32

pv.erase(2); // adds a section (can't move size 32 into a size 20 slot)
pv.erase(0); // removes the first section, adds another section (but the removed one isn't re-added, even though it's still relevant)

Neither of the erase function calls are able to move items backwards to fill the gaps. But after the second erase, we've discarded the section data we added when doing the first erase, even though the gap still exists.

While the above issue could be fixed, and the section data perhaps used to provide an "insert wherever" function that found the first (or smallest) possible insertion point, it's not needed for erasing.

We can calculate the new offset directly from the previous handle (if there's no previous handle, then the offset is zero). So the code to remove an element and consolidate the vector can be simplified:

void polymorphic_vector_base::deallocate(size_type const i)
{
    assert(i size() + (reinterpret_cast(p->src()) - data_);
    }

    consolidate(h, noffset);
}

void polymorphic_vector_base::consolidate(std::vector::iterator begin, size_type offset)
{
    assert(handles_.cbegin() = begin);
    assert(offset align());

        if (src + begin->size() > begin->src()) // can't move anything else, we're done!
        {
            return;
        }
        else
        {
            assert(reinterpret_cast(src) % begin->align() == 0);

            begin->transfer(blk, src);
            blk = data_ + (offset += begin->size() + (src - blk));
        }
    }

    offset_ = offset;
}

Note that there's no need to explicitly call destroy() on the erased handle, as it's called in the handle destructor.

StackExchange Code Review Q#144179, answer score: 4