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

std::vector<base*> v;          // or std::vector<std::unique_ptr<base>>
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<T> 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 inhertiance hierarchy.

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

polymorphic_vector<base> 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.

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

The vtable_t structure contains type information necessary for operations and data in order to store multiple types in generic fashion while having to call the correct destroy/move/copy operations of the types.

• It is a simple POD structure containing size and alignment data and function pointers to destroy/move/copy operations and more.

vtable.h

#ifndef VTABLE_H
#define VTABLE_H

#include <cstddef>
#include <new>
#include <utility>
#include <type_traits>

// type aliases for function prototypes
using dtor_t = void(*)(void const* src);
using move_ctor_t = void(*)(void* dst, void* src);
using copy_ctor_t = void(*)(void* dst, void const* src);
using transfer_t = void(*)(void* dst, void* src);

// structure to contain a type's function pointers and other data
struct vtable_t
{
    std::size_t const align;
    std::size_t const size;

    dtor_t dtor;
    move_ctor_t move_ctor;
    copy_ctor_t copy_ctor;
    transfer_t transfer;
};

// template functions to call relevant operations through function pointers
template<class T>
void destroy(T const* src)
noexcept(std::is_nothrow_destructible<T>::value)
{
    src->~T();
}

template<class T>
void move_construct(T* dst, T* src)
noexcept(std::is_nothrow_move_constructible<T>::value)
{
    ::new (dst) T{ std::move(*src) };
}

template<class T>
void copy_construct(T* dst, T const* src)
noexcept(std::is_nothrow_copy_constructible<T>::value)
{
    ::new (dst) T{ *src };
}

template<class T>
void transfer(T* dst, T* src)
noexcept(noexcept(transfer(std::integral_constant<bool,
    std::is_move_constructible<T>::value>{}, dst, src)))
{
    static constexpr auto is_moveable = std::integral_constant<
        bool, std::is_move_constructible<T>::value>{};

    transfer(is_moveable, dst, src);
}

template<class T>
void transfer(std::true_type, T* dst, T* src)
noexcept(noexcept(move_construct(dst, src)))
{
    move_construct(dst, src);
}

template<class T>
void transfer(std::false_type, T* dst, T* src)
noexcept(noexcept(copy_construct(dst, src)))
{
    copy_construct(dst, src);
}

// constructs a vtable_t instance for the specified template type argument
template<class T>
vtable_t make_vtable() noexcept
{
    return
    {
        alignof(T), sizeof(T),
        reinterpret_cast<dtor_t>(&destroy<T>),
        reinterpret_cast<move_ctor_t>(&move_construct<T>),
        reinterpret_cast<copy_ctor_t>(&copy_construct<T>),
        reinterpret_cast<transfer_t>(static_cast<void(*)(T*, T*)>(transfer<T>))
    };
}

// statically store a vtable_t and get a pointer to the instance.
template<class T>
auto get_vtable_ptr() noexcept
{
    static vtable_t vtable = make_vtable<T>();
    return &vtable;
}
#endif // VTABLE_H

The handle class stores a pointer to some type and a pointer to that type's vtable in a type erased manner.

• It is hashable: hashing is done on the address the handle points to.

• It is a move-only type: a handle owns whatever it points to) that provides utility functions such as swapping and comparison operations.

handle.h

#ifndef HANDLE_H
#define HANDLE_H

#include "vtable.h"
#include <cstddef>
#include <cassert>

class handle
{
public:
    ~handle() noexcept;

    template<class T>
    handle(void* blk, T* src) noexcept
        : vtable_{ get_vtable_ptr<T>() }
        , blk_{ blk }
        , src_{ src }
    {
        assert(vtable_ != nullptr);
        assert(blk_ != nullptr);
        assert(src_ != nullptr);
    }

    handle(handle&& other) noexcept;
    handle& operator=(handle&& other) noexcept;

    handle(handle const&) = delete;
    handle& operator=(handle const&) = delete;
    
    void destroy() noexcept;
    void transfer(void* blk, void* dst);
    handle copy(void* blk, void* dst) const;

    void swap(handle& other) noexcept;
    
    std::size_t align() const noexcept;
    std::size_t size() const noexcept;

    void* blk() const noexcept;
    void* src() const noexcept;

private:
    constexpr handle(vtable_t const* vtable, void* blk, void* src) noexcept;
    
    vtable_t const* vtable_;
    void* blk_;
    void* src_;
};

void swap(handle& a, handle& b) noexcept;
bool operator==(handle const& lhs, handle const& rhs) noexcept;
bool operator!=(handle const& lhs, handle const& rhs) noexcept;

namespace std
{
    template<>
    struct hash<handle>
    {
        size_t operator()(handle const& h) const
        {
            return hash<void*>{}(h.src());
        }
    };
}
#endif // HANDLE_H

handle.cpp

#include "handle.h"

handle::~handle() noexcept
{
    if (src_)
    {
        vtable_->dtor(src_);
    }
}

handle::handle(handle&& other) noexcept
    : vtable_{ other.vtable_ }
    , blk_{ other.blk_ }
    , src_{ other.src_ }
{
    other.src_ = nullptr;
}

handle& handle::operator=(handle&& other) noexcept
{
    vtable_ = other.vtable_;
    blk_ = other.blk_;
    src_ = other.src_;
    other.src_ = nullptr;
    return *this;
}

constexpr handle::handle(vtable_t const* vtable, void* blk, void* src) noexcept
    : vtable_{ vtable }
    , blk_{ blk }
    , src_{ src }
{}

void handle::destroy() noexcept
{
    vtable_->dtor(src_);
    src_ = nullptr;
}

void handle::transfer(void* blk, void* dst)
{
    vtable_->transfer(dst, src_);
    blk_ = blk;
    src_ = dst;
}

handle handle::copy(void* blk, void* dst) const
{
    vtable_->copy_ctor(dst, src_);
    return { vtable_, blk, dst };
}

void handle::swap(handle& other) noexcept
{
    std::swap(vtable_, other.vtable_);
    std::swap(blk_, other.blk_);
    std::swap(src_, other.src_);
}

std::size_t handle::align() const noexcept
{
    return vtable_->align;
}

std::size_t handle::size() const noexcept
{
    return vtable_->size;
}

void* handle::blk() const noexcept
{
    return blk_;
}

void* handle::src() const noexcept
{
    return src_;
}

void swap(handle& a, handle& b) noexcept
{
    a.swap(b);
}

bool operator==(handle const& lhs, handle const& rhs) noexcept
{
    return lhs.src() == rhs.src();
}

bool operator!=(handle const& lhs, handle const& rhs) noexcept
{
    return lhs.src() != rhs.src();
}

The polymorphic_vector_base class does all memory management and ensures proper alignment.

• It stores handles to every contained object.
• The allocation algorithm simply stores the new object contiguously while maintaining alignment. If a reallocation is required, fragmentation is completely removed.
• The deallocation algorithm attempts to prevent fragmentation or reallocation calls by keeping types as close together as possible.

polymorphic_vector_base.h

#ifndef POLYMORPHIC_VECTOR_BASE_H
#define POLYMORPHIC_VECTOR_BASE_H

#include "handle.h"
#include <cstddef>
#include <vector>

class polymorphic_vector_base
{
public:
    using byte = unsigned char;
    using size_type = std::size_t;

    explicit polymorphic_vector_base(size_type const cap = 0);

    template<class T>
    T* allocate();

    void deallocate(size_type const i);

private:
    struct section
    {
        constexpr section(void* const hnd_src, size_type const avail_sz) noexcept;

        void* handle_src;
        size_type available_size;
    };

    size_type destroy(size_type const i, size_type const j);
    
    bool transfer(std::vector<handle>::iterator begin,
        std::vector<handle>::const_iterator end, size_type& offset);

    std::vector<handle> handles_;
    std::vector<section> sections_;
    byte* data_;
    size_type offset_;
    size_type cap_;
};

#define make_aligned(block, align)\
(polymorphic_vector_base::byte*)(((std::uintptr_t)block + align - 1) & ~(align - 1))

template<class T>
inline T* polymorphic_vector_base::allocate()
{
    byte* blk{ data_ + offset_ };
    byte* src{ make_aligned(blk, alignof(T)) };
    size_type required_size{ sizeof(T) + (src - blk) };

    if (cap_ - offset_ < required_size)
    {
        size_type ncap{ (cap_ + required_size) * 2 };
        byte* ndata{ reinterpret_cast<byte*>(std::malloc(ncap)) };

        if (ndata)
        {
            sections_.clear();
            offset_ = 0;
            cap_ = ncap;

            for (auto& h : handles_)
            {
                blk = ndata + offset_;
                src = make_aligned(blk, h.align());

                h.transfer(blk, src);
                offset_ += h.size() + (src - blk);
            }

            blk = ndata + offset_;
            src = make_aligned(blk, alignof(T));

            std::free(data_);
            data_ = ndata;
        }
        else
        {
            throw std::bad_alloc{};
        }
    }

    handles_.emplace_back(blk, reinterpret_cast<T*>(src));
    offset_ += sizeof(T) + (src - blk);

    return reinterpret_cast<T*>(src);
}
#endif // POLYMORPHIC_VECTOR_BASE_H

polymorphic_vector_base.cpp

#include "polymorphic_vector_base.h"
#include <algorithm>

constexpr polymorphic_vector_base::section::section(void* const hnd_src,
    size_type const avail_sz) noexcept
    : handle_src{ hnd_src }
    , available_size{ avail_sz }
{}

polymorphic_vector_base::polymorphic_vector_base(size_type const cap)
    : data_{ reinterpret_cast<byte*>(std::malloc(cap)) }
    , offset_{ 0 }
    , cap_{ 0 }
{
    if (data_)
    {
        cap_ = cap;
    }
    else
    {
        throw std::bad_alloc{};
    }
}

void polymorphic_vector_base::deallocate(size_type const i)
{
    assert(i < handles_.size());

    auto noffset = destroy(i, i + 1);
    auto h = handles_.begin() + i;

    if (transfer(h + 1, handles_.end(), noffset))
    {
        offset_ = noffset;
    }

    handles_.erase(h);
}

polymorphic_vector_base::size_type polymorphic_vector_base::destroy(size_type i,
    size_type const j)
{
    assert(j <= handles_.size());
    assert(i < j);

    auto& h = handles_[i];
    auto offset = reinterpret_cast<byte*>(h.blk()) - data_;

    auto e = sections_.end();
    sections_.erase(std::remove_if(sections_.begin(), e,
        [&h](auto&& s) { return s.handle_src > h.src(); }), e);

    for (auto b = sections_.begin(), e = sections_.end(); b != e; ++b)
    {
        if (b->handle_src == h.src())
        {
            offset -= b->available_size;
            std::swap(*b, sections_.back());
            sections_.pop_back();
            break;
        }
    }

    h.destroy();

    for (++i; i != j; ++i)
    {
        handles_[i].destroy();
    }

    return offset;
}

bool polymorphic_vector_base::transfer(std::vector<handle>::iterator begin,
    std::vector<handle>::const_iterator end, size_type& offset)
{
    assert(handles_.cbegin() <= begin);
    assert(handles_.cbegin() <= end);
    assert(handles_.cend() >= begin);
    assert(handles_.cend() >= end);
    assert(offset < cap_);

    for (byte* blk{ data_ + offset }, *src; begin != end; ++begin)
    {
        src = make_aligned(blk, begin->align());
        if (src + begin->size() > begin->src())
        {
            sections_.emplace_back(begin->src(),
                reinterpret_cast<byte*>(begin->src()) - (data_ + offset));
            return false;
        }
        else
        {
            assert(reinterpret_cast<std::uintptr_t>(src) % begin->align() == 0);
            assert(src + begin->size() <= begin->src());

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

As the name implied, this was not the full polymorphic_vector implementation, which can be implemented as a simple wrapper or derived class of polymorphic_vector_base. There is a lot of boilerplate involved, so I've omitted from this already very long question.

I would like a review that focuses on:

• Correctness; there are some tricky memory management spots.
• Performance and efficiency of algorithms.

This implementation is missing a range based erase operation. However, the building blocks to build such a function are already present.