Как написать собственный dynamic_cast - PullRequest
5 голосов
/ 04 июля 2010

Об этом спрашивали в интервью.

Как написать собственный dynamic_cast.Я думаю, на основе функции name typeid.

Теперь, как реализовать собственный typid?Понятия не имею.

Ответы [ 4 ]

20 голосов
/ 04 июля 2010

Существует причина, по которой у вас нет никакой подсказки, dynamic_cast и static_cast не похожи на const_cast или reinterpret_cast, они фактически выполняют арифметику указателей и в некоторой степени безопасны от типов.

Указатель арифметический

Чтобы проиллюстрировать это, подумайте о следующем дизайне:

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

struct Derived: Base1, Base2 {};

Экземпляр Derived должен выглядеть примерно так (он основан на gcc, поскольку на самом деле он зависит от компилятора ...):

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

Теперь подумайте о работе, необходимой для кастинга:

  • приведение от Derived к Base1 не требует дополнительной работы, они находятся по тому же физическому адресу
  • приведение от Derived до Base2 требует сдвига указателя на 2 байта

Следовательно, необходимо знать расположение объектов в памяти, чтобы иметь возможность проводить преобразование между одним производным объектом и одним из его основания. И это известно только компилятору, информация не доступна через какой-либо API, она не стандартизирована или что-либо еще.

В коде это будет выглядеть так:

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

И это, конечно, для static_cast.

Теперь, если бы вы могли использовать static_cast в реализации dynamic_cast, то вы могли бы использовать компилятор и позволить ему обрабатывать арифметику указателей для вас ... но вы все еще не ушли .

Написание dynamic_cast?

Перво-наперво, нам нужно уточнить спецификации dynamic_cast:

  • dynamic_cast<Derived*>(&base); возвращает ноль, если base не является экземпляром Derived.
  • dynamic_cast<Derived&>(base); бросает std::bad_cast в этом случае.
  • dynamic_cast<void*>(base); возвращает адрес самого производного класса
  • dynamic_cast соблюдайте спецификации доступа (public, protected и private наследование)

Я не знаю о вас, но я думаю, что это будет ужасно. Использование typeid здесь недостаточно:

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

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

Проблема здесь в том, что typeid(base) == typeid(Derived) != typeid(Intermediate), так что вы тоже не можете на это полагаться.

Еще одна забавная вещь:

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

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

static_cast не работает, когда задействовано виртуальное наследование ... поэтому мы столкнулись с проблемой арифметических вычислений с указателями.

Почти решение

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

Вам понадобятся некоторые мелочи в конструкторе:

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

Итак, давайте проверим:

  • классическое использование: хорошо
  • virtual наследование? должно работать ... но не проверено
  • с учетом спецификаторов доступа ... ARG: /

Удачи всем, кто пытается реализовать это вне компилятора, действительно: x

1 голос
/ 04 июля 2010

Один из способов - объявить статический идентификатор (например, целое число), который определяет идентификатор класса. В классе вы можете реализовать как статические, так и ограниченные подпрограммы, которые возвращают идентификатор класса ( Remeber для пометки подпрограмм виртуальными ).

Статический идентификатор должен быть инициализирован при инициализации приложения. Одним из способов является вызов подпрограммы InitializeId для каждого класса, но это означает, что имена классов должны быть известны, и код инициализации должен изменяться каждый раз, когда изменяется иерархия классов. Другой способ - проверить действительный идентификатор во время создания, но это приводит к дополнительным расходам, поскольку каждый раз, когда создается класс, выполняется проверка, но только в первый раз полезно (кроме того, если класс не создан, статическая процедура не может быть полезной). поскольку идентификатор никогда не инициализируется).

Справедливой реализацией может быть класс шаблона:

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 должен быть определен для каждого класса, производного от ClassId, а gClassId и gClassMap должны быть видны в глобальной области видимости.

Доступные идентификаторы классов хранятся в одной статической целочисленной переменной, доступной для всех классов (базовый класс ClassID или глобальная переменная), которая увеличивается каждый раз, когда назначается новый идентификатор класса.

Для представления иерархии классов достаточно карты между идентификатором класса и его производными классами. Чтобы узнать, может ли какой-либо класс быть приведен к определенному классу, выполните итерацию по карте и отметьте объявление производных.

Есть много трудностей, с которыми приходится сталкиваться ... использование ссылок! виртуальные деривации! плохой кастинг! Неправильная инициализация отображения типов классов приведет к ошибкам приведения ...


Отношения между классами должны быть определены вручную, жестко закодированы с помощью процедуры инициализации. Это позволяет определить, является ли класс производным от двух классов или общим производным.

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

Лично я согласен с "есть причина, если компиляторы реализуют dynamic_cast"; возможно, компилятор сделает все лучше (особенно в отношении примера кода!).

0 голосов
/ 04 июля 2010

Чтобы попытаться ответить немного менее рутинно, если чуть менее определено:

Что вам нужно сделать, это привести указатель на int *, создать новый тип T в стеке, привести указатель на него к int * и сравнить первое int в обоих типах. Это сделает сравнение адресов vtable. Если они одного типа, у них будет один и тот же vtable. Иначе, нет.

Более разумные из нас просто придерживаются интегральной константы в наших классах.

0 голосов
/ 04 июля 2010

Легко. Получите все объекты из некоторого интерфейса typeid с помощью виртуальной функции WhoAmI (). Переопределите его во всех производных классах.

...