В этой статье мы рассмотрим один из вариантов реализации поведенческого шаблона проектирования Acyclic Visitor без ипользования RTTI.
![](https://habrastorage.org/files/5c9/2bd/02e/5c92bd02e999479485082b802abe93bd.jpeg)
Основным назначением поведенческого шаблона проектирования 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'а для типа. Собирался сам её делать. Всю неделю откладывал эту задачу, делая пока то, что можно сделать без неё. А говорят, что бога нет. Может его и нет, но конкретно мне он походу помогает…