Técnicas de borrado de tipo

136

(Con el borrado de tipo, me refiero a ocultar parte o la totalidad de la información de tipo con respecto a una clase, algo así como Boost.Any .)
Quiero obtener una serie de técnicas de borrado de tipo, al mismo tiempo que comparto las que conozco. Espero encontrar alguna técnica loca que alguien haya pensado en su hora más oscura. :)

El primer y más obvio, y enfoque comúnmente adoptado, que sé, son las funciones virtuales. Simplemente oculte la implementación de su clase dentro de una jerarquía de clases basada en la interfaz. Muchas bibliotecas de Boost hacen esto, por ejemplo Boost.Any hace esto para ocultar su tipo y Boost.Shared_ptr hace esto para ocultar la (des) asignación mecánica.

Luego está la opción con punteros de función para funciones con plantilla, mientras se mantiene el objeto real en un void*puntero, como Boost.Function lo hace para ocultar el tipo real del functor. Se pueden encontrar implementaciones de ejemplo al final de la pregunta.

Entonces, para mi pregunta real:
¿Qué otro tipo de técnicas de borrado conoce? Proporcione, si es posible, un código de ejemplo, casos de uso, su experiencia con ellos y quizás enlaces para lecturas adicionales.

Editar
(Dado que no estaba seguro de si agregar esto como respuesta, o simplemente editar la pregunta, haré la más segura).
Otra buena técnica para ocultar el tipo real de algo sin funciones virtuales o void*tocar el violín es un GMan emplea aquí , con relación a mi pregunta sobre cómo funciona exactamente esto.


Código de ejemplo:

#include <iostream>
#include <string>

// NOTE: The class name indicates the underlying type erasure technique

// this behaves like the Boost.Any type w.r.t. implementation details
class Any_Virtual{
        struct holder_base{
                virtual ~holder_base(){}
                virtual holder_base* clone() const = 0;
        };

        template<class T>
        struct holder : holder_base{
                holder()
                        : held_()
                {}

                holder(T const& t)
                        : held_(t)
                {}

                virtual ~holder(){
                }

                virtual holder_base* clone() const {
                        return new holder<T>(*this);
                }

                T held_;
        };

public:
        Any_Virtual()
                : storage_(0)
        {}

        Any_Virtual(Any_Virtual const& other)
                : storage_(other.storage_->clone())
        {}

        template<class T>
        Any_Virtual(T const& t)
                : storage_(new holder<T>(t))
        {}

        ~Any_Virtual(){
                Clear();
        }

        Any_Virtual& operator=(Any_Virtual const& other){
                Clear();
                storage_ = other.storage_->clone();
                return *this;
        }

        template<class T>
        Any_Virtual& operator=(T const& t){
                Clear();
                storage_ = new holder<T>(t);
                return *this;
        }

        void Clear(){
                if(storage_)
                        delete storage_;
        }

        template<class T>
        T& As(){
                return static_cast<holder<T>*>(storage_)->held_;
        }

private:
        holder_base* storage_;
};

// the following demonstrates the use of void pointers 
// and function pointers to templated operate functions
// to safely hide the type

enum Operation{
        CopyTag,
        DeleteTag
};

template<class T>
void Operate(void*const& in, void*& out, Operation op){
        switch(op){
        case CopyTag:
                out = new T(*static_cast<T*>(in));
                return;
        case DeleteTag:
                delete static_cast<T*>(out);
        }
}

class Any_VoidPtr{
public:
        Any_VoidPtr()
                : object_(0)
                , operate_(0)
        {}

        Any_VoidPtr(Any_VoidPtr const& other)
                : object_(0)
                , operate_(other.operate_)
        {
                if(other.object_)
                        operate_(other.object_, object_, CopyTag);
        }

        template<class T>
        Any_VoidPtr(T const& t)
                : object_(new T(t))
                , operate_(&Operate<T>)
        {}

        ~Any_VoidPtr(){
                Clear();
        }

        Any_VoidPtr& operator=(Any_VoidPtr const& other){
                Clear();
                operate_ = other.operate_;
                operate_(other.object_, object_, CopyTag);
                return *this;
        }

        template<class T>
        Any_VoidPtr& operator=(T const& t){
                Clear();
                object_ = new T(t);
                operate_ = &Operate<T>;
                return *this;
        }

        void Clear(){
                if(object_)
                        operate_(0,object_,DeleteTag);
                object_ = 0;
        }

        template<class T>
        T& As(){
                return *static_cast<T*>(object_);
        }

private:
        typedef void (*OperateFunc)(void*const&,void*&,Operation);

        void* object_;
        OperateFunc operate_;
};

int main(){
        Any_Virtual a = 6;
        std::cout << a.As<int>() << std::endl;

        a = std::string("oh hi!");
        std::cout << a.As<std::string>() << std::endl;

        Any_Virtual av2 = a;

        Any_VoidPtr a2 = 42;
        std::cout << a2.As<int>() << std::endl;

        Any_VoidPtr a3 = a.As<std::string>();
        a2 = a3;
        a2.As<std::string>() += " - again!";
        std::cout << "a2: " << a2.As<std::string>() << std::endl;
        std::cout << "a3: " << a3.As<std::string>() << std::endl;

        a3 = a;
        a3.As<Any_Virtual>().As<std::string>() += " - and yet again!!";
        std::cout << "a: " << a.As<std::string>() << std::endl;
        std::cout << "a3->a: " << a3.As<Any_Virtual>().As<std::string>() << std::endl;

        std::cin.get();
}
Xeo
fuente
1
Por "borrado de tipo", ¿realmente se refiere al "polimorfismo"? Creo que "borrado de tipo" tiene un significado algo específico, que generalmente se asocia con, por ejemplo, genéricos de Java.
Oliver Charlesworth
3
@Oli: El borrado de texto se puede implementar con polimorfismo, pero esa no es la única opción, mi segundo ejemplo lo muestra. :) Y con el borrado de tipo quiero decir que su estructura no depende de un tipo de plantilla, por ejemplo. Boost.Function no le importa si lo alimenta con un functor, un puntero de función o incluso una lambda. Lo mismo con Boost.Shared_Ptr. Puede especificar una función de asignación y desasignación, pero el tipo real de la shared_ptrno refleja esto, siempre será el mismo, shared_ptr<int>por ejemplo, a diferencia del contenedor estándar.
Xeo
2
@ Matthieu: considero que el segundo ejemplo también escribe safe. Siempre sabes el tipo exacto en el que estás operando. ¿O me estoy perdiendo algo?
Xeo
2
@ Matthieu: Tienes razón. Normalmente, tal As(s) función (s) no se implementaría de esa manera. Como dije, ¡de ninguna manera es seguro de usar! :)
Xeo
44
@lurscher: Bueno ... ¿nunca usaste las versiones de impulso o estándar de ninguno de los siguientes? function, shared_ptr, any, Etc.? Todos emplean borrado tipo para la comodidad del usuario dulce dulce.
Xeo

Respuestas:

100

Todas las técnicas de borrado de tipo en C ++ se realizan con punteros de función (para comportamiento) y void*(para datos). Los métodos "diferentes" simplemente difieren en la forma en que agregan el azúcar semántico. Las funciones virtuales, por ejemplo, son solo azúcar semántica para

struct Class {
    struct vtable {
        void (*dtor)(Class*);
        void (*func)(Class*,double);
    } * vtbl
};

iow: punteros de función.

Dicho esto, sin embargo, hay una técnica que me gusta particularmente: es shared_ptr<void>, simplemente porque hace que las personas que no saben que pueden hacer esto se sorprendan: puede almacenar cualquier dato en un shared_ptr<void>, y aún así llamar al destructor correcto en el final, porque el shared_ptrconstructor es una plantilla de función y usará el tipo del objeto real pasado para crear el eliminador de forma predeterminada:

{
    const shared_ptr<void> sp( new A );
} // calls A::~A() here

Por supuesto, esto es solo el void*borrado de tipo habitual / puntero de función, pero muy convenientemente empaquetado.

Marc Mutz - mmutz
fuente
9
Casualmente, tuve que explicar el comportamiento de shared_ptr<void>un amigo mío con un ejemplo de implementación hace solo unos días. :) Realmente es genial.
Xeo
Buena respuesta; Para hacerlo increíble, un bosquejo de cómo se puede crear una tabla falsa para cada tipo borrado es muy educativo. Tenga en cuenta que las implementaciones de falsa vtables y puntero de función le brindan estructuras conocidas del tamaño de la memoria (en comparación con los tipos virtuales puros) que pueden almacenarse fácilmente localmente y (fácilmente) divorciarse de los datos que están virtualizando.
Yakk - Adam Nevraumont
por lo tanto, si shared_ptr almacena un Derivado *, pero Base * no declaró el destructor como virtual, shared_ptr <void> todavía funciona según lo previsto, ya que, para empezar, nunca conoció una clase base. ¡Frio!
TamaMcGlinn
@Apollys: lo hace, pero unique_ptrno borra el borrador, por lo que si desea asignar unique_ptr<T>a a unique_ptr<void>, debe proporcionar un argumento de borrador, explícitamente, que sepa cómo borrar el a Ttravés de a void*. Si ahora se desea asignar una S, también, entonces usted necesita un Deleter, de manera explícita, que sabe cómo eliminar una Tpor una void*y también una Spor una void*, y , dada una void*, sabe si es una To un S. En ese momento, ha escrito un borrador de tipo borrado para unique_ptr, y luego también funciona para unique_ptr. Simplemente no fuera de la caja.
Marc Mutz - mmutz
Siento que la pregunta que respondió fue "¿Cómo soluciono el hecho de que esto no funciona unique_ptr?" Útil para algunas personas, pero no abordó mi pregunta. Supongo que la respuesta es, porque los punteros compartidos obtuvieron más atención en el desarrollo de la biblioteca estándar. Lo cual creo que es un poco triste porque los punteros únicos son más simples, por lo que debería ser más fácil implementar funcionalidades básicas, y son más eficientes para que las personas los usen más. En cambio, tenemos exactamente lo contrario.
Apollys apoya a Monica el
54

Básicamente, esas son sus opciones: funciones virtuales o punteros de función.

La forma en que almacena los datos y los asocia con las funciones puede variar. Por ejemplo, puede almacenar un puntero a base y hacer que la clase derivada contenga los datos y las implementaciones de funciones virtuales, o puede almacenar los datos en otro lugar (por ejemplo, en un búfer asignado por separado), y solo hacer que la clase derivada proporcione las implementaciones de funciones virtuales, que toman un punto void*que apunta a los datos. Si almacena los datos en un búfer separado, podría usar punteros de función en lugar de funciones virtuales.

El almacenamiento de un puntero a base funciona bien en este contexto, incluso si los datos se almacenan por separado, si hay varias operaciones que desea aplicar a sus datos borrados por tipo. De lo contrario, terminará con múltiples punteros de función (uno para cada una de las funciones borradas por tipo), o funciones con un parámetro que especifica la operación a realizar.

Anthony Williams
fuente
1
Entonces, en otras palabras, ¿los ejemplos que di en la pregunta? Sin embargo, gracias por escribirlo así, especialmente en las funciones virtuales y las operaciones múltiples en los datos borrados por tipo.
Xeo
Hay al menos otras 2 opciones. Estoy componiendo una respuesta.
John Dibling
25

También me gustaría tener en cuenta (similar a void*) el uso de "almacenamiento bruto": char buffer[N].

En C ++ 0x tienes std::aligned_storage<Size,Align>::typepara esto.

Puede almacenar todo lo que desee allí, siempre que sea lo suficientemente pequeño y maneje la alineación correctamente.

Matthieu M.
fuente
44
Bueno, sí, Boost.Function en realidad usa una combinación de esto y el segundo ejemplo que di. Si el functor es lo suficientemente pequeño, lo almacena internamente dentro del functor_buffer. Es bueno saberlo std::aligned_storage, ¡gracias! :)
Xeo
También puede usar la ubicación nueva para esto.
rustyx
2
@RustyX: En realidad, tienes que hacerlo. std::aligned_storage<...>::typees solo un búfer en bruto que, a diferencia char [sizeof(T)], está adecuadamente alineado. Sin embargo, por sí mismo es inerte: no inicializa su memoria, no construye un objeto, nada. Por lo tanto, una vez que tenga un búfer de este tipo, debe construir manualmente objetos dentro de él (ya sea con newun constructmétodo de colocación o de asignación ) y también tiene que destruir manualmente los objetos dentro de él (ya sea invocando manualmente su destructor o usando un destroymétodo de asignación )
Matthieu M.
22

Stroustrup, en el lenguaje de programación C ++ (4a edición) §25.3 , establece:

Las variantes de la técnica de usar una única representación en tiempo de ejecución para valores de varios tipos y confiar en el sistema de tipos (estático) para garantizar que se usen solo de acuerdo con su tipo declarado se ha llamado borrado de tipo .

En particular, no es necesario el uso de funciones virtuales o punteros de función para realizar el borrado de tipo si usamos plantillas. El caso, ya mencionado en otras respuestas, de la llamada del destructor correcto según el tipo almacenado en un std::shared_ptr<void>es un ejemplo de eso.

El ejemplo proporcionado en el libro de Stroustrup es igual de agradable.

Piense en implementar template<class T> class Vector, un contenedor en la línea de std::vector. Cuando usará su Vectorcon muchos tipos de punteros diferentes, como sucede a menudo, el compilador supuestamente generará un código diferente para cada tipo de puntero.

Esta hinchazón de código se puede evitar definiendo una especialización de Vector para void*punteros y luego utilizando esta especialización como una implementación de base común Vector<T*>para todos los demás tipos T:

template<typename T>
class Vector<T*> : private Vector<void*>{
// all the dirty work is done once in the base class only 
public:
    // ...
    // static type system ensures that a reference of right type is returned
    T*& operator[](size_t i) { return reinterpret_cast<T*&>(Vector<void*>::operator[](i)); }
};

Como se puede ver, tenemos un contenedor fuertemente tipado, pero Vector<Animal*>, Vector<Dog*>, Vector<Cat*>, ..., compartirá el mismo (C ++ y código para la aplicación binario), que tienen su tipo de puntero borrado detrás void*.

Paolo M
fuente
2
Sin querer ser blasfemo: preferiría CRTP a la técnica dada por Stroustrup.
davidhigh
@davidhigh ¿Qué quieres decir?
Paolo M
Se puede obtener el mismo comportamiento (con una sintaxis menos incómoda) utilizando una clase base CRTPtemplate<typename Derived> VectorBase<Derived> que luego se especializa como template<typename T> VectorBase<Vector<T*> >. Además, este enfoque no funciona solo para punteros, sino para cualquier tipo.
davidhigh
3
Tenga en cuenta que los buenos enlazadores de C ++ combinan métodos y funciones idénticos: el enlazador dorado o el plegado de comdatos MSVC. El código se genera, pero luego se descarta durante el enlace.
Yakk - Adam Nevraumont
1
@davidhigh Estoy tratando de entender tu comentario y me pregunto si puedes darme un enlace o un nombre de un patrón para buscar (no el CRTP, sino el nombre de una técnica que permite la eliminación de tipos sin funciones virtuales o punteros de función) . Respetuosamente, - Chris
Chris Chiasson
19

Consulte esta serie de publicaciones para obtener una lista (bastante corta) de técnicas de borrado de tipo y la discusión sobre las compensaciones: Parte I , Parte II , Parte III , Parte IV .

El que no he visto mencionado aún es Adobe.Poly y Boost.Variant , que puede considerarse un tipo de borrado hasta cierto punto.

Andrzej
fuente
7

Como dijo Marc, uno puede usar yeso std::shared_ptr<void>. Por ejemplo, guarde el tipo en un puntero de función, transmítalo y guárdelo en un functor de un solo tipo:

#include <iostream>
#include <memory>
#include <functional>

using voidFun = void(*)(std::shared_ptr<void>);

template<typename T>
void fun(std::shared_ptr<T> t)
{
    std::cout << *t << std::endl;
}

int main()
{
    std::function<void(std::shared_ptr<void>)> call;

    call = reinterpret_cast<voidFun>(fun<std::string>);
    call(std::make_shared<std::string>("Hi there!"));

    call = reinterpret_cast<voidFun>(fun<int>);
    call(std::make_shared<int>(33));

    call = reinterpret_cast<voidFun>(fun<char>);
    call(std::make_shared<int>(33));


    // Output:,
    // Hi there!
    // 33
    // !
}
Janek Olszak
fuente