Двойная отправка в C++

Двойная диспетчеризация в C++ — это механизм, который распределяет вызов функции по разным конкретным функциям в зависимости от типов среды выполнения двух объектов, участвующих в вызове. Проще говоря, его функция вызывается с использованием двух разных виртуальных таблиц соответствующих двух объектов. Я знаю, что это звучит загадочно, но не волнуйтесь, я приду к решению с двойной отправкой после того, как попробую большинство наивных решений, так что вы получите полное понимание концепции без ненужной путаницы.

/!\: Первоначально опубликовано @ www.vishalchovatiya.com.

Мотивация

• Поначалу указатель на базовый класс имел смысл; вам не нужно было знать фактический производный класс. Итак, вы решили предоставить своим клиентам единую коллекцию указателей базового класса следующим образом:

struct Animal {
    virtual const char *name() = 0;
};
using AnimalList = vector<Animal*>

• Когда вы добавили свои первые несколько классов, ваши предположения подтвердились; вам никогда не нужно было знать фактический тип.

struct Cat : Animal {
    const char *name() { return "Cat"; }
};
struct Dog : Animal {
    const char *name() { return "Dog"; }
};

• Но требования меняются.
• Однажды клиент пришел к вам и сказал: «Я пытаюсь смоделировать человека, который боится собак, поэтому они убегают, когда видят их. Но они любят кошек, поэтому стараются погладить их, когда увидят».
• Черт. Теперь ваши предположения неверны. Тип нужно знать. И вы находитесь под давлением, чтобы уложиться в срок.

Идентификация типа во время выполнения

• Тогда вы подумали: «Ну, есть только два вида животных, это не так уж и плохо». Итак, вы написали такой код:

struct Person {
    void ReactTo(Animal *_animal) {
        if (dynamic_cast<Dog *>(_animal))
            RunAwayFrom(_animal);
        else if (dynamic_cast<Cat *>(_animal))
            TryToPet(_animal);
    }
    void RunAwayFrom(Animal *_animal) { cout << "Run Away From " << _animal->name() << endl; }
    void TryToPet(Animal *_animal) { cout << "Try To Pet " << _animal->name() << endl; }
};

• Затем клиент сказал, что если Animal это Horse, они хотят попробовать на нем прокатиться.

void Person::ReactTo(Animal *_animal) {
    if (dynamic_cast<Dog *>(_animal))
        RunAwayFrom(_animal);
    else if (dynamic_cast<Cat *>(_animal))
        TryToPet(_animal);
    else if (dynamic_cast<Horse *>(_animal))
        TryToRide(_animal);
}

• Вы видите, что это сходит с ума. В какой-то момент в будущем вам может не понравиться работать с собственным кодом. Мы все были там. Тем не менее, эта тенденция продолжалась некоторое время, пока вы не столкнулись с таким беспорядком:

void Person::ReactTo(Animal *_animal) {
    if (dynamic_cast<Dog *>(_animal) || dynamic_cast<Gerbil *>(_animal)){
        if (dynamic_cast<Dog *>(_animal) && dynamic_cast<Dog>()->GetBreed() == DogBreed.Daschund) // Daschund's are the exception
            TryToPet(_animal);
        else
            RunAwayFrom(_animal);    
    }
    else if (dynamic_cast<Cat *>(_animal) || dynamic_cast<Pig *>(_animal))
        TryToPet(_animal);
    else if (dynamic_cast<Horse *>(_animal))
        TryToRide(_animal);
    else if (dynamic_cast<Lizard *>(_animal))
        TryToFeed(_animal);
    else if (dynamic_cast<Mole *>(_animal))
        Attack(_animal)
    // etc.
}

• Этот список становится довольно длинным, как-то подумали вы про себя. Все эти dynamic_cast кажутся неправильными, к тому же они какие-то медленные. Итак, в дополнение к рефакторингу, вы придумываете решение, которое идентифицирует typeid(), это немного быстрее, чем dynamic_cast, но все же это не оптимальная производительность.

Использование полиморфизма

• Поскольку кто-то из вашего старшего/наставника предлагает вам использовать перечисление с полиморфными методами для определения типа, вы написали следующий код:

enum class AnimalType { Dog, Cat };
struct Animal {
    virtual const char *name() = 0;
    virtual AnimalType type() = 0;
};
struct Cat : Animal {
    const char *name() { return "Cat"; }
    AnimalType type() { return AnimalType::Cat; }
};
struct Dog : Animal {
    const char *name() { return "Dog"; }
    AnimalType type() { return AnimalType::Dog; }
};
struct Person {
    void ReactTo(Animal *_animal) {
        if (_animal->type() == AnimalType::Cat)
            TryToPet(_animal);
        else if (_animal->type() == AnimalType::Dog)
            RunAwayFrom(_animal);
    }
    void RunAwayFrom(Animal *_animal) { cout << "Run Away From " << _animal->name() << endl; }
    void TryToPet(Animal *_animal) { cout << "Try To Pet " << _animal->name() << endl; }
};
int main() {
    Person p;
    Animal *animal_0 = new Dog;
    p.ReactTo(animal_0);
    Animal *animal_1 = new Cat;
    p.ReactTo(animal_1);
    return 0;
}

• Вы можете получить улучшение производительности, но все же у вас останется длинный список if/else-if.

Более функциональный и модульный подход

using PersonMethodPtr = void (Person::*)(Animal *);
using ReactionHash = unordered_map<AnimalType, PersonMethodPtr>;
void Person::ReactTo(Animal *_animal){
    static const ReactionHash reactionFunctions{
        {AnimalType::Cat, &TryToPet},
        {AnimalType::Dog, &RunAwayFrom},
        // etc.
    };
    reactionFunctions[_animal->type()](_animal);
}

• Но здесь вы косвенно пишете свою собственную виртуальную таблицу (очень плохую виртуальную таблицу), которая может вообще не дать прироста производительности из-за накладных расходов на хэширование и поиск. Кроме того, вы платите немного больше за память для хранения вашей таблицы поиска.

Единая отправка

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

struct Animal {
    virtual string name() = 0;
    virtual void Visit(class ReactVisitor *visitor) = 0;
};
struct ReactVisitor {
    class Person *person = nullptr;
};
struct Person {
    void ReactTo(Animal *_animal) {
        ReactVisitor visitor{this};        
        _animal->Visit(&visitor);
    }
    void RunAwayFrom(Animal *_animal) { cout << "Run Away From " << _animal->name() << endl; }
    void TryToPet(Animal *_animal) { cout << "Try To Pet " << _animal->name() << endl; }
};
struct Cat : public Animal {
    string name() { return "Cat"; }
    void Visit(ReactVisitor *visitor) { visitor->person->TryToPet(this); }
};
struct Dog : public Animal {
    string name() { return "Dog"; }
    void Visit(ReactVisitor *visitor) { visitor->person->RunAwayFrom(this); }
};
int main() {
    Person p;
    vector<Animal*> animals = {new Dog, new Cat};
    for(auto&& animal : animals)
        p.ReactTo(animal);    
    return 0;
}

• Чтобы сохранить посредника в вызове функции маршрута, мы должны добавить метод visit(ReactVisitor *), который принимает посредника, то есть ReactVisitor, в качестве параметра. Затем мы добавляем соответствующее поведение для каждого типа Animal, то есть Dog и Cat.

Проблемы с единым диспетчерским подходом

1. Почему класс Dog должен диктовать, как на него реагировать Person? Мы просочились в подробности реализации класса Person и, следовательно, нарушили инкапсуляцию.
2. Что, если у класса Person есть другие варианты поведения, которые они хотят реализовать? Неужели мы собираемся добавить новый виртуальный метод в базовый класс для каждого из них?

Решение вышеуказанной проблемы приведет нас к использованию механизма двойной отправки.

Двойная отправка в C++

• Мы можем преодолеть недостаток Single-Dispatch, добавив еще один уровень косвенности (например, AnimalVisitor).

/* -------------------------------- Added Visitor Classes ------------------------------- */
struct AnimalVisitor {
    virtual void Visit(struct Cat *) = 0;
    virtual void Visit(struct Dog *) = 0;
};
struct ReactVisitor : AnimalVisitor {
    ReactVisitor(struct Person *p) : person{p} {}
    void Visit(struct Cat *c);
    void Visit(struct Dog *d);
    struct Person *person = nullptr;
};
/* --------------------------------------------------------------------------------------- */

struct Animal {
    virtual string name() = 0;
    virtual void Visit(struct AnimalVisitor *visitor) = 0;      
};
struct Cat : Animal {
    string name() { return "Cat"; }
    void Visit(AnimalVisitor *visitor) { visitor->Visit(this); } // 2nd dispatch <<---------
};
struct Dog : Animal {
    string name() { return "Dog"; }
    void Visit(AnimalVisitor *visitor) { visitor->Visit(this); } // 2nd dispatch <<---------
};
struct Person {
    void ReactTo(Animal *_animal) {
        ReactVisitor visitor{this};        
        _animal->Visit(&visitor);   // 1st dispatch <<---------
    }
    void RunAwayFrom(Animal *_animal) { cout << "Run Away From " << _animal->name() << endl; }
    void TryToPet(Animal *_animal) { cout << "Try To Pet " << _animal->name() << endl; }
};

/* -------------------------------- Added Visitor Methods ------------------------------- */
void ReactVisitor::Visit(Cat *c) { // Finally comes here <<-------------
    person->TryToPet(c);
}
void ReactVisitor::Visit(Dog *d) { // Finally comes here <<-------------
    person->RunAwayFrom(d);
}
/* --------------------------------------------------------------------------------------- */

int main() {
    Person p;
    for(auto&& animal : vector<Animal*>{new Dog, new Cat})
        p.ReactTo(animal);
    return 0;
}

• Как вы можете видеть выше, скорее зависящий непосредственно от ReactVisitor, мы взяли AnimalVisitor как еще один уровень косвенности. И метод visit(AnimalVisitor *) в классе Cat и Dog принимает AnimalVisitor в качестве параметра.
• Это дает нам два преимущества: i). нам не нужно записывать поведение человека в классах Cat и Dog, поэтому мы не нарушаем правило инкапсуляции, и ii). мы выделяем реакцию Person в отдельный класс (т.е. ReactVisitor), поэтому мы поощряем Принцип единой ответственности.

Как работает механизм двойной отправки?

Я знаю, что все усложняется, но я бы сказал, что это достаточно сложно. Фрейм стека функций и одно изображение цепочки вызовов функций с фрагментом кода значительно упростят его.

• Из Person::ReactTo мы вызываем Animal::visit, который перенаправляется на соответствующий переопределенный визит, т. е. либо Cat::visit, либо Dog::visit.
• Из переопределенного Cat::visit(AnimalVisitor*) мы вызываем AnimalVisitor::visit, который снова будет отправляться на соответствующий переопределенный, т. е. либо ReactionVisitor::visit(Cat*), либо ReactionVisitor::visit(Dog*).

Альтернативный подход к двойной отправке в современном C++ с использованием std::variant и std::visit

struct Animal {
    virtual string name() = 0;
};
struct Cat : Animal {
    string name() { return "Cat"; }
};
struct Dog : Animal {
    string name() { return "Dog"; }
};
struct Person {
    void RunAwayFrom(Animal *animal) { cout << "Run Away From " << animal->name() << endl; }
    void TryToPet(Animal *animal) { cout << "Try To Pet " << animal->name() << endl; }
};
struct ReactVisitor {
    void operator()(Cat *c) { person->TryToPet(c); }
    void operator()(Dog *d){ person->RunAwayFrom(d); }
    Person *person = nullptr;
};
using animal_ptr = std::variant<Cat*, Dog*>;
int main() {
    Person p;
    ReactVisitor rv{&p};
    for(auto&& animal : vector<animal_ptr>({new Dog, new Cat}))
        std::visit(rv, animal);
    return 0;
}

• Так что те из вас, кто не знаком с std::variant, могут рассматривать его как союз. И строка std::variant<Cat*, Dog*> предполагает, что вы можете использовать/назначать/получать доступ либо к Cat*, либо к Dog* одновременно.
• А Современный C++ предоставляет нам std::visit, которые принимают callable, т.е. ReactVisitor в нашем случае с перегруженным оператором функции для каждого типа и std::variant. Вы также используете лямбда-функции, а не функтор, то есть ReactVisitor.

Преимущества механизма двойной отправки

1. Соблюдение принципа единой ответственности, что означает выделение логики конкретного типа в отдельный объект/класс. В нашем случае ReactVisitor обрабатывает реакцию только для разных типов животных.
2. Соблюдение принципа открытого-закрытого означает, что новые функции могут быть добавлены, не касаясь каких-либо заголовков классов, после того, как мы вставили метод visit() для иерархии. Например, если вы хотите добавить метод sound() для каждого отдельного животного, вы можете создать SoundVisitor и остальную часть редактирования идет так же ReactVisitor.
3. Это будет очень полезно, когда вы уже выполнили модульное тестирование для всей своей иерархии, и теперь вы не хотите его трогать и хотите добавить новую функциональность.
4. Производительность выше dynamic_cast, typeid() и проверка на enum/string сравнения.

Пример использования механизма двойной отправки

1. Сортировка смешанного набора объектов: Вы можете реализовать фильтрацию с двойной отправкой. Например: «Дайте мне все Cats из vector<Animal*>».
2. Вы можете добавить дополнительные функции ко всей иерархии наследования, не изменяя ее снова и снова. если вы хотите добавить метод sound() для каждого отдельного животного, вы можете создать SoundVisitor, а остальная часть редактирования будет такой же, как ReactVisitor.
3. Системы обработки событий, которые используют как тип события, так и тип объекта-приемника для вызова правильной процедуры обработки событий.
4. Адаптивные алгоритмы коллизий обычно требуют, чтобы коллизии между разными объектами обрабатывались по-разному. Типичным примером является игровая среда, где столкновение между космическим кораблем и астероидом вычисляется иначе, чем столкновение между космическим кораблем и космической станцией.

Вывод

Каждое решение имеет свои преимущества и недостатки, и выбор одного из них зависит от конкретных потребностей вашего проекта. C++ представляет уникальные проблемы при проектировании таких высокоуровневых абстракций, поскольку он сравнительно жесткий и статически типизированный. Абстракции в C++ также стремятся быть как можно более дешевыми с точки зрения производительности во время выполнения и потребления памяти, что добавляет еще одно измерение сложности к проблеме.

Ссылка

Эта статья стала побочным продуктом, пока я писал о классическом Visitor Design Pattern, потому что без механизма двойной диспетчеризации в C++ классический посетитель не существует. Большая часть заслуг в этой статье и изображениях принадлежит Энди Джи. Фрагменты кода, которые вы видите в этой статье, упрощены, а не сложны.

Есть предложения, вопросы или пожелания Hi? Снимите давление, вы на расстоянии одного клика.🖱️