Geben Sie Löschtechniken ein

136

(Mit Typlöschung meine ich, einige oder alle Typinformationen zu einer Klasse zu verbergen , ähnlich wie Boost.Any .)
Ich möchte die Techniken zum Löschen von Typen kennenlernen und gleichzeitig die mir bekannten teilen. Meine Hoffnung ist es, eine verrückte Technik zu finden, an die jemand in seiner dunkelsten Stunde gedacht hat. :) :)

Der erste und offensichtlichste und am häufigsten verwendete Ansatz, den ich kenne, sind virtuelle Funktionen. Verstecken Sie einfach die Implementierung Ihrer Klasse in einer schnittstellenbasierten Klassenhierarchie. Viele Boost-Bibliotheken tun dies, zum Beispiel Boost.Any tut dies, um Ihren Typ auszublenden, und Boost.Shared_ptr tut dies, um die ( De- ) Zuordnungsmechanik auszublenden.

Dann gibt es die Option mit Funktionszeigern auf Vorlagenfunktionen, während das eigentliche Objekt in einem void*Zeiger gehalten wird, wie dies Boost.Function tut, um den realen Typ des Funktors auszublenden. Beispielimplementierungen finden Sie am Ende der Frage.

Also, für meine eigentliche Frage:
Welche anderen Löschtechniken kennen Sie? Bitte geben Sie ihnen nach Möglichkeit einen Beispielcode, Anwendungsfälle, Ihre Erfahrungen mit ihnen und möglicherweise Links zur weiteren Lektüre.

Bearbeiten
(Da ich nicht sicher war, ob ich dies als Antwort hinzufügen oder nur die Frage bearbeiten sollte, mache ich einfach die sicherere.)
Eine andere nette Technik, um den tatsächlichen Typ von etwas ohne virtuelle Funktionen oder void*Fummelei zu verbergen , ist das Ein GMan beschäftigt hier , was für meine Frage relevant ist, wie genau dies funktioniert.


Beispielcode:

#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
quelle
1
Beziehen Sie sich mit "Typlöschung" wirklich auf "Polymorphismus"? Ich denke, "Type Erasure" hat eine etwas spezifische Bedeutung, die normalerweise mit zB Java-Generika verbunden ist.
Oliver Charlesworth
3
@Oli: Typlöschung kann mit Polymorphismus implementiert werden, aber das ist nicht die einzige Option, mein zweites Beispiel zeigt das. :) Und mit Typlöschung meine ich nur, dass Ihre Struktur zum Beispiel nicht von einem Vorlagentyp abhängt. Boost.Function ist es egal, ob Sie ihm einen Funktor, einen Funktionszeiger oder sogar ein Lambda zuführen. Gleiches gilt für Boost.Shared_Ptr. Sie können eine Zuweisungs- und Freigabefunktion angeben, aber der tatsächliche Typ der Funktion shared_ptrspiegelt dies nicht wider. Er ist shared_ptr<int>beispielsweise im Gegensatz zum Standardcontainer immer derselbe .
Xeo
2
@Matthieu: Ich halte das zweite Beispiel auch für sicher. Sie kennen immer den genauen Typ, mit dem Sie arbeiten. Oder fehlt mir etwas?
Xeo
2
@ Matthieu: Du hast recht. Normalerweise würde eine solche AsFunktion nicht auf diese Weise implementiert. Wie gesagt, keineswegs sicher zu bedienen! :)
Xeo
4
@lurscher: Nun ... haben Sie noch nie die Boost- oder Standardversion einer der folgenden Versionen verwendet ? function, shared_ptr, anyEtc.? Sie alle verwenden Typlöschung für süße, süße Benutzerkomfort.
Xeo

Antworten:

100

Alle Löschtechniken in C ++ werden mit Funktionszeigern (für das Verhalten) und void*(für Daten) ausgeführt. Die "verschiedenen" Methoden unterscheiden sich einfach darin, wie sie semantischen Zucker hinzufügen. Virtuelle Funktionen sind zB nur semantischer Zucker für

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

iow: Funktionszeiger.

Das heißt, es gibt eine Technik, die ich besonders mag: Es ist shared_ptr<void>einfach, weil sie Leute um den Verstand bringt, die nicht wissen, dass Sie dies tun können: Sie können alle Daten in einem speichern shared_ptr<void>und haben immer noch den richtigen Destruktor auf dem Ende, da der shared_ptrKonstruktor eine Funktionsvorlage ist und standardmäßig den Typ des tatsächlich übergebenen Objekts zum Erstellen des Löschers verwendet:

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

Dies ist natürlich nur die übliche void*Löschung vom Typ / Funktionszeiger, aber sehr bequem verpackt.

Marc Mutz - mmutz
quelle
9
Zufälligerweise musste ich vor shared_ptr<void>einigen Tagen einem Freund von mir das Verhalten anhand einer Beispielimplementierung erklären . :) Es ist wirklich cool.
Xeo
Gute Antwort; Um es erstaunlich zu machen, ist eine Skizze, wie eine gefälschte Tabelle statisch für jeden gelöschten Typ erstellt werden kann, sehr lehrreich. Beachten Sie, dass Fake-Vtables und Funktionszeiger-Implementierungen Ihnen bekannte Strukturen in Speichergröße (im Vergleich zu rein virtuellen Typen) bieten, die einfach lokal gespeichert und (leicht) von den Daten, die sie virtualisieren, getrennt werden können.
Yakk - Adam Nevraumont
Wenn also shared_ptr dann ein abgeleitetes * speichert, die Basis * den Destruktor jedoch nicht als virtuell deklariert, funktioniert shared_ptr <void> weiterhin wie beabsichtigt, da es zunächst nicht einmal über eine Basisklasse Bescheid wusste. Cool!
TamaMcGlinn
@Apollys: unique_ptrDer Deleter wird zwar gelöscht, aber nicht typisiert. Wenn Sie also a unique_ptr<T>einem zuweisen möchten unique_ptr<void>, müssen Sie explizit ein Deleter-Argument angeben, das weiß, wie das Tdurch a gelöscht wird void*. Wenn Sie jetzt ein zuweisen möchten S, auch dann müssen Sie eine deleter, explizit, die weiß , wie ein löschen Tdurch ein void*und auch ein Sdurch ein void*, und , da einvoid* , weiß , ob es ein ist Toder ein S. Zu diesem Zeitpunkt haben Sie einen typenlöschenden Löscher für geschrieben unique_ptr, und dann funktioniert er auch für unique_ptr. Nur nicht sofort einsatzbereit.
Marc Mutz - mmutz
Ich habe das Gefühl, die Frage, die Sie beantwortet haben, lautete: "Wie kann ich die Tatsache umgehen, dass dies nicht funktioniert unique_ptr?" Nützlich für einige Leute, hat aber meine Frage nicht beantwortet. Ich denke, die Antwort ist, weil gemeinsame Zeiger bei der Entwicklung der Standardbibliothek mehr Aufmerksamkeit erhielten. Was ich ein wenig traurig finde, weil eindeutige Zeiger einfacher sind, daher sollte es einfacher sein, grundlegende Funktionen zu implementieren, und sie sind effizienter, sodass die Benutzer sie häufiger verwenden sollten. Stattdessen haben wir genau das Gegenteil.
Apollys unterstützt Monica
54

Grundsätzlich sind dies Ihre Optionen: virtuelle Funktionen oder Funktionszeiger.

Wie Sie die Daten speichern und mit den Funktionen verknüpfen, kann variieren. Sie könnten beispielsweise einen Zeiger auf die Basis speichern und die abgeleitete Klasse die Daten und die Implementierungen der virtuellen Funktionen enthalten lassen, oder Sie könnten die Daten an anderer Stelle speichern (z. B. in einem separat zugewiesenen Puffer) und nur die abgeleitete Klasse bereitstellen lassen die virtuellen Funktionsimplementierungen, die void*auf die Daten verweisen. Wenn Sie die Daten in einem separaten Puffer speichern, können Sie anstelle virtueller Funktionen Funktionszeiger verwenden.

Das Speichern eines Zeigers auf die Basis funktioniert in diesem Zusammenhang gut, auch wenn die Daten separat gespeichert werden, wenn Sie mehrere Operationen auf Ihre typgelöschten Daten anwenden möchten. Andernfalls erhalten Sie mehrere Funktionszeiger (einen für jede der vom Typ gelöschten Funktionen) oder Funktionen mit einem Parameter, der die auszuführende Operation angibt.

Anthony Williams
quelle
1
Also, mit anderen Worten, die Beispiele, die ich in der Frage gegeben habe? Vielen Dank, dass Sie es so geschrieben haben, insbesondere in Bezug auf die virtuellen Funktionen und mehrere Operationen an den typenlöschenden Daten.
Xeo
Es gibt mindestens 2 weitere Optionen. Ich verfasse eine Antwort.
John Dibling
25

Ich würde auch (ähnlich void*) die Verwendung von "Rohspeicher" in Betracht ziehen : char buffer[N].

In C ++ 0x haben Sie std::aligned_storage<Size,Align>::typedafür.

Sie können dort alles speichern, was Sie möchten, solange es klein genug ist und Sie mit der Ausrichtung richtig umgehen.

Matthieu M.
quelle
4
Nun ja, Boost.Function verwendet tatsächlich eine Kombination aus diesem und dem zweiten Beispiel, das ich gegeben habe. Wenn der Funktor klein genug ist, speichert er ihn intern im functor_buffer. Gut zu wissen std::aligned_storage, danke! :)
Xeo
Sie können hierfür auch die Platzierung neu verwenden .
Rustyx
2
@RustyX: Eigentlich Sie haben zu. std::aligned_storage<...>::typeist nur ein Rohpuffer, der im Gegensatz char [sizeof(T)]dazu geeignet ausgerichtet ist. An sich ist es jedoch inert: Es initialisiert seinen Speicher nicht, baut kein Objekt auf, nichts. Sobald Sie einen Puffer dieses Typs haben, müssen Sie Objekte darin manuell erstellen (entweder mit Platzierung newoder einer Zuweisungsmethode construct) und Sie müssen auch die darin enthaltenen Objekte manuell zerstören (entweder manuell ihren Destruktor aufrufen oder eine Zuweisungsmethode destroyverwenden ).
Matthieu M.
22

Stroustrup heißt in der Programmiersprache C ++ (4. Ausgabe) §25.3 :

Varianten der Technik, eine einzelne Laufzeitdarstellung für Werte einer Reihe von Typen zu verwenden und sich auf das (statische) Typsystem zu verlassen, um sicherzustellen, dass sie nur gemäß ihrem deklarierten Typ verwendet werden, wurden als Typlöschung bezeichnet .

Insbesondere ist keine Verwendung von virtuellen Funktionen oder Funktionszeigern erforderlich, um das Löschen von Typen durchzuführen, wenn Vorlagen verwendet werden. Der bereits in anderen Antworten erwähnte Fall des richtigen Destruktoraufrufs gemäß dem in a gespeicherten Typ std::shared_ptr<void>ist ein Beispiel dafür.

Das Beispiel in Stroustrups Buch ist genauso unterhaltsam.

Denken Sie an die Implementierung template<class T> class Vectoreines Containers nach dem Vorbild von std::vector. Wenn Sie Ihren Vectormit vielen verschiedenen Zeigertypen verwenden, wie es häufig vorkommt, generiert der Compiler angeblich für jeden Zeigertyp einen anderen Code.

Dieses Aufblähen des Codes kann verhindert werden, indem eine Spezialisierung des Vektors für void*Zeiger definiert und diese Spezialisierung dann als gemeinsame Basisimplementierung Vector<T*>für alle anderen Typen verwendet wird 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)); }
};

Wie Sie sehen können, haben wir einen stark typisierte Container aber Vector<Animal*>, Vector<Dog*>, Vector<Cat*>, ..., das gleiche (C ++ teilen und binär) Code für die Implementierung, dessen Zeiger Typen gelöscht hinter void*.

Paolo M.
quelle
2
Ohne blasphemisch zu sein: Ich würde CRTP der von Stroustrup gegebenen Technik vorziehen.
Davidhigh
@davidhigh Was meinst du?
Paolo M
Man kann das gleiche Verhalten (mit einer weniger akward-Syntax) erhalten, indem man eine CRTP- Basisklasse verwendet, template<typename Derived> VectorBase<Derived>die dann als spezialisiert ist template<typename T> VectorBase<Vector<T*> >. Darüber hinaus funktioniert dieser Ansatz nicht nur für Zeiger, sondern für jeden Typ.
Davidhigh
3
Beachten Sie, dass gute C ++ - Linker identische Methoden und Funktionen zusammenführen: den Goldlinker oder die MSVC-Comdat-Faltung. Code wird generiert, aber beim Verknüpfen verworfen.
Yakk - Adam Nevraumont
1
@davidhigh Ich versuche, Ihren Kommentar zu verstehen und frage mich, ob Sie mir einen Link oder einen Namen eines Musters geben können, nach dem gesucht werden soll (nicht das CRTP, sondern der Name einer Technik, die das Löschen von Typen ohne virtuelle Funktionen oder Funktionszeiger ermöglicht). . Hochachtungsvoll, - Chris
Chris Chiasson
7

Wie von Marc angegeben, kann man Besetzung verwenden std::shared_ptr<void>. Speichern Sie beispielsweise den Typ in einem Funktionszeiger, wandeln Sie ihn um und speichern Sie ihn in einem Funktor nur eines Typs:

#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
quelle