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 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<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.
• 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 generic through void* function prototypes.
• The transfer() function transfers an instance to a new memory location through a move operation. If the type is not movable, a copy operation is used.

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);

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(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);
}

template<class T>
void transfer(T* dst, T* src)
noexcept(noexcept(transfer(typename std::is_move_constructible<T>::type{}, dst, src)))
{
    transfer(typename std::is_move_constructible<T>::type{}, 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 const vtable{ make_vtable<T>() };
    return &vtable;
}
#endif // VTABLE_H

The handle class manages the unique lifetime of the instance it points to in generic fashion; type information is only available in the template constructor.

• The blk_ data member points to block of memory that stores the instance.
• The src_ data member points to the first byte of the instance. Note that this can differ from blk_ due to padding requirements.
• The copy() member function copies a handle's contained value and type information onto the specified location and returns a new handle to manage that copy.
• Simple utility functions such as hashing (based on the src_ data member), no-throw swapping and equality/inequality are available.

handle.h

#ifndef HANDLE_H
#define HANDLE_H

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

class handle
{
public:
    ~handle() noexcept;

    template<class T>
    handle(void* blk, T* src) noexcept
        : handle(get_vtable_ptr<T>(), blk, src)
    {}

    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:
    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"
#include <cassert>

handle::~handle() noexcept
{
    if (src_)
    {
        destroy();
    }
}

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;
}

handle::handle(vtable_t const* vtable, void* blk, void* src) noexcept
    : vtable_{ vtable }
    , blk_{ blk }
    , src_{ src }
{
    assert(vtable_ != nullptr);
    assert(blk_ != nullptr);
    assert(src_ != nullptr);
}

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 <cstdint>
#include <vector>

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

    ~polymorphic_vector_base() noexcept;

    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 <cstdlib>
#include <cassert>
#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() noexcept
{
    for (auto& h : handles_)
    {
        h.destroy();
    }
    std::free(data_);
}

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);

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

Review goals

The full implementation (with iterators and a std::vector<>-like interface is omitted because of the amount of boilerplate code involved. This question is already long.

A sample toy implementation is provided in the demo below to demonstrate minimal polymorphic_vector_base usage.

I would like a review that focuses on:

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

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

Demo

Note: The polymorphic_vector public interface should be based on std::vector<> as defined in the C++ standard. This implementation is purely for demonstrative purposes.

template<class B>
class polymorphic_vector : private polymorphic_vector_base
{
public:
    auto begin()
    {
        // a proper polymorphic_vector_iterator can be implemented by wrapping
        // around an iterator or an index into handles_
        return handles_.begin();
    }

    auto end()
    {
        return handles_.end();
    }

    template<class T>
    void push_back(T&& value)
    noexcept(std::is_nothrow_move_constructible<std::decay_t<T>>::value)
    {
        using der_t = std::decay_t<T>;
        ::new (allocate<der_t>()) der_t{ std::move(value) };
    }
    
    // the actual erase function would take an iterator
    void erase(std::size_t const i)
    {
        deallocate(i);
    }
};

template<template<class...> class PolyVec, class T>
void print(PolyVec<T>& pv)
{
    // an actual iterator for polymorphic_vector should not expose handles
    for (auto& h : pv)
        reinterpret_cast<T*>(h.src())->print();
}

And here is some sample usage:

#include <iostream>
#include <string>

struct base
{
    virtual ~base() = default;
    virtual void print() const = 0;
};

struct derived_a : public base
{
    derived_a(std::string const& m) : m_{m} {}
    void print() const override { std::cout << m_ << '\n'; }
    std::string m_;
};

struct derived_b : public base
{
    derived_b(std::vector<int> const& m) : m_{ m } {}
    void print() const override { for (auto i : m_) std::cout << i; std::cout << '\n'; }
    std::vector<int> m_;
};

int main()
{
    polymorphic_vector<base> pv;

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

    print(pv);

    pv.erase(0);

    print(pv);
}