Techniques d'effacement de caractères

136

(Avec l'effacement de type, je veux dire cacher tout ou partie des informations de type concernant une classe, un peu comme Boost.Any .)
Je veux mettre la main sur les techniques d'effacement de type, tout en partageant celles que je connais. Mon espoir est un peu de trouver une technique folle à laquelle quelqu'un a pensé à son heure la plus sombre. :)

La première approche, la plus évidente et la plus courante, que je connaisse, ce sont les fonctions virtuelles. Cachez simplement l'implémentation de votre classe dans une hiérarchie de classes basée sur une interface. De nombreuses bibliothèques Boost le font, par exemple Boost.Any le fait pour masquer votre type et Boost.Shared_ptr le fait pour masquer le mécanisme de (dé) allocation.

Ensuite, il y a l'option avec des pointeurs de fonction vers des fonctions modèles, tout en maintenant l'objet réel dans un void*pointeur, comme Boost.Function le fait pour masquer le type réel du foncteur. Des exemples d'implémentations peuvent être trouvés à la fin de la question.

Donc, pour ma vraie question:
quelles autres techniques d'effacement de type connaissez-vous? Veuillez leur fournir, si possible, un exemple de code, des cas d'utilisation, votre expérience avec eux et peut-être des liens pour en savoir plus.

Modifier
(Étant donné que je n'étais pas sûr d'ajouter ceci comme réponse, ou simplement de modifier la question, je vais simplement faire la plus sûre.)
Une autre technique intéressante pour masquer le type réel de quelque chose sans fonctions virtuelles ni void*violon est le un GMan emploie ici , en rapport avec ma question sur la façon dont cela fonctionne exactement.


Exemple de code:

#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
la source
1
Par «effacement de type», faites-vous vraiment référence au «polymorphisme»? Je pense que "l'effacement de type" a une signification quelque peu spécifique, qui est généralement associée par exemple aux génériques Java.
Oliver Charlesworth
3
@Oli: L'effacement de type peut être implémenté avec le polymorphisme, mais ce n'est pas la seule option, mon deuxième exemple le montre. :) Et avec l'effacement de type, je veux juste dire que votre structure ne dépend pas d'un type de modèle par exemple. Boost.Function ne se soucie pas si vous lui donnez un foncteur, un pointeur de fonction ou même un lambda. Idem avec Boost.Shared_Ptr. Vous pouvez spécifier un allocateur et une fonction de désallocation, mais le type réel de shared_ptrne reflète pas cela, il sera toujours le même, shared_ptr<int>par exemple, contrairement au conteneur standard.
Xeo
2
@Matthieu: Je considère que le deuxième exemple tape également safe. Vous connaissez toujours le type exact sur lequel vous opérez. Ou est-ce que je manque quelque chose?
Xeo
2
@Matthieu: Vous avez raison. Normalement, une telle Asfonction (s) ne serait pas implémentée de cette façon. Comme je l'ai dit, pas sûr à utiliser! :)
Xeo
4
@lurscher: Eh bien ... jamais utilisé les versions boost ou std de l' un des éléments suivants? function, shared_ptr, any, Etc.? Ils utilisent tous l'effacement de type pour un confort d'utilisation doux.
Xeo

Réponses:

100

Toutes les techniques d'effacement de type en C ++ sont effectuées avec des pointeurs de fonction (pour le comportement) et void*(pour les données). Les méthodes «différentes» diffèrent simplement par la façon dont elles ajoutent du sucre sémantique. Les fonctions virtuelles, par exemple, ne sont que du sucre sémantique pour

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

iow: pointeurs de fonction.

Cela dit, il y a une technique que j'aime particulièrement, cependant: c'est shared_ptr<void>simplement parce que cela épate les gens qui ne savent pas que vous pouvez le faire: vous pouvez stocker toutes les données dans un shared_ptr<void>, tout en ayant le bon destructeur appelé à la end, car le shared_ptrconstructeur est un modèle de fonction, et utilisera le type de l'objet réel passé pour créer le suppresseur par défaut:

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

Bien sûr, il ne s'agit que de l' void*effacement habituel de type pointeur de fonction /, mais il est très pratique.

Marc Mutz - mmutz
la source
9
Par coïncidence, j'ai dû expliquer le comportement de shared_ptr<void>à un de mes amis avec un exemple d'implémentation il y a quelques jours à peine. :) C'est vraiment cool.
Xeo
Bonne réponse; pour le rendre incroyable, un croquis de la façon dont une fausse table peut être créée de manière statique pour chaque type effacé est très éducatif. Notez que les fausses vtables et les implémentations de pointeurs de fonction vous donnent des structures connues de la taille de la mémoire (par rapport aux types virtuels purs) qui peuvent être facilement stockées localement et (facilement) séparées des données qu'elles virtualisent.
Yakk - Adam Nevraumont
donc, si shared_ptr stocke ensuite un Derived *, mais que la Base * n'a pas déclaré le destructeur comme virtuel, shared_ptr <void> fonctionne toujours comme prévu, car il n'a même jamais connu une classe de base pour commencer. Cool!
TamaMcGlinn
@Apollys: Il le fait, mais unique_ptrn'efface pas le suppresseur, donc si vous voulez affecter a unique_ptr<T>à a unique_ptr<void>, vous devez fournir un argument deleter, explicitement, qui sait comment supprimer le Tvia a void*. Si vous voulez maintenant attribuer un Saussi, alors vous avez besoin d'un suppresseur, explicitement, qui sait comment supprimer un à Ttravers un void*et aussi un à Stravers un void*, et , étant donné a void*, sait s'il s'agit d'un Tou d'un S. À ce stade, vous avez écrit un suppresseur de type effacé pour unique_ptr, puis cela fonctionne également pour unique_ptr. Tout simplement pas hors de la boîte.
Marc Mutz - mmutz
J'ai l'impression que la question à laquelle vous avez répondu était "Comment contourner le fait que cela ne fonctionne pas unique_ptr?" Utile pour certaines personnes, mais n'a pas répondu à ma question. Je suppose que la réponse est, parce que les pointeurs partagés ont attiré plus d'attention dans le développement de la bibliothèque standard. Ce qui, à mon avis, est un peu triste car les pointeurs uniques sont plus simples, il devrait donc être plus facile d'implémenter les fonctionnalités de base et ils sont plus efficaces afin que les gens les utilisent davantage. Au lieu de cela, nous avons exactement le contraire.
Apollys soutient Monica le
54

Fondamentalement, ce sont vos options: des fonctions virtuelles ou des pointeurs de fonction.

La manière dont vous stockez les données et les associez aux fonctions peut varier. Par exemple, vous pouvez stocker un pointeur vers la base et faire en sorte que la classe dérivée contienne les données et les implémentations de fonction virtuelle, ou vous pouvez stocker les données ailleurs (par exemple dans un tampon alloué séparément), et demander simplement à la classe dérivée de fournir les implémentations de fonction virtuelle, qui prennent unvoid* pointant vers les données. Si vous stockez les données dans un tampon séparé, vous pouvez utiliser des pointeurs de fonction plutôt que des fonctions virtuelles.

Le stockage d'un pointeur vers la base fonctionne bien dans ce contexte, même si les données sont stockées séparément, s'il existe plusieurs opérations que vous souhaitez appliquer à vos données effacées de type. Sinon, vous vous retrouvez avec plusieurs pointeurs de fonction (un pour chacune des fonctions effacées de type), ou des fonctions avec un paramètre qui spécifie l'opération à effectuer.

Anthony Williams
la source
1
Donc, en d'autres termes, les exemples que j'ai donnés dans la question? Cependant, merci de l'avoir écrit comme ça, en particulier pour les fonctions virtuelles et les opérations multiples sur les données effacées de type.
Xeo
Il existe au moins 2 autres options. Je rédige une réponse.
John Dibling
25

Je voudrais également envisager (similaire à void*) l'utilisation de « stockage brut »: char buffer[N].

En C ++ 0x vous avez std::aligned_storage<Size,Align>::typepour cela.

Vous pouvez y stocker tout ce que vous voulez, à condition qu'il soit suffisamment petit et que vous gérez correctement l'alignement.

Matthieu M.
la source
4
Eh bien oui, Boost.Function utilise en fait une combinaison de ceci et du deuxième exemple que j'ai donné. Si le foncteur est suffisamment petit, il le stocke en interne dans le functor_buffer. Bon à savoir std::aligned_storage, merci! :)
Xeo
Vous pouvez également utiliser l' emplacement nouveau pour cela.
rustyx
2
@RustyX: En fait, vous devez le faire. std::aligned_storage<...>::typeest juste un tampon brut qui, contrairement à char [sizeof(T)], est correctement aligné. En soi, cependant, il est inerte: il n'initialise pas sa mémoire, ne construit pas d'objet, rien. Par conséquent, une fois que vous avez un tampon de ce type, vous devez construire manuellement des objets à l'intérieur (avec placement newou une constructméthode d' allocation ) et vous devez également détruire manuellement les objets à l'intérieur (soit en appelant manuellement leur destructeur, soit en utilisant une destroyméthode d' allocation ).
Matthieu M.
22

Stroustrup, dans le langage de programmation C ++ (4e édition) §25.3 , déclare:

Les variantes de la technique consistant à utiliser une seule représentation au moment de l'exécution pour les valeurs d'un certain nombre de types et reposant sur le système de type (statique) pour s'assurer qu'elles ne sont utilisées qu'en fonction de leur type déclaré ont été appelées effacement de type .

En particulier, aucune utilisation de fonctions virtuelles ou de pointeurs de fonction n'est nécessaire pour effectuer un effacement de type si nous utilisons des modèles. Le cas, déjà mentionné dans d'autres réponses, de l'appel de destructeur correct en fonction du type stocké dans a en std::shared_ptr<void>est un exemple.

L'exemple fourni dans le livre de Stroustrup est tout aussi agréable.

Pensez à mettre en œuvre template<class T> class Vector, un conteneur du type std::vector. Lorsque vous utiliserez votre Vectoravec de nombreux types de pointeurs différents, comme cela arrive souvent, le compilateur génèrera un code différent pour chaque type de pointeur.

Ce gonflement du code peut être évité en définissant une spécialisation de Vector pour les void*pointeurs, puis en utilisant cette spécialisation comme une implémentation de base commune de Vector<T*>pour tous les autres types 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)); }
};

Comme vous pouvez le voir, nous avons un conteneur fortement typé mais Vector<Animal*>, Vector<Dog*>, Vector<Cat*>, ..., partagera la même (C ++ et binaire) code pour la mise en œuvre, ayant leur type de pointeur effacé derrière void*.

Paolo M
la source
2
Sans vouloir être blasphématoire: je préférerais le CRTP à la technique donnée par Stroustrup.
davidhigh
@davidhigh Que voulez-vous dire?
Paolo M
On peut obtenir le même comportement (avec une syntaxe moins pratique) en utilisant une classe de base CRTPtemplate<typename Derived> VectorBase<Derived> qui est alors spécialisée en template<typename T> VectorBase<Vector<T*> >. De plus, cette approche ne fonctionne pas uniquement pour les pointeurs, mais pour tout type.
davidhigh
3
Notez que les bons linkers C ++ fusionnent des méthodes et des fonctions identiques: le gold linker ou MSVC comdat fold. Le code est généré, puis rejeté lors de la liaison.
Yakk - Adam Nevraumont
1
@davidhigh J'essaie de comprendre votre commentaire et je me demande si vous pouvez me donner un lien ou un nom d'un modèle pour lequel rechercher (pas le CRTP, mais le nom d'une technique qui permet l'effacement de type sans fonctions virtuelles ou pointeurs de fonction) . Respectueusement, - Chris
Chris Chiasson
19

Voir cette série d'articles pour une liste (assez courte) des techniques d'effacement de type et la discussion sur les compromis: Partie I , Partie II , Partie III , Partie IV .

Celui que je n'ai pas encore vu mentionné est Adobe.Poly et Boost.Variant , qui peuvent être considérés dans une certaine mesure comme un effacement de type.

Andrzej
la source
7

Comme indiqué par Marc, on peut utiliser le cast std::shared_ptr<void>. Par exemple, stockez le type dans un pointeur de fonction, transtypez-le et stockez-le dans un foncteur d'un seul type:

#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
la source