CrazyC CrazyC - 1 month ago 7
C++ Question

How to write own dynamic_cast

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

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