c++ - sistemas - primer ajuste mejor ajuste peor ajuste

¿Cómo puedo almacenar polimórficamente y acceder a diferentes tipos de la misma jerarquía de herencia en la memoria contigua?

Question

Para el polimorfismo, el enfoque habitual es usar std::vector<base*> . Sin embargo, tengo que proporcionar las direcciones yo mismo, es decir, administrar la memoria yo mismo si uso std::unique_ptr<> o punteros sin std::unique_ptr<> .

Me gustaría tener un tipo polymorphic_storage<base> que acepte cualquier tipo que herede de la base . También quiero que los tipos se almacenen en la memoria contigua para un cruce más rápido y para preocupaciones relacionadas con la caché.

Sin embargo, hay un problema bastante grande: en ausencia de información de tipo en el nivel de almacenamiento, se deben solicitar las operaciones de copia / movimiento correctas para cambiar el tamaño.

Solicitud de función:

• Cualquier tipo que herede de la clase base se puede agregar al almacenamiento; sin jerarquías de herencia fija.
• Los tipos heredados deben alinearse correctamente dentro del tipo de almacenamiento.
• Deben llamarse las operaciones correctas de mover y copiar, ya que no estoy tratando con tipos de POD.

¿Qué mecanismo puedo usar para lograr esto?

Mientras proporciono una respuesta, agradecería a cualquiera que publique su solución.

Answer 1

Ahora con soporte de alineación.

Demostración: http://coliru.stacked-crooked.com/a/c304d2b6a475d70c

Esta respuesta se enfoca en resolver las tres características solicitadas en la pregunta.

• No se utiliza memoria estática porque generará cambios en la codificación si se agrega un nuevo tipo a la jerarquía de herencia y ese tipo nuevo excede el límite estático.
• Todos los tipos dentro del almacenamiento están alineados correctamente.
• Se llaman los constructores de movimiento / copia correctos cuando ocurre la reasignación.

Se compila con fstrict-aliasing , así que no tengas miedo de ese reinterpret_cast<>() uso.

El tipo handle_base tiene un miembro de datos void* llamado src_ , que apunta a algún valor. Tiene dos funciones miembro que actúan en src_ .

void transfer( void* dst, std::size_t& out_size )

Utiliza ubicación-nueva para mover o copiar construir el valor apuntado por src_ en dst , luego establece src_ en dst . También agrega el tamaño, en bytes, tomado por el tipo al argumento de referencia out_size ; esto es útil para alinear correctamente tipos.

void* src()

Devuelve el puntero src_ .

handle_base.h

namespace gut
{
    template<class T> class handle;

    class handle_base
    {
    public:
        virtual ~handle_base() = default;

        handle_base() = default;
        handle_base( handle_base&& ) = default;
        handle_base( handle_base const& ) = default;
        handle_base& operator=( handle_base&& ) = default;
        handle_base& operator=( handle_base const& ) = default;

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

        virtual void transfer( void* dst, std::size_t& out_size ) = 0;
        virtual void destroy() = 0;

    protected:
        handle_base( void* src ) noexcept
            : src_{ src }
        {}

        void* src_;
    };
}

A continuación, creo el tipo de handle<T> que hereda de handle_base para proporcionar las operaciones correctas de mover / copiar. La información de tipo está disponible en este nivel; esto permite todo, desde la alineación adecuada hasta las operaciones correctas de movimiento / copia.

void transfer( void* dst, std::size_t& out_size )

La función se ocupará de seleccionar si usar el movimiento o el constructor de copia. El constructor de movimiento siempre se elegirá si está disponible. Calcula cualquier relleno necesario para la alineación, transfiere el valor en src_ a dst + padding e incrementa el argumento de referencia out_size por su tamaño y relleno.

handle.h

namespace gut
{
    template<class T>
    static std::size_t calculate_padding( void* p ) noexcept
    {
        std::size_t r{ reinterpret_cast<std::uintptr_t>( p ) % alignof( T ) };
        return r == 0 ? 0 : alignof( T ) - r;
    }

    template <class T>
    class handle final : public handle_base
    {
    public:
        using byte = unsigned char;

        static_assert( sizeof( void* ) == sizeof( T* ),
            "incompatible pointer sizes" );

        static constexpr std::integral_constant
        <
            bool, std::is_move_constructible<T>::value
        > is_moveable{};

        handle( T* src ) noexcept
            : handle_base( src )
        {}

        handle( handle&& ) = default;
        handle( handle const& ) = default;
        handle& operator=( handle&& ) = default;
        handle& operator=( handle const& ) = default;

        void transfer( std::true_type, void* dst )
        noexcept( std::is_nothrow_move_assignable<T>::value )
        {
            src_ = ::new ( dst ) T{ std::move( *reinterpret_cast<T*>( src_ ) ) };
        }

        void transfer( std::false_type, void* dst )
        noexcept( std::is_nothrow_copy_assignable<T>::value )
        {
            src_ = ::new ( dst ) T{ *reinterpret_cast<T*>( src_ ) };
        }

        virtual void transfer( void* dst, std::size_t& out_size )
        noexcept( noexcept(
            std::declval<handle>().transfer( is_moveable, dst ) ) ) override
        {
            std::size_t padding{ gut::calculate_padding<T>( dst ) };
            transfer( is_moveable, reinterpret_cast<byte*>( dst ) + padding );
            out_size += sizeof( T ) + padding;
        }

        virtual void destroy()
        noexcept( std::is_nothrow_destructible<T>::value )
        {
            reinterpret_cast<T*>( src_ )->~T();
            src_ = nullptr;
        }
    };
}

Como sé con sizeof( handle_base ) == sizeof( handle<T> ) que sizeof( handle_base ) == sizeof( handle<T> ) para cualquier T , creo un tipo de polymorphic_handle como indirección adicional para facilitar su uso. Este tipo puede contener cualquier handle<T> y sobrecarga el operator->() para que pueda actuar como un manejador genérico para cualquier manejador.

polymorphic_handle.h

namespace gut
{
    class polymorphic_handle
    {
    public:
        using value_type = gut::handle_base;
        using pointer = value_type*;
        using const_pointer = value_type const*;

        template<class T>
        polymorphic_handle( gut::handle<T> h ) noexcept
        {
            ::new ( &h_ ) gut::handle<T>{ h };
        }

        pointer operator->()
        {
            return reinterpret_cast<pointer>( &h_ );
        }

        const_pointer operator->() const
        {
            return reinterpret_cast<const_pointer>( &h_ );
        }

    private:
        std::aligned_storage_t<sizeof( value_type ), alignof( value_type )> h_;
    };
}

Ahora que todos los bloques de construcción están presentes, se puede definir el tipo polymorphic_storage<T> . Simplemente almacena un std::vector<gut::polymorphic_handle> , un buffer e información de tamaño.

El tipo de almacenamiento garantiza que solo se puedan agregar las clases que se derivan de su tipo de argumento de plantilla. Solo se puede crear con una instancia inicial o con alguna capacidad inicial (en bytes).

template<class D> void ensure_capacity()

Esta función hace casi todo el trabajo. Asegura que hay suficiente capacidad para el tipo especificado como un argumento de plantilla y transfiere todos los datos a un nuevo búfer en la reasignación. También actualiza la función de miembro size_ a la siguiente ubicación de construcción.

void emplace_back( D&& value )

Esto colocará value en polymorphic_storage<B> y creará un manejador para el valor recién emplazado.

namespace gut
{
    template<class B>
    class polymorphic_storage
    {
    public:
        using byte = unsigned char;
        using size_type = std::size_t;

        ~polymorphic_storage() noexcept
        {
            for ( auto& h : handles_ )
            {
                h->destroy();
            }
            std::free( data_ );
        }

        explicit polymorphic_storage( size_type const initial_capacity )
        {
            byte* new_data
            {
                reinterpret_cast<byte*>( std::malloc( initial_capacity ) )
            };

            if ( new_data )
            {
                data_ = new_data;
                size_ = 0;
                capacity_ = initial_capacity;
            }
            else
            {
                throw std::bad_alloc{};
            }
        }

        template
        <
            class D,
            std::enable_if_t<std::is_base_of<B, std::decay_t<D>>::value, int> = 0
        >
        explicit polymorphic_storage( D&& value )
            : data_{ nullptr }
            , size_{ 0 }
            , capacity_{ 0 }
        {
            using der_t = std::decay_t<D>;

            byte* new_data{ reinterpret_cast<byte*>(
                std::malloc( sizeof( der_t ) + alignof( der_t ) ) ) };

            if ( new_data )
            {
                data_ = new_data;
                size_ = sizeof( der_t );
                capacity_ = sizeof( der_t ) + alignof( der_t );
                handles_.emplace_back( gut::handle<der_t>
                {
                    ::new ( data_ ) der_t{ std::forward<D>( value ) }
                } );
            }
            else
            {
                throw std::bad_alloc{};
            }
        }

        template
        <
            class D,
            std::enable_if_t<std::is_base_of<B, std::decay_t<D>>::value, int> = 0
        >
        void emplace_back( D&& value )
        {
            using der_t = std::decay_t<D>;

            ensure_capacity<der_t>();
            der_t* p{ ::new ( data_ + size_ ) der_t{ std::forward<D>( value ) } };
            size_ += sizeof( der_t );
            handles_.emplace_back( gut::handle<der_t>{ p } );
        }

        template
        <
            class D,
            std::enable_if_t<std::is_base_of<B, std::decay_t<D>>::value, int> = 0
        >
        void ensure_capacity()
        {
            using der_t = std::decay_t<D>;

            auto padding = gut::calculate_padding<der_t>( data_ + size_ );
            if ( capacity_ - size_ < sizeof( der_t ) + padding )
            {
                auto new_capacity =
                    ( sizeof( der_t ) + alignof( der_t ) + capacity_ ) * 2;

                auto new_data = reinterpret_cast<byte*>(
                    std::malloc( new_capacity ) );

                if ( new_data )
                {
                    size_ = 0;
                    capacity_ = new_capacity;
                    for ( auto& h : handles_ )
                    {
                        h->transfer( new_data + size_, size_ );
                    }
                    std::free( data_ );
                    data_ = new_data;
                }
                else
                {
                    throw std::bad_alloc{};
                }
            }
            else
            {
                size_ += padding;
            }
        }

    public:
        std::vector<gut::polymorphic_handle> handles_;
        byte* data_;
        size_type size_;
        size_type capacity_;
    };
}

Aquí hay un ejemplo del almacenamiento en uso. Tenga en cuenta que los tipos der0 , der1 y der2 heredan de la base y tienen diferentes tamaños y alineaciones.

Demostración: http://coliru.stacked-crooked.com/a/c304d2b6a475d70c

#include <iostream>
#include <string>

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

struct der0 : public base
{
    der0( int&& i ) noexcept : i_{ i } {}
    void print() const override { std::cout << "der0_" << i_ << ''/n''; }
    int i_;
};

struct der1 : public base
{
    der1( std::string const& s ) noexcept : s_{ s } {}
    void print() const override { std::cout << "der1_" << s_ << ''/n''; }
    std::string s_;
};

struct der2 : public base
{
    der2( std::string&& s ) noexcept : s_{ std::move( s ) } {}
    void print() const override { std::cout << "der2_" << s_ << ''/n''; }
    std::string s_;
    double d[ 22 ];
};

int main()
{
    gut::polymorphic_storage<base> ps{ 32 };
    ps.emplace_back( der1{ "aa" } );
    ps.emplace_back( der2{ "bb" } );
    ps.emplace_back( der1{ "cc" } );
    ps.emplace_back( der2{ "ee" } );
    ps.emplace_back( der0{ 13 } );
    ps.emplace_back( der2{ "ff" } );

    for ( auto handle : ps.handles_ )
        reinterpret_cast<base*>( handle->src() )->print();
}

Answer 2

Este enfoque intentó evitar la creación de objetos virtuales en un búfer. En cambio, crea tablas virtuales y las amplía.

Lo primero que comenzamos es un value vtable que nos permite manejar virtualmente un valor:

struct value_vtable {
  void(* copy_ctor)(void* dest, void const* src) = nullptr;
  void(* move_ctor)(void* dest, void* src) = nullptr;
  void(* dtor)(void* delete_this) = nullptr;
};

Crear uno de estos para un tipo T ve así:

template<class T>
value_vtable make_value_vtable() {
  return {
    [](void* dest, void const* src) { // copy
      new(dest) T( *(T const*)src );
    },
    [](void* dest, void * src) { // move
      new(dest) T( std::move(*(T*)src) );
    },
    [](void* delete_this) { // dtor
      ((T*)delete_this)->~T();
    },
  };
}

Podemos almacenar estos vtables en línea, o podemos crear un almacenamiento estático para ellos:

template<class T>
value_vtable const* get_value_vtable() {
  static auto const table = make_value_vtable<T>();
  return &table;
}

En este punto, no hemos almacenado nada.

Aquí hay un value_storage. Puede almacenar cualquier valor (se puede copiar, mover y destruir):

template<std::size_t S, std::size_t A>
struct value_storage {
  value_vtable const* vtable;
  std::aligned_storage_t<S, A> data;
  template<class T,
    std::enable_if_t<!std::is_same< std::decay_t<T>, value_storage >{}, int> =0,
    std::enable_if_t< ( sizeof(T)<=S && alignof(T)<=A ), int > = 0
  >
  value_storage( T&& tin ) {
    new ((void*)&data) std::decay_t<T>( std::forward<T>(tin) );
    vtable = get_value_vtable<std::decay_t<T>>();
  }
  // to permit overriding the vtable:
protected:
  template<class T>
  value_storage( value_vtable const* vt, T&& t ):
    value_storage( std::forward<T>(t) )
  {
    vtable = vt;
  }
public:
  void move_from( value_storage&& rhs ) {
    clear();
    if (!rhs.vtable) return;
    rhs.vtable->move_ctor( &data, &rhs.data );
    vtable = rhs.vtable;
  }
  void copy_from( value_storage const& rhs ) {
    clear();
    if (!rhs.vtable) return;
    rhs.vtable->copy_ctor( &data, &rhs.data );
    vtable = rhs.vtable;
  }
  value_storage( value_storage const& rhs ) {
    copy_from(rhs);
  }
  value_storage( value_storage && rhs ) {
    move_from(std::move(rhs));
  }
  value_storage& operator=( value_storage const& rhs ) {
    copy_from(rhs);
    return *this;
  }
  value_storage& operator=( value_storage && rhs ) {
    move_from(std::move(rhs));
    return *this;
  }
  template<class T>
  T* get() { return (T*)&data; }
  template<class T>
  T const* get() const { return (T*)&data; }
  explicit operator bool() const { return vtable; }
  void clear() {
    if (!vtable) return;
    vtable->dtor( &data );
    vtable = nullptr;
  }
  value_storage() = default;
  ~value_storage() { clear(); }
};

Este tipo almacena algo que actúa como un valor, tal vez, hasta el tamaño S y alinea A No almacena qué tipo almacena, ese es el trabajo de otra persona. Almacena cómo copiar, mover y destruir todo lo que almacena, pero no sabe qué es lo que está almacenando.

Asume que los objetos construidos en un bloque se construyen en la parte frontal del mismo. Puede agregar un campo void* ptr si no desea hacer esa suposición.

Ahora podemos aumentar este value_storage con operaciones.

En particular, queremos cast-to-base.

template<class Base>
struct based_value_vtable:value_vtable {
  Base*(* to_base)(void* data) = nullptr;
};

template<class Base, class T>
based_value_vtable<Base> make_based_value_vtable() {
  based_value_vtable<Base> r;
  (value_vtable&)(r) = make_value_vtable<T>();
  r.to_base = [](void* data)->Base* {
    return (T*)data;
  };
  return r;
}

template<class Base, class T>
based_value_vtable<Base> const* get_based_value_vtable() {
  static const auto vtable = make_based_value_vtable<Base, T>();
  return &vtable;
}

Ahora hemos ampliado value_vtable para incluir una familia de "vtable con base".

template<class Base, std::size_t S, std::size_t A>
struct based_value:value_storage<S, A> {
  template<class T,
    std::enable_if_t< !std::is_same< std::decay_t<T>, based_value >{}, int> = 0
  >
  based_value( T&& tin ):
    value_storage<S, A>(
      get_based_value_vtable<Base, std::decay_t<T> >(),
      std::forward<T>(tin)
    )
  {}

  template<class T>
  based_value(
    based_value_vtable<Base> const* vt,
    T&& tin
  ) : value_storage<S, A>( vt, std::forward<T>(tin) )
  {}

  based_value() = default;
  based_value( based_value const& ) = default;
  based_value( based_value && ) = default;
  based_value& operator=( based_value const& ) = default;
  based_value& operator=( based_value && ) = default;
  based_value_vtable<Base> const* get_vt() const {
    return static_cast< based_value_vtable<Base>* >(this->vtable);
  }
  Base* get() {
    if (!*this) return nullptr;
    return get_vt()->to_base( &this->data );
  }
  Base const* get() const {
    if (!*this) return nullptr;
    return get_vt()->to_base( (void*)&this->data );
  }
};

Estos son tipos de valores regulares que se almacenan localmente, son polimórficos y pueden ser cualquier cosa que se baje de Base que coincida con los requisitos de tamaño y alineación.

Simplemente almacena un vector de estos. Y eso resuelve tu problema. Estos objetos satisfacen los axiomas de los tipos de valor que std::vector espera.

ejemplo en vivo Código no muy probado (puede ver la prueba muy pequeña), probablemente todavía contenga algunos errores tipográficos. Pero el diseño es sólido, lo he hecho antes.

Aumentar con el operator* y el operator-> es un ejercicio que le queda al lector. Si desea un rendimiento extremo a costa de algún tamaño, puede almacenar los punteros de la función vtable en línea en la clase en lugar de en la memoria compartida.

Si te das cuenta de que estás haciendo esto más de una vez o based_value nuevas capacidades a tu based_value , una mejor extensión que el truco based_value el valor based_value sería automatizar el procedimiento de extensión vtable. Utilizaría algo así como tipo borrado con std::any , simplemente reemplazando any con value_storage<Size, Align> para almacenamiento automático garantizado, agregando mejor soporte de const e integrando los dos vtables en uno (como en based_value arriba) .

Al final, obtendríamos:

template<class T>
auto to_base = [](auto&& self)->copy_const< decltype(self), T& > {
  return decltype(self)(self);
};

template<class Base, std::size_t S, std::size_t A>
using based_value = super_value_storage< S, A, decltype(to_base<Base>) >;

using my_type = based_value< Some_Base, 100, 32 >;

my_type bob = // some expression
if (bob)
  return (bob->*to_base<Some_Base>)()
else
  return nullptr;

o somesuch.

Todos los moldes de estilo C se pueden reemplazar con una combinación de moldes estáticos y const, pero me volví perezoso. No creo que haga algo que requiera un reinterpreteo.

Pero realmente, una vez que tienes este tipo de polimorfismo mágico basado en el valor, ¿por qué molestarse con una base en absoluto? Simplemente borre todas las operaciones que desee en el valor y acepte cualquier cosa que admita las operaciones borradas.

Con el uso cuidadoso de ADL en su any_method s, ahora puede asignar un concepto de objetos distintos a su conjunto de conceptos que deben ser compatibles. Si sabes cómo criar un vector de perros, puedes almacenar directamente un vector de perros en un super_value_storage< Size, Align, ..., decltype(do_the_chicken) > .

Sin embargo, eso podría estar yendo demasiado lejos.