В этой статье мы рассмотрим один из вариантов реализации поведенческого шаблона проектирования Acyclic Visitor без ипользования RTTI.
Основным назначением поведенческого шаблона проектирования Visitor является введение абстрактной функциональности для иерархической структуры объектов.
Реализации шаблона можно условно разделить на две категории.
- Cyclic Visitor. Основан на механизме перегрузки функций (Function overloading). Из-за циклической зависимости (посещаемой иерархии необходимо уточнение типа посетителя, посетителю необходимо уточнение всех классов в иерархии), область применения ограничевается только устойчивыми иерархиями (в которые редко добавляются новые классы).
- Acyclic Visitor. Основан на механизме динамической идентификации типа данных (RTTI). Нет ограничений на посещаемые иерархии, но за счет использования динамической идентификации снижается производительность.
struct entity;
struct geometry;
struct model;
struct visitor
{
virtual bool visit(entity &) = 0;
virtual bool visit(geometry &) = 0;
virtual bool visit(model &) = 0;
};
struct entity
{
public:
virtual ~entity() {}
virtual void accept(visitor & obj) { obj.visit(*this); }
};
struct geometry : entity
{
public:
void accept(visitor & obj) { obj.visit(*this); }
};
struct model : geometry
{
public:
void accept(visitor & obj) { obj.visit(*this); }
};
struct test_visitor : visitor
{
public:
void visit(entity & obj)
{
// something
}
void visit(geometry & obj)
{
// something
}
void visit(model & obj)
{
// something
}
};template<typename _Visitable>
struct visitor
{
virtual void visit(_Visitable &) = 0;
};
struct visitor_base
{
virtual ~visitor_base(){}
};
struct entity
{
public:
virtual ~entity()
{}
virtual void accept(visitor_base & obj)
{
using entity_visitor = visitor<entity>;
if(entity_visitor * ev = dynamic_cast<entity_visitor*>(&obj))
ev->visit(*this);
}
};
struct geometry : entity
{
public:
virtual void accept(visitor_base & obj)
{
using geometry_visitor = visitor<geometry>;
if(geometry_visitor * gv = dynamic_cast<geometry_visitor*>(&obj))
gv->visit(*this);
}
};
struct model : geometry
{
public:
virtual void accept(visitor_base & obj)
{
using model_visitor = visitor<model>;
if(model_visitor * mv = dynamic_cast<model_visitor*>(&obj))
mv->visit(*this);
}
};
struct test_visitor : visitor_base,
visitor<entity>,
visitor<geometry>,
visitor<model>
{
public:
void visit(entity & obj)
{
// something
}
void visit(geometry & obj)
{
// something
}
void visit(model & obj)
{
// something
}
};Производительность
Выполнение простой операции на массиве из трех миллионов элементов
| Pattern | Time(ms) |
|---|---|
| Cyclic visitor | 11.3 |
| Acyclic visitor(RTTI) | 220.4 |
Видно что посетитель c динамической идентификацией сильно уступает в производительности обычному шаблону. Нашей основной задачей будет сохранить ацикличность шаблона, но приблизить его производительность к варианту без RTTI.
Реализация
Основная идея заключается в том, что для набора посещаемых классов из иерархии, посетитель генерирует специальную таблицу позднего связывания (vtbl), содержащую методы-преобразователи, вызывающие соответствующие методы у посетителя, основываясь на уникальном идентификаторе типа посещаемого класса.
Итак, у нас есть две подзадачи
- Получить уникальный идентификатор типа
- Сгенерировать таблицу позднего связывания
Уникальный идентификатор типа
Для решения этой задачи мы воспользуемся маленькой header-only библиотекой CTTI. В качестве уникального идентификатора будем использовать хеш, посчитанный на основе уникального строкового имени типа.
namespace detail {
using hash_type = std::uint64_t;
template<typename _Base, typename _Specific>
struct tag {};
template<typename _Base, typename _Specific>
inline constexpr hash_type get_hash()
{
using tag_type = tag<typename std::remove_cv<_Base>::type,
typename std::remove_cv<_Specific>::type>;
return ctti::unnamed_type_id<tag_type>().hash();
}
} /* detail */Исходя из того, что мы будем обрабатывать наши объекты полиморфно и точный тип объекта нам будет неизвестен, кажный класс в иерархии должен позаботиться о механизме получения своего уникального идентификатора. Мы добавим виртуальный метод возвращающий идентификатор.
template <typename _Base>
struct visitable
{
using base_type = _Base;
};
// макрос для удобства
// добавляется в конкретный класс в иерархии
#define VISITABLE(Specific) static constexpr detail::hash_type hash__ = detail::get_hash<base_type, Specific>(); virtual detail::hash_type get_hash() const { return hash__; }struct entity : visitable<entity>
{
public:
VISITABLE(entity);
public:
virtual ~entity() {}
};
struct geometry : entity
{
public:
VISITABLE(geometry);
};
struct model : geometry
{
public:
VISITABLE(model);
};Генерация таблицы позднего связывания
В качестве контейнера для методов-преобразователей мы будем использовать стандартный ассоциативный контейнер map с уникальным идентификатором посещаемого типа в качестве ключа.
namespace detail {
template<typename _Visitor, typename _Base>
struct vtbl_traits
{
// базовый класс в иерархии.
// также содержит иформацию о константности итерируемых объектов
using base_type = _Base;
// тип посетителя
using visitor_type = _Visitor;
// тип указателя на метод-преобразователь посетителя
using function_type = void(visitor_type::*)(base_type &);
};
template<typename _Traits>
struct vtbl
{
using base_type = typename _Traits::base_type;
using function_type = typename _Traits::function_type;
using visitor_type = typename _Traits::visitor_type;
// добавить преобразователь для конкретного класса из иерархии
template<typename _Specific>
void put(function_type function)
{
vtbl_[get_hash<base_type, _Specific>()] = function;
}
// получить преобразователь для объекта на основе уникального идентификатора
function_type get(const hash_type & hash) const
{
auto it = vtbl_.find(hash);
return it != vtbl_.end() ? it->second : nullptr;
}
private:
std::map<hash_type, function_type> vtbl_;
};
} /* detail */Далле нам нужно сгенерировать таблицу для списка классов, которые мы будем посещать
namespace detail
{
// _Traits свойства таблицы
// _Specifics список классов для посещения
template<typename _Traits, typename... _Specifics>
struct vtbl_builder
{
// тип таблицы
using vtbl_type = vtbl<_Traits>;
// тип посетителя
using visitor_type = typename _Traits::visitor_type;
// тип базового класа
using base_type = typename _Traits::base_type;
template<typename... _Targets>
struct targets {};
vtbl_builder()
{
// начинаем заполнять таблицу
put_thunk(targets<_Specifics...>());
}
const auto * get_vtbl() const { return &vtbl_; }
private:
template<typename _Specific, typename... _Tail>
void put_thunk(targets<_Specific, _Tail...>)
{
// проверяем имеет ли посетитель метод для обработки
// объекта с типом из списка классов.
// добавляем константность если итерация идет по констанным объектам
using specific_type = constancy_t<base_type, _Specific>;
using is_put = typename has_visit_method<visitor_type, specific_type>::type;
put_thunk(targets<_Specific, _Tail...>(), is_put());
}
// у посетителя есть метод для обработки класса из списка
// добавляем преобразователь thunk и переходим к следующему типу
template<typename _Specific, typename... _Tail>
void put_thunk(targets<_Specific, _Tail...>, std::true_type)
{
vtbl_.template put<_Specific>(&visitor_type::template thunk<base_type, _Specific>);
put_thunk(targets<_Tail...>());
}
// у посетителя нет метода для обработки класса из списка
// ничего не добавляем, переходим к следующему типу
template<typename _Specific, typename... _Tail>
void put_thunk(targets<_Specific, _Tail...>, std::false_type)
{
put_thunk(targets<_Tail...>());
}
void put_thunk(targets<>) {}
private:
vtbl_type vtbl_;
};
// получаем указатель на таблицу для конкретного списка классов
template<typename _Traits, typename... _Specifics>
inline const auto * get_vtbl()
{
static vtbl_builder<_Traits, typename std::remove_cv<_Specifics>::type...> builder;
return builder.get_vtbl();
}
} /* detail */template<typename _From, typename _To>
using constancy_t = typename std::conditional<std::is_const<_From>::value,
const _To, _To>::type;template<typename _Visitor, typename _Specific>
struct has_visit_method
{
template<typename _Class, typename _Param>
static auto test(_Param * p) -> decltype(std::declval<_Class>().visit(*p),
std::true_type());
template<typename, typename>
static std::false_type test(...);
using type = decltype(test<_Visitor, _Specific>(nullptr));
static constexpr const bool value = std::is_same<std::true_type, type>::value;
};Нам осталось определить методы-преобразователи и описать механизм обработки объекта
template<typename _Base>
struct visitor_traits
{
// тип базового объекта в иерархии
using base_type = _Base;
};
// базовый класс для посетителя
template<typename _Visitor, typename _Traits>
struct visitor
{
using visitor_type = _Visitor;
using traits_type = _Traits;
// метод-преобразователь, указатель на специализацию хранится в таблице
template<typename _Base, typename _Specific>
void thunk(_Base & base)
{
using specific_type = detail::constancy_t<_Base, _Specific>;
static_cast<visitor_type*>(this)->visit(static_cast<specific_type&>(base));
}
// метод обработки объекта
template<typename _Base>
void operator()(_Base & base)
{
// проверяем, что обрабатываемый класс является потомком
// базового класса посещаемой иерархии.
static_assert(std::is_base_of<typename traits_type::base_type, _Base>::value, "");
// определяем свойства таблицы.
// тип _Base используется для получение информации
// о константности итерируемых объектов
using base_type = detail::constancy_t<_Base, typename traits_type::base_type>;
using traits_type = detail::vtbl_traits<visitor_type, base_type>;
// получаем указатель на таблицу с преобразователями.
// шаблонный метод get_vtbl определен в конкретном посетителе
const auto * vtbl = static_cast<visitor_type*>(this)->template get_vtbl<traits_type>();
// запрашиваем у обрабатываемго объекта уникальный идентификатор типа,
// если для этого типа зарегистрирован обрабочик, вызываем
if(auto thunk = vtbl->get(base.get_hash()))
(static_cast<visitor_type*>(this)->*thunk)(base);
}
};
// макрос для определения списка обрабатываемых объектов и инициализации таблицы
// добавляется в конкретный класс-посетитель
#define VISIT(...) template<typename _Traits> const auto * get_vtbl() const { return detail::get_vtbl<_Traits, __VA_ARGS__>(); }struct entity : visitable<entity>
{
public:
VISITABLE(entity);
public:
virtual ~entity() {}
};
struct geometry : entity
{
public:
VISITABLE(geometry);
};
struct model : geometry
{
public:
VISITABLE(model);
};
template<typename _Visitor>
using visitor_entities = visitor<_Visitor, visitor_traits<entity>>;
struct test_visitor : visitor_entities<test_visitor>
{
public:
VISIT(entity, geometry, model);
public:
void visit(const entity & obj)
{
// something
}
void visit(const geometry & obj)
{
// something
}
void visit(const model & obj)
{
// something
}
};
int main()
{
const entity & ref_entity = entity();
const entity & ref_model = model();
const entity & ref_geometry = geometry();
test_visitor test;
test(ref_entity);
test(ref_model);
test(ref_geometry);
}Производительность
Производительность на том же тесте с разными стандартными контейнерами для таблицы позднего связывания
| Pattern | Time(ms) |
|---|---|
| Cyclic visitor | 11.3 |
| Acyclic visitor(RTTI) | 220.4 |
| Acyclic visitor with map | 23.2 |
| Acyclic visitor with unordered_map | 44.5 |
| Acyclic visitor with sort vector | 31.1 |
» Код проекта можно найти на GitHub.
Буду рад комментариям и предложениям (можно по почте yegorov.alex@gmail.com)
Спасибо!
Комментарии (14)
Siemargl
20.10.2016 12:48Непонятно, зачем нужен dynamic_cast<geometry_visitor*>(&obj)) в типичной реализации, если obj.visit() — виртуальный? Соответственно, вызов виртуального метода быстрее, чем RTTI.
Ну и тогда проблемы, которая решается в статье, нет вообще.
PkXwmpgN
20.10.2016 12:48У obj нет метода visit. Если бы был, тогда нужна перегрузка для всех типов — это циклическая зависимость.
Про этот пример можно подробно прочитать в книге Andrei Alexandrescu. Modern c++ design.Siemargl
20.10.2016 14:46А, действительно. Но как пишет Александреску — это самый неудачный паттерн, потому редко используемый.
В вашем примере в итоге весь выигрыш из-за неудачной реализации dynamic_cast, который вы с помощью 3х листов исходного кода, с блекджеком и шаблонами реализуете руками с помощью map<>.
На мой взгляд, не нужно множить сущности, http://ideone.com/K0KQhk вот реализация проще, расширяемая и более эффективная, т.к switch() отлично оптимизируется компиляторомЗаголовок спойлера#include <iostream> #include <vector> #include <algorithm> using namespace std; enum e_type { ENTITY, GEOMETRY, MODEL }; struct visitor_base; struct visitable { virtual void accept(visitor_base & obj) = 0; }; struct visitor_base { virtual void visit(visitable &, enum e_type type) = 0; }; struct entity : visitable { void accept(visitor_base & obj) { obj.visit(*this, ENTITY); } }; struct geometry : entity { void accept(visitor_base & obj) { obj.visit(*this, GEOMETRY); } }; struct model : geometry { void accept(visitor_base & obj) { obj.visit(*this, MODEL); } }; struct test_visitor : visitor_base { void visit(visitable & obj, enum e_type type) { switch(type) { case ENTITY: { entity &ent = (entity&)obj; // its enough safe cout << "Visited ENTITY" << endl; break; } case GEOMETRY: { geometry &geo = (geometry&)obj; cout << "Visited GEOMETRY" << endl; break; } case MODEL: { model &mod = (model&)obj; cout << "Visited MODEL" << endl; break; } default: // TRAP ; } } }; struct modern_visitor : test_visitor // extension for new objects { // add new methods for new visitables, call parent otherwise }; int main() { entity E; geometry G; model M; vector<entity*> vec = {&E, &G, &M}; test_visitor visi; for_each(vec.begin(), vec.end(), [&](entity *i){ i->accept(visi); }); // your code goes here return 0; }PkXwmpgN
20.10.2016 15:23Но как пишет Александреску — это самый неудачный паттерн, потому редко используемый
Это немного упрошенный пример, у Александреску более аккуратный, обобщенный шаблон (в Loki, dynamic_cast вынемен отдельно), но суть там такая же. Не такой уж он и неудачный.
Намой взгляд, возможности по расшерению и поддержке этой модели, такие же как и у Cyclic Visitor. Только вместо виртуальной функции мне нужно добавить поле в enum, вы же понимаете, что если я добавлю поле в enum все существующие visitor'ы нужно будет перекомпелировать. Что если это библиотека и у меня нет возможности добавить поле в enum, также как у меня может не быть возможности добавить виктуальную функцию в случаи с Cyclic Visitor и перекомпилировать все?
Siemargl
20.10.2016 16:04На самом деле, перекомпилировать не нужно. Это же Си — обычные константы!
Просто новые Визиторы должны видеть дополненный enum.
Вот интересно скорость сравнить — мой вариант сравнить с табличкой производительности.
Ассемблерный код switch я уже посмотрел — 2 инструкции сравнения )
Eivind
20.10.2016 14:43Я это вижу как-то так:
Код#include <iostream> template <class T> struct visitor { virtual void visit( T& ) = 0; }; template <class T, class... Base> struct visitable : Base... { template <class Visitor> void accept( Visitor& obj ) { static_cast<visitor<T>&>( obj ).visit( static_cast<T&>( *this ) ); } }; struct entity : visitable<entity> { }; struct geometry : visitable<geometry, entity> { }; struct model : visitable<model, geometry> { }; struct test_visitor : visitor<entity>, visitor<geometry>, visitor<model> { void visit( entity& obj ) override { std::cout << "entity\n"; } void visit( geometry& obj ) override { std::cout << "geometry\n"; } void visit( model& obj ) override { std::cout << "model\n"; } }; int main() { entity e; geometry g; model m; test_visitor v; e.accept( v ); g.accept( v ); m.accept( v ); }Eivind
20.10.2016 14:54Хотя вру, через ссылки на базовые классы работать не будет.
Eivind
20.10.2016 16:26Вот, теперь должно быть правильно:
Заголовок спойлера#include <iostream> #include <vector> template <class T> struct visitor_base { template <class R> void visit_base( R& obj ) { static_cast<typename R::visitor_type&>( *this ).visit( obj ); } }; template <class T> struct visitor : T::parent_visitor_type { virtual void visit( T& ) = 0; }; template <class T, class Base = void> struct visitable : Base { using parent_visitor_type = typename Base::visitor_type; using visitor_type = visitor<T>; void accept( typename Base::visitor_base_type& obj ) override { obj.visit_base( static_cast<T&>( *this ) ); } }; template <class T> struct visitable<T, void> { using parent_visitor_type = visitor_base<T>; using visitor_base_type = visitor<T>; using visitor_type = visitor_base_type; virtual void accept( visitor_base_type& obj ) { obj.visit( static_cast<T&>( *this ) ); } }; struct entity : visitable<entity> { }; struct geometry : visitable<geometry, entity> { }; struct geometry2 : geometry { }; struct model : visitable<model, geometry2> { }; struct test_visitor : visitor<model> { void visit( entity& obj ) override { std::cout << "entity\n"; } void visit( geometry& obj ) override { std::cout << "geometry\n"; } void visit( model& obj ) override { std::cout << "model\n"; } }; int main() { entity e; geometry g; geometry2 g2; model m; test_visitor v; e.accept( v ); g.accept( v ); g2.accept( v ); m.accept( v ); std::vector<entity*> vec{&e, &g, &g2, &m}; for ( auto it : vec ) { it->accept( v ); } }PkXwmpgN
20.10.2016 16:57А если у меня иерархия не линейная?
Скрытый текстstruct entity {}; struct geometry : entity {}; struct model : entity {};Eivind
20.10.2016 18:46Впрочем, можно доработать методом из соседнего комментария
Заголовок спойлера#include <iostream> #include <type_traits> #include <vector> template <class T> struct id { static id id_; }; template <class T> id<T> id<T>::id_; template <class T> struct visitor_base { using common_type = T; virtual void visit_base( T& obj, void* ptr ) = 0; }; template <class T, class Base = void> struct visitable : Base { void accept( typename Base::visitor_type& obj ) override { obj.visit_base( static_cast<T&>( *this ), &id<T>::id_ ); } }; template <class T> struct visitable<T, void> { using visitor_type = visitor_base<T>; virtual void accept( visitor_type& obj ) { obj.visit_base( static_cast<T&>( *this ), &id<T>::id_ ); } }; template <class...> struct tag { }; template <class T> struct visitor_impl { virtual void visit( T& ) = 0; }; template <class... Ts> struct visitor : visitor_impl<Ts>..., std::common_type<Ts...>::type::visitor_type { using common_type = typename std::common_type<Ts...>::type::visitor_type::common_type; void visit_base( common_type& obj, void* ptr ) override { visit_( obj, ptr, tag<Ts...>() ); } private: void visit_( common_type& obj, void*, tag<> ) { } template <class Head, class... Tail> void visit_( common_type& obj, void* ptr, tag<Head, Tail...> ) { if ( ptr == &id<Head>::id_ ) { static_cast<visitor_impl<Head>&>( *this ).visit( static_cast<Head&>( obj ) ); } else { visit_( obj, ptr, tag<Tail...>() ); } } }; struct entity : visitable<entity> { }; struct geometry : visitable<geometry, entity> { }; struct model : visitable<model, entity> { }; struct test_visitor : visitor<entity, geometry, model> { void visit( entity& ) override { std::cout << "entity\n"; } void visit( geometry& ) override { std::cout << "geometry\n"; } void visit( model& ) override { std::cout << "model\n"; } }; int main() { entity e; geometry g; model m; test_visitor v; e.accept( v ); g.accept( v ); m.accept( v ); std::cout << "\n"; std::vector<entity*> vec{&e, &g, &m}; for ( auto it : vec ) { it->accept( v ); } }
antoshkka
20.10.2016 19:10Аналогичный CTTI есть в Boost http://boostorg.github.io/type_index/boost/typeindex/ctti_type_index.html
Только вот ему пока не хватает `constexpr` hash функции.
Shamov
А мне как раз нужна constexpr-функция для генерация уникального hash'а для типа. Собирался сам её делать. Всю неделю откладывал эту задачу, делая пока то, что можно сделать без неё. А говорят, что бога нет. Может его и нет, но конкретно мне он походу помогает…