KutilkinFedor Dec 10 2020 at 19:30

Обобщаем паттерн посетитель (С++)

8 min

8.7K

Programming*C++*

From sandbox

Недостатки типичной реализации

В статье намеренно не приведен пример типичной реализации паттерна посетителя в C++.

Если вы не знакомы с этим паттерном, то вот тут можно с ним ознакомиться.

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

Поэтому перейдем сразу к недостаткам, которые хотели бы устранить.

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

Что хотим получить?

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

Реализация

Начинаем с создания абстрактного посетителя.

Source:

template< class T >
struct AbstractVisitor
{
    virtual ~AbstractVisitor() = default;
    virtual void visit( T& ) = 0;
};

(Пояснение: здесь виртуальная функция-член visit не является шаблоном, количество виртуальных функций при инстанцировании класса AbstractVisitor точно известно т.к. T является параметром шаблона класса, а не функции )

Инстанс конкретного посетителя сможет обойти только один тип объекта. Нам же необходимо чтобы посетитель мог обходить несколько различных типов объектов.

Для этого создадим простой список типов TypeList и класс агрегатор AbstractVisitors. Список у AbstractVisitors будет содержать все типы объектов, которые посетитель может обойти.

Source:

template< class ... T >
struct TypeList
{

};

template< class T >
struct AbstractVisitor
{
    virtual ~AbstractVisitor() = default;
    virtual void visit( T& ) = 0;
};

template< class ...T >
struct AbstractVisitors;

template< class ... T >
struct AbstractVisitors< TypeList< T... > > : AbstractVisitor< T >...
{
};

Т.к. мы не хотим каждый раз наследоваться от абстрактного посетителя, наследуемся от него один раз и будем принимать функтор (если быть точным, то принимать будем обобщённую лямбду). Для этого создадим класс Dispatcher.

Source:

template< class Functor, class ... T >
struct Dispatcher;

template< class Functor, class ... T >
struct Dispatcher< Functor, TypeList< T... > > : AbstractVisitors< TypeList< T... > >
{
    Dispatcher( Functor functor ) : functor( functor ) {}

    Functor functor;
};

Теперь необходимо для всех типов из листа переопределить виртуальную функцию-член visit.

Для этого создадим класс Resolver, который этим и будет заниматься. А сам класс Dispatcher унаследуем от всех возможных типов Resolver-ов.

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

(Подробнее о том что такое CRTP можно почитать тут).

Source:

template< class Dispatcher, class T >
struct Resolver : AbstractVisitor< T >
{
    void visit( T& obj ) override 
    {
        static_cast< Dispatcher* >( this )->functor( obj );
    };
};

template< class Functor, class ... T >
struct Dispatcher< Functor, TypeList< T... > > : AbstractVisitors< TypeList< T... > >, Resolver< Dispatcher< Functor, TypeList< T... > >, T >...
{
    Dispatcher( Functor functor ) : functor( functor ) {}

    Functor functor;
};

Вроде все в порядке.

Попробуем создать объект класс Dispatcher. Компилятор начинает ругаться на то, что объект класса Dispatcher абстрактный, как же так?

Причина этого в том, что мы переопределили виртуальные функции для Resolver, но для Dispatcher мы ведь ничего не переопределяли.

Чтобы этого избежать, необходимо сделать наследование от AbstractVisitor< T >виртуальным.(Подробнее о размещении объектов в памяти и виртуальном наследовании можно почитать тут.)

Source:

template< class ... T >
struct AbstractVisitors< TypeList< T... > > : virtual AbstractVisitor< T >...
{
};

template< class Dispatcher, class T >
struct Resolver : virtual AbstractVisitor< T >
{
    void visit( T& obj ) override 
    {
        static_cast< Dispatcher* >( this )->functor( obj );
    };
};

Создадим абстрактный базовый класс (AbstractObject) и какие-нибудь классы (Object1, Object2), которые хотели обойти.

Так же создадим функцию test и шаблон функции test, которые будут получать непосредственно ссылку на объект определенного типа.

Пример использования:

Source:

struct Object1;
struct Object2;

using ObjectList = TypeList< Object1, Object2 >;

struct AbstractObject
{
    virtual void accept( AbstractVisitors< ObjectList >& visitor ) = 0; 
};

struct Object1 : AbstractObject
{
    void accept( AbstractVisitors< ObjectList >& visitor ) override 
    { 
        static_cast< AbstractVisitor< Object1 >& >( visitor ).visit( *this );  
    };
};

struct Object2 : AbstractObject
{
    void accept( AbstractVisitors< ObjectList >& visitor ) override 
    { 
        static_cast< AbstractVisitor< Object2 >& >( visitor ).visit( *this );
    };
};

void test( Object1& obj )
{
    std::cout << "1" << std::endl;
}

template< class T >
void test( T& obj )
{
    std::cout << "2" << std::endl;
}

int main()
{
    Object1 t1,t2,t3,t4;
    Object2 e1,e2,e3;

    std::vector< AbstractObject* > vector = { &t1, &e1, &t2, &t3, &e2, &e3, &t4 };
		
    auto l = []( auto& obj ){ test(obj); };
    Dispatcher<decltype(l), ObjectList> dispatcher;
  
    for( auto* obj : vector )
    {
        obj->accept( dispatcher );
    }
}

(Пояснение: мы не можем просто написать visitor.visit( *this ), это приведет к неоднозначности, если классов в иерархии будет больше двух.)

Строчки на которых создается обобщенная лямбда и объект класса Dispatcher какие-то то страшные и не удобные, спрятать бы все это от глаз.

Так же, хотелось бы спрятать функцию-член accept у AbstractObject, Object1 и Object2, т.к. тело функции для всех типов объектов будет одинаковое, различаться будет только тип объекта.

Для этого создадим абстрактный класс Dispatchable. Cделаем у него чисто виртуальную функцию-член accept и шаблон функции-члена который будет принимать функтор. В нем собственно и будем создавать наш Dispatcher.

Помимо этого создадим макрос DISPATCHED, он понадобится чтобы спрятать переопределение функции-члена accept у Object1 и Object2.

Source:

template< class TypeList >
struct Dispatchable
{
    virtual ~Dispatchable() = default;
    virtual void accept( AbstractVisitors< TypeList >& ) = 0;

    template< class Functor >
    void dispatch( Functor functor )
    {
        static Dispatcher< decltype(functor), TypeList > dispatcher( functor );
        accept( dispatcher );
    };
};

#define DISPATCHED( TYPE, TYPE_LIST ) \
    void accept( AbstractVisitors< TYPE_LIST >& visitor ) override \
    { \
        static_cast< AbstractVisitor< TYPE >& >( visitor ).visit( *this );  \
    }

Затем наследуем AbstractObject от класса Dispatchable. А в классы Object1 и Object2 добавляем макрос DISPATCHED.

Source:


struct Object1;
struct Object2;

using ObjectList = TypeList< Object1, Object2 >;

struct AbstractObject : Dispatchable< ObjectList >
{
};

struct Object1 : AbstractObject
{
    DISPATCHED( Object1, ObjectList )
};

struct Object2 : AbstractObject
{
    DISPATCHED( Object2, ObjectList )
};

Отлично, мы спрятали все функции-члены accept и вынесли общий код. Вот теперь все готово.

Пример использования:

Source:

void test( Object1& obj )
{
    std::cout << "1" << std::endl;
}

template< class T >
void test( T& obj )
{
    std::cout << "2" << std::endl;
}

int main()
{
    Object1 t1,t2,t3,t4;
    Object2 e1,e2,e3;

    std::vector< AbstractObject* > vector = { &t1, &e1, &t2, &t3, &e2, &e3, &t4 };

    for( auto* obj : vector )
    {
        obj->dispatch( []( auto& obj ) { test(obj); } );
    }
}

Output:

Производительность

Хороший вопрос был задан в комментариях, чем этот подход лучше по сравнению с уже имеющимися в стандартной библиотеке std::visit и std::variant.

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

Сравним производительность при их типичном использовании.

А именно:

Диспетчеризацию через метод dispatch и std::visit.
Вызов виртуальной функции-члена с вызовом обычной, обернутой в std::visit.
Вызов обычной функции-члена с вызовом обычной функции, обернутой в std::visit.

Вызов виртуальной функции сравнивать с вызовом виртуальной обернутой в std::visit нет особого смысла.

1. Диспетчеризация

Clang 10.0, Optim=OFast

GCC 10.1, Optim=OFast

2. Вызов виртуальной функции

Clang 10.0, Optim=OFast

GCC 10.1, Optim=OFast

3. Вызов обычной функции

Clang 10.0, Optim=OFast

GCC 10.1, Optim=OFast

Тут ссылка на код для Quick Benchmarks.

Когда использовать?

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

Пример:

Source

template< class T >
void templateFunc1()
{
	/*some code*/
}

template< class T >
void templateFunc2( T& obj )
{
	/*some code*/
}

std::vector< AbstractObject* > vector = { /* ... */ };

for( auto* obj : vector )
{
	//вызов обычной функции-члена
	obj->getName();
	
	//вызов виртуальной функции-члена
	obj->action();
	
	//получение типа и передача его в шаблон-функции
	obj->dispatch([](auto& obj) 
	{ 
		//1 case
		using T = std::decay_t< decltype(obj) >;	
		templateFunc1<T>();		
		
		//2 case
		templateFunc2( obj );	
	};
}

Заключение

Чтобы добавить или удалить класс, который будет обрабатываться посетителем, достаточно просто изменить список типов.
Посетитель не привязан к предметной области, т.к. является шаблоном класса.
Можем в полной мере пользоваться шаблонами функций.
Остается возможность пользоваться обычной реализацией посетителя, достаточно лишь сделать своего наследника от AbstractVisitors и передавать его в функцию accept.

Какие недостатки?

Дополнительная косвенность, т.к. Dispatcher содержит функтор.

Ссылка на код в compiler explorer.

Full source:

#include <type_traits>
#include <iostream>
#include <vector>

template< class ... T >
struct TypeList
{

};

template< class T >
struct AbstractVisitor
{
    virtual ~AbstractVisitor() = default;
    virtual void visit( T& ) = 0;
};

template< class ...T >
struct AbstractVisitors;

template< class ... T >
struct AbstractVisitors< TypeList< T... > > : virtual AbstractVisitor< T >...
{
};

template< class Dispatcher, class T >
struct Resolver : virtual AbstractVisitor< T >
{
    void visit( T& obj ) override 
    {
        static_cast< Dispatcher* >( this )->functor( obj );
    };
};

template< class Functor, class ... T >
struct Dispatcher;

template< class Functor, class ... T >
struct Dispatcher< Functor, TypeList< T... > > : AbstractVisitors< TypeList< T... > >, Resolver< Dispatcher< Functor, TypeList< T... > >, T >...
{
    Dispatcher( Functor functor ) : functor( functor ) {}

    Functor functor;
};

template< class TypeList >
struct Dispatchable
{
    virtual ~Dispatchable() = default;
    virtual void accept( AbstractVisitors< TypeList >& ) = 0;

    template< class Functor >
    void dispatch( Functor functor )
    {
        static Dispatcher< decltype(functor), TypeList > dispatcher( functor );
        accept( dispatcher );
    };
};

#define DISPATCHED( TYPE, TYPE_LIST ) \
    void accept( AbstractVisitors< TYPE_LIST >& visitor ) override \
    { \
        static_cast< AbstractVisitor< TYPE >& >( visitor ).visit( *this );  \
    }

struct Object1;
struct Object2;

using ObjectList = TypeList< Object1, Object2 >;

struct AbstractObject : Dispatchable< ObjectList >
{
};

struct Object1 : AbstractObject
{
    DISPATCHED( Object1, ObjectList )
};

struct Object2 : AbstractObject
{
    DISPATCHED( Object2, ObjectList )
};

void test( Object1& obj )
{
    std::cout << "1" << std::endl;
}

template< class T >
void test( T& obj )
{
    std::cout << "2" << std::endl;
}

int main()
{
    Object1 t1,t2,t3,t4;
    Object2 e1,e2,e3;

    std::vector< AbstractObject* > vector = { &t1, &e1, &t2, &t3, &e2, &e3, &t4 };

    for( auto* obj : vector )
    {
        obj->dispatch( []( auto& obj ) { test(obj); } );
    }
}

Tags:

Hubs: