Comment écrire propre dynamic_cast

Question

ont été posées dans l'interview.

Comment écrire propre dynamic_cast. Je pense que, sur la base de la fonction du nom de typeid.

Maintenant, comment mettre en œuvre propre TypeID? Je n'ai aucune idée là-dessus.

Answer 1

Il y a une raison pour laquelle vous n'avez pas la moindre idée, dynamic_cast et static_cast ne sont pas comme const_cast ou reinterpret_cast, ils effectuent en fait l'arithmétique des pointeurs et sont un peu typé.

Le pointeur arithmétique

Pour illustrer cela, pensez à la conception suivante:

struct Base1 { virtual ~Base1(); char a; };
struct Base2 { virtual ~Base2(); char b; };

struct Derived: Base1, Base2 {};

Une instance de Derived devrait ressembler à ceci (il est basé sur gcc, car il est en réalité dépend du compilateur ...):

|      Cell 1       | Cell 2 |      Cell 3        | Cell 4 |
| vtable pointer    |    a   | vtable pointer     |    b   |
|         Base 1             |        Base 2               |
|                     Derived                              |

Pensez maintenant aux travaux nécessaires pour la coulée:

• Castings de Derived à Base1 ne nécessite aucun travail supplémentaire, ils sont à la même adresse physique
• coulée à partir de Derived nécessite de passer de Base2 pour le pointeur de 2 octets

Par conséquent, il est nécessaire de connaître la mise en mémoire des objets pour pouvoir cast entre un objet dérivé et l'un de sa base. Et ce n'est connu que le compilateur, les informations ne sont pas accessibles via une API, il est pas normalisé ou quoi que ce soit d'autre.

Dans le code, cela se traduirait comme:

Derived derived;
Base2* b2 = reinterpret_cast<Base2>(((char*)&derived) + 2);

Et qui est, bien sûr, pour un static_cast.

Maintenant, si vous étiez en mesure d'utiliser static_cast dans la mise en œuvre de dynamic_cast, alors vous pourriez tirer parti du compilateur et laisser gérer l'arithmétique des pointeurs pour vous ... mais vous n'êtes toujours pas hors du bois.

dynamic_cast écriture?

Tout d'abord, nous devons clarifier les spécifications des dynamic_cast:

• retourne dynamic_cast<Derived*>(&base); null si base n'est pas une instance de Derived.
• dynamic_cast<Derived&>(base); jette std::bad_cast dans ce cas.
• dynamic_cast<void*>(base); renvoie l'adresse de la classe la plus dérivée
• dynamic_cast respecter les spécifications d'accès (public, protected et héritage de private)

Je ne sais pas vous, mais je pense que ça va être laid. L'utilisation typeid ne suffit pas ici:

struct Base { virtual ~Base(); };
struct Intermediate: Base {};
struct Derived: Base {};

void func()
{
  Derived derived;
  Base& base = derived;
  Intermediate& inter = dynamic_cast<Intermediate&>(base); // arg
}

Le problème ici est que typeid(base) == typeid(Derived) != typeid(Intermediate), de sorte que vous ne pouvez pas compter sur ce soit.

Une autre chose amusante:

struct Base { virtual ~Base(); };
struct Derived: virtual Base {};

void func(Base& base)
{
  Derived& derived = static_cast<Derived&>(base); // Fails
}

static_cast ne fonctionne pas lorsque l'héritage virtuel est impliqué ... Nous avons donc aller un problème de calcul arithmétique rampante pointeur dans.

Une solution presque

class Object
{
public:
  Object(): mMostDerived(0) {}
  virtual ~Object() {}

  void* GetMostDerived() const { return mMostDerived; }

  template <class T>
  T* dynamiccast()
  {
    Object const& me = *this;
    return const_cast<T*>(me.dynamiccast());
  }

  template <class T>
  T const* dynamiccast() const
  {
    char const* name = typeid(T).name();
    derived_t::const_iterator it = mDeriveds.find(name);
    if (it == mDeriveds.end()) { return 0; }
    else { return reinterpret_cast<T const*>(it->second); }
  }

protected:
  template <class T>
  void add(T* t)
  {
    void* address = t;
    mDerived[typeid(t).name()] = address;
    if (mMostDerived == 0 || mMostDerived > address) { mMostDerived= address; }
  }

private:
  typedef std::map < char const*, void* > derived_t;
  void* mMostDerived;
  derived_t mDeriveds;
};

// Purposely no doing anything to help swapping...

template <class T>
T* dynamiccast(Object* o) { return o ? o->dynamiccast<T>() : 0; }

template <class T>
T const* dynamiccast(Object const* o) { return o ? o->dynamiccast<T>() : 0; }

template <class T>
T& dynamiccast(Object& o)
{
  if (T* t = o.dynamiccast<T>()) { return t; }
  else { throw std::bad_cast(); }
}

template <class T>
T const& dynamiccast(Object const& o)
{
  if (T const* t = o.dynamiccast<T>()) { return t; }
  else { throw std::bad_cast(); }
}

Vous avez besoin de quelques petites choses dans le constructeur:

class Base: public Object
{
public:
  Base() { this->add(this); }
};

Alors, nous allons vérifier:

• utilisations classiques: ok
• l'héritage de virtual? il devrait fonctionner ... mais pas testé
• le respect spécificateurs d'accès ... ARG: /

Bonne chance à tous ceux qui essaient de mettre en œuvre ce en dehors du compilateur, vraiment: x

Answer 2

Une façon consiste à déclarer un identificateur statique (un nombre entier par exemple) qui définit l'ID de classe. Dans la classe que vous pourriez mettre en œuvre à la fois statique et routines scope Wich retourne l'identificateur de classe ( Remeber à des routines de marque virtuelle ).

L'identifiant statique doit être initialisé lors de l'initialisation de l'application. Une façon est d'appeler une routine de InitializeId pour chaque classe, mais cela signifie que les noms de classe doivent être connus, et le code d'initialisation doit être modifié à chaque fois que la hiérarchie des classes est modifiée. Une autre façon consiste à vérifier identificateur valide au moment de la construction, mais ceci introduit une surcharge puisque chaque fois qu'une classe est construite la vérification est exécutée, mais seulement la première fois est utile (en outre, si aucune classe est construit, la routine statique ne peut pas être utile puisque l'identifiant est jamais été initialisé).

Une mise en œuvre équitable pourrait être une classe de modèle:

template <typename T>
class ClassId<T>
{
    public:

    static int GetClassId() { return (sClassId); }

    virtual int GetClassId() const { return (sClassId); }

    template<typename U> static void StateDerivation() {
        gClassMap[ClassId<T>::GetClassId()].push_back(ClassId<U>::GetClassId());
    }

    template<typename U> const U DynamicCast() const {
        std::map<int, std::list<int>>::const_iterator it = gClassMap.find(ClassId<T>); // Base class type, with relative derivations declared with StateDerivation()
        int id = ClassId<U>::GetClassId();

        if (id == ClassId<T>::GetClassId()) return (static_cast<U>(this));

        while (it != gClassMap.end()) {
            for (std::list<int>::const_iterator = pit->second.begin(), pite = it->second->end(); pit != pite; pit++) {
                if ((*pit) == id) return (static_cast<U>(this));
                // ... For each derived element, iterate over the stated derivations.
                // Easy to implement with a recursive function, better if using a std::stack to avoid recursion.
            }
        }

        return (null); 
    }  

    private:

    static int sClassId;
}

#define CLASS_IMP(klass) static int ClassId<klass>::sClassId = gClassId++;

// Global scope variables    

static int gClassId = 0;
static std::map<int, std::list<int>> gClassMap;

CLASS_IMP est définie pour chaque classe provenant de ClassId et gClassId et gClassMap est visible à portée mondiale.

Les identificateurs de classe sont disponibles keeped par une seule variable entière statique accessible par toutes les classes (une classe de base ClassID ou une variable globale), qui est incrémenté chaque fois qu'un nouvel identificateur de classe est attribué.

Pour représente la hiérarchie des classes est suffisante une carte entre l'identifiant de classe et ses classes dérivées. Pour savoir si une classe peut être casté à une classe spécifique, itérer sur la carte et contrôle dérivations déclaration des.

Il y a beaucoup de difficultés à faire face à ... l'utilisation de références! dérivations virtuel! mauvais casting! Bad initialisation de mappage de type de classe conduira à la coulée des erreurs ...

---

Les relations entre les classes doit être définie manuellement, avec la routine hardcoded d'initialisation. Cela permet de déterminer si une classe dérivée de, ou si deux classes comme une dérivation commune.

class Base : ClassId<Base> {  }
#define CLASS_IMP(Base);
class Derived : public Base, public ClassId<Derived> {  }
#define CLASS_IMP(Derived);
class DerivedDerived : public Derived, public ClassId<DerivedDerived> {  }
#define CLASS_IMP(DerivedDerived);

static void DeclareDerivations()
{
    ClassId<Base>::StateDerivation<Derived>();
    ClassId<Derived>::StateDerivation<DerivedDerived>();
}

---

Personnellement, je suis d'accord avec « il y a une raison si compilateurs met en œuvre dynamic_cast »; probablement le compilateur faire les choses mieux (en particulier en ce qui concerne le code exemple!).

Answer 3

Pour tenter une réponse un peu moins de routine, si un peu moins défini:

Ce que vous devez faire est de lancer le pointeur sur un int *, créez un nouveau type T sur la pile, jeta un pointeur à int * et comparer le premier int dans les deux types. Cela va faire une comparaison d'adresse vtable. Si elles sont du même type, ils auront les mêmes vtable. Sinon, ils ne le font pas.

Le plus sensible de nous coller juste une constante intégrale dans nos classes.

Answer 4

facile. Dériver tous les objets à partir de plusieurs interfaces typeid avec un WhoAmI de fonctions virtuelles (). Remplacer dans toutes les classes dérivées.