21
\$\begingroup\$

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);
}
Improve this question
\$\endgroup\$

3 Answers 3

Reset to default
4
\$\begingroup\$

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 < handles_.size());

    handles_.erase(handles_.begin() + i);

    auto h = handles_.begin() + i;

    auto noffset = 0;

    if (i != 0)
    {
        auto p = std::prev(h);
        noffset = p->size() + (reinterpret_cast<byte*>(p->src()) - data_);
    }

    consolidate(h, noffset);
}

void polymorphic_vector_base::consolidate(std::vector<handle>::iterator begin, size_type offset)
{
    assert(handles_.cbegin() <= begin);
    assert(handles_.cend() >= begin);
    assert(offset < cap_);

    for (byte* blk{ data_ + offset }, *src; begin != handles_.end(); ++begin)
    {
        src = make_aligned(blk, begin->align());

        if (src + begin->size() > begin->src()) // can't move anything else, we're done!
        {
            return;
        }
        else
        {
            assert(reinterpret_cast<std::uintptr_t>(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.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

It's a neat piece of engineering but it's not that much different from a std::vector of unique_ptrs to the base class. The following accomplishes the same thing with a tad more typing.

std::vector<std::unique_ptr<base>> pv;

pv.push_back(std::make_unique<derived_a>(derived_a{ "abc" }));
pv.push_back(std::make_unique<derived_b>(derived_b{ { 1, 2, 3 } }));

auto print = [&](){    
  for (const auto& el : pv) { el->print();}    
};

print();

pv.erase(pv.begin());

print();

This could be streamlined with a few free functions that hide the make_unique call and help deal with lists. NOTE, I prefer to use the array by reference function signature but I included a delegate using initializer_list for completeness. I added an additional constructor to derived_b to that end to move the contents of the array into the vector.

// tested with -std=c++14, gcc version 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1)

#include <iostream>
#include <string>
#include <vector>
#include <memory>

struct base {
  // forbid instantiation of standalone ABC
protected:
  base() = default;

public:
  virtual ~base() = default;
  virtual void print() const = 0;
};

struct derived_a : public base {
  derived_a(std::string const& m)
    : m_{m} {
    std::cout << "(derived_a-string-ctor)\n";
  }

  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} {
      std::cout << "(derived_b-vector-ctor)\n";
    }

  // accept an array by reference rather than mess with
  // initializer lists and all their associated problems.
  //
  // https://akrzemi1.wordpress.com/2016/07/07/the-cost-of-stdinitializer_list/
  // https://stackoverflow.com/questions/26379311/calling-initializer-list-constructor-via-make-unique-make-shared
  // http://mikelui.io/2019/01/03/seriously-bonkers.html
  // https://tristanbrindle.com/posts/beware-copies-initializer-list
  //
  template <typename std::size_t N>
  derived_b(const int (&m)[N])
    : m_(std::make_move_iterator(std::begin(m)),
         std::make_move_iterator(std::end(m)))
  {
    std::cout << "(derived_b-array-ctor)\n";
    //     m_.resize(N);
    //     std::copy(std::begin(m), std::end(m), std::begin(m_));
  }

  void print() const override {
    for (auto i : m_)
      std::cout << i;
    std::cout << '\n';
  }
  std::vector<int> m_;
};

namespace poly {
typedef std::vector<std::unique_ptr<base>> poly_vector;

// we don't want to type out the long make_unique sig every time
template <typename T, typename... Args>
void emplace_back(poly_vector& pv, Args&&... args) {
  std::cout << "(perfect forwarding delegator)";
  pv.emplace_back(std::make_unique<T>(std::forward<Args>(args)...));
}

// delegate arrays passed by reference
template <typename T, std::size_t N>
void emplace_back(poly_vector& pv, const int (&list)[N]) {
  std::cout << "(reference array delegator)";
  pv.emplace_back(std::make_unique<T>(list));
}

#if 0
// delegate initializer_lists
template <typename T>
void emplace_back(poly_vector& pv, std::initializer_list<int> list) {
  std::cout << "(initializer_list<int> delegator)";
  pv.emplace_back(std::make_unique<T>(list));
}
#endif

// delegate vectors
template <typename T>
void emplace_back(poly_vector& pv, std::vector<int> list) {
  std::cout << "(std::vector<int> delegator)";
  pv.emplace_back(std::make_unique<T>(list));
}

void print(poly_vector& c) {
  for (const auto& el : c) {
    el->print();
  }
}

} // namespace poly

typedef poly::poly_vector poly_vector;

int main() {
  poly_vector pv;

  {
    using namespace poly;
    emplace_back<derived_a>(pv, "abc");

    // ref array
    emplace_back<derived_b>(pv, {1, 2, 3});

    // vector<int> delegate
    emplace_back<derived_b>(pv, {{4, 5, 6}});
    emplace_back<derived_b>(pv, std::vector<int>{{7, 8, 9}});

    std::cout << "\n";
  }

  poly::print(pv);

  pv.erase(pv.begin());

  std::cout << "\nafter...\n\n";

  poly::print(pv);
}

// output
/*
(perfect forwarding delegator)(derived_a-string-ctor)
(reference array delegator)(derived_b-array-ctor)
(std::vector<int> delegator)(derived_b-vector-ctor)
(std::vector<int> delegator)(derived_b-vector-ctor)

abc
123
456
789

after...

123
456
789
*/
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Very nice ideas but there is a major caveat:

You can break this easily if you store pointers or references to objects stored as this vector does not guarantee stable addresses:
On removing elements not at the end you move an object from behind to the now-free spot in memory. This changes the address of that object.

The other points are already mentioned in the response by user673679 but you also asked about Correctness which wasn't addressed.

I'm afraid you can't even fix this or assert in any way as this is due to external usage behaviour. A standard std::vector has the same issue, but there you store value types. Here you store something similar to pointers so using code might want to do something like this:

struct Foo{
  InterfaceBar* bar;
};
polyVector.push_back(ImplBar(42, 1337));
passToCode(Foo{polyVector[0]});

If this is not wanted/required it should work pretty well!

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.