How to write own dynamic_cast

Question

This have been asked in the interview.

How to write own dynamic_cast. I think, on the basis of typeid's name function.

Now how to implement own typid? I have no clue on it.

Answer 1

There is a reason you don't have any clue, dynamic_cast and static_cast are not like const_cast or reinterpret_cast, they actually perform pointer arithmetic and are somewhat typesafe.

The pointer arithmetic

In order to illustrate this, think of the following design:

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

struct Derived: Base1, Base2 {};

An instance of Derived should look something like this (it's based on gcc since it is actually compiler dependent...):

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

Now think of the work necessary for casting:

• casting from Derived to Base1 does not require any extra work, they are at the same physical address
• casting from Derived to Base2 necessitates to shift the pointer by 2 bytes

Therefore, it is necessary to know the memory layout of the objects to be able to cast between one derived object and one of its base. And this is only known to the compiler, the information is not accessible through any API, it's not standardised or anything else.

In code, this would translate like:

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

And that is, of course, for a static_cast.

Now, if you were able to use static_cast in the implementation of dynamic_cast, then you could leverage the compiler and let it handle the pointer arithmetic for you... but you're still not out of the wood.

Writing dynamic_cast ?

First things first, we need to clarify the specifications of dynamic_cast:

• dynamic_cast<Derived*>(&base); returns null if base is not an instance of Derived.
• dynamic_cast<Derived&>(base); throws std::bad_cast in this case.
• dynamic_cast<void*>(base); returns the address of the most derived class
• dynamic_cast respect the access specifications (public, protected and private inheritance)

I don't know about you, but I think it's going to be ugly. Using typeid is not sufficient here:

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

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

The issue here is that typeid(base) == typeid(Derived) != typeid(Intermediate), so you can't rely on that either.

Another amusing thing:

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

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

static_cast doesn't work when virtual inheritance is involved... so we've go a problem of pointer arithmetic computation creeping in.

An almost solution

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(); }
}

You need some little things in the constructor:

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

So, let's check:

• classic uses: okay
• virtual inheritance ? it should work... but not tested
• respecting access specifiers... ARG :/

Good luck to anyone trying to implement this outside of the compiler, really :x

Answer 2

ONe way is to declare a static identifier (an integer for example) which defines the class ID. In the class you could implement both static and scoped routines wich returns the class identifier (Remeber to mark routines virtual).

The static identifier shall be initialized at application initialization. One way is to call an InitializeId routine for each class, but this mean that the class names must be known, and the initialization code shall be modified each time the class hierarchy is modified. Another way is to check for valid identifier at construction time, but this introduces an overhead since each time a class is constructed the check is executed, but only the first time is usefull (additionally if no class is constructed, the static routine cannot be usefull since the identifier is never initialized).

A fair implementation could be a template class:

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 shall be defined in for each class deriving from ClassId, and gClassId and gClassMap shall be visible at global scope.

The available class identifiers are keeped by a single static integer variable accessible by all classes (a base class ClassID or a global variable), which is incremented each time a new class identifier is assigned.

To represents the class hierarchy is sufficient a map between the class identifier and its derived classes. To know whether any class can be casted to a specific class, iterate over the map and check declare derivations.

There are many difficulties to face... use of references! virtual derivations! bad casting! Bad class type mapping initialization will lead to casting errors...

---

Relationships between classes shall be defined manually, hardcoded with the initialization routine. This allow to determine whether a class derived from, or whether two classes as a common derivation.

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>();
}

---

Personally I agree with "there is a reason if compilers implements dynamic_cast"; probably the compiler do the things better (especially with respect of the example code!).