Russian Qt Forum

Программирование => С/C++ => Тема начата: m_ax от Февраль 23, 2015, 12:55



Название: Паттерны Variant и Visitor. Тонкости реализации
Отправлено: m_ax от Февраль 23, 2015, 12:55
Паттерны Variant и Visitor. Тонкости реализации



Abstract & Introduction
Написание данной заметки было мотивировано недавней темой http://www.prog.org.ru/topic_28407_0.html (http://www.prog.org.ru/topic_28407_0.html) от товарища navrovsky в которой он предложил свою реализацию Variant - аналога boost::any http://www.boost.org/doc/libs/1_57_0/doc/html/any.html (http://www.boost.org/doc/libs/1_57_0/doc/html/any.html). Там же  мной была приведена простая реализация аналога boost::variant http://www.boost.org/doc/libs/1_51_0/doc/html/variant.html (http://www.boost.org/doc/libs/1_51_0/doc/html/variant.html). В последствии, русло дискуссии ушло в сторону обсуждения механизмов визитирования коллекции из объектов класса variant и, в частности, патерна Visitor, реализующий  этот самый механизм.  Однако, у меня осталось стойкое ощущение, что один из участников дискуссии (не будем показывать пальцем), будучи адептом философии: "лучше банальный if-else-switch, понятный и доступный каждому, чем заумные паттерны проектирования, boostы и иже с ними" так и  не осознал те преимущества, что  даёт связка boost::variant  и boost::static_visitor в задачах связанных с операциями над коллекциями из гетерогенных объектов (в данном случае variant'ов). Это ещё одна из причин, что заставила меня  написать эту заметку. Ну и наконец, во многом благодаря выше обозначенной теме и процессу обсуждения в ней, а также раскуриванию исходников boost'а, с мыслью "истина где то рядом", пришло осознание как же на самом деле это реализуется в boost'е (как работает boost::static_visitor с boost::variant: это, на самом деле, не так тривиально). И об этом пойдёт речь дальше.

И так, здесь я постараюсь показать на простом примере, как изнутри устроен механизм визитирования в boost::variant + boost::static_visitor.  Сразу оговорюсь, речь будет идти именно о бустовской реализации: обычный классический вариант паттерна Visitor не столь интересен с академической точки зрения - там всё прозрачно и понятно (почитать о нём можно, например здесь http://cpp-reference.ru/patterns/behavioral-patterns/visitor/ (http://cpp-reference.ru/patterns/behavioral-patterns/visitor/)).

Theoretical background
Начнём с того, что наша реализация variant'а полностью завязана на меташаблонном программировании.
Вот так выглядит объявление  класса variant
Код
C++ (Qt)
template <class ...Args>
class variant
{
...
};
 

Это обычный variadic template, доступный со стандарта c++11. Другими словами при объявлении variant'а мы должны передать ему (в качестве параметров шаблонов) список всех типов с которым он может работать:
Код
C++ (Qt)
typedef variant<int, float, long, double, short, std::string> variant_t;
 
 
Для того, чтоб продвинуться дальше, нам необходимо реализовать несколько вспомогательных "функций", которые могли бы извлекать полезную для нас информацию из списка параметров шаблона <class...Args>.  Одна из таких функций - это подсчёт числа всех типов: num_args. Ниже пример её возможной реализации:
Код
C++ (Qt)
template <class T, class ...Args>
struct num_args
{
   static constexpr int value = num_args<Args...>::value + 1;
};
 
template <class T>
struct num_args<T>
{
   static constexpr int value = 1;
};
 

Вообще, когда мы имеем дело с меташаблонным программированием, это практически всегда связано со специализацией шаблонов (почитать об этом можно, например, здесь http://habrahabr.ru/post/54762/ (http://habrahabr.ru/post/54762/)). Так, специализация
Код
C++ (Qt)
template <class T>
struct num_args<T>
{
   static constexpr int value = 1;
};
 
останавливает рекурсию.

Далее, нам бы хотелось иметь возможность приписать каждому типу (из списка) свой уникальный id.
Один из вариантов такого индексирования напрашивается сам-собой: id каждого типа в списке соответствует его порядковому  номеру (начиная с нуля), т.е.
Код
C++ (Qt)
std::cout << type_id<double,        double, int, short>::value // вернёт 0
 
std::cout << type_id<int,           double, int, short>::value // вернёт 1
 
std::cout << type_id<short,         double, int, short>::value // вернёт 2
 
std::cout << type_id<std::string,   double, int, short>::value // вернёт bad_id, поскольку в списке нет класса std::string
 
Реализовать это можно так:
Код
C++ (Qt)
template <class T, class Arg1, class ...Args>
struct type_id_helper
{
   static constexpr int value = (std::is_same<T, Arg1>::value) ? num_args<Arg1, Args...>::value : type_id_helper<T, Args...>::value;
};
 
template <class T, class Arg>
struct type_id_helper<T, Arg>
{
   static constexpr int value = (std::is_same<T, Arg>::value) ? 1 : -1;
};
 
// type_id_helper::value возвращает индексы для типов в обратном порядке, а нам хочется чтобы они начинались с нуля:
 
template <class T, class ...Args>
struct type_id
{
   static constexpr int bad_id = -1;
 
   static constexpr int value = (type_id_helper<T, Args...>::value > -1) ? num_args<Args...>::value - type_id_helper<T, Args...>::value : bad_id;
};
 

На самом деле здесь ничего сложного нет, нужно только привыкнуть к особенностям меташаблонной магии..
Теперь, когда у нас есть возможность ставить каждому типу из списка свой уникальный id, можно продолжить реализовывать variant:
Код
C++ (Qt)
template <class ...Args>
class variant
{
private:
struct holder_base
   {
       holder_base(int _id) : id(_id) {}
       virtual ~holder_base() {}
       int id;
   };
 
   template <class T>
   struct holder : holder_base
   {
       holder(const T & _data, int _id) : holder_base(_id), data(_data) {}
       T data;
   };
 
   std::shared_ptr<holder_base> _holder;
};
 
 
Помимо самих данных _holder знает текущий id типа, объектом которого он владеет.
Например, одна из таких функций где это используется: проверка типа:
Код
C++ (Qt)
template <class T>
   bool is_type() const
   {
       return (_holder) ? detail::type_id<T, Args...>::value == _holder->id : false;
   }
 
   
Я не буду здесь останавливаться на описании всех функций, что входят в variant - это не так принципиально (полный код приаттачен к теме).
И на этом можно было бы и закончить, но мы хотим иметь возможность элегантного визитирования, так как это реализовано в boost'е..

Но для этого нам необходимо получать тип параметра шаблона по его id. Тип получить можно так (упрощённая версия):
Код
C++ (Qt)
template <size_t N, class T, class ...Args>
struct type_for_id : public type_for_id<N-1,  Args...>
{};
 
template <class T, class...Args>
struct type_for_id<0, T, Args...>
{
   typedef T type;
};
 
   
Здесь мы опять имеем дело со специализацией type_for_id<0, T, Args...> .
Теперь мы можем делать так:
Код
C++ (Qt)
typename type_for_id<0,  double, int, std::string>::type d = 3.1415; // double
typename type_for_id<1,  double, int, std::string>::type i = 10; // int
typename type_for_id<2,  double, int, std::string>::type str = "hello-hello";
 

Последний штрих: нам осталось написать приватный метод apply_visitor:
Код
C++ (Qt)
template <class ...Args>
class variant
{
...
private:
   template <class Visitor>
   typename Visitor::result_type apply_visitor(Visitor visitor) throw (std::runtime_error)
   {
       if (!_holder)
           throw std::runtime_error("variant::apply_visitor: variant is empty");
 
       #define APPLY_VISITOR(n) return visitor(get_p<typename detail::type_for_id<n, Args...>::type>());
 
       STATIC_SWITCH(_holder->id, APPLY_VISITOR);
 
       return typename Visitor::result_type();
   }
};
 
Здесь стоит обратить внимание на строчку:  
Код
C++ (Qt)
#define APPLY_VISITOR(n) return visitor(get_p<typename detail::type_for_id<n, Args...>::type>());
 
Это вспомогательный макрос который подаётся в макрос STATIC_SWITCH  
Код
C++ (Qt)
STATIC_SWITCH(_holder->id, APPLY_VISITOR);
 
который в итоге разворачивается в следующее:
Код
C++ (Qt)
switch (_holder->id)
{
case 0: return visitor(get_p<typename detail::type_for_id<0, Args...>::type>()); break;
case 1: return visitor(get_p<typename detail::type_for_id<1, Args...>::type>()); break;
case 2: return visitor(get_p<typename detail::type_for_id<2, Args...>::type>()); break;
case 3: return visitor(get_p<typename detail::type_for_id<3, Args...>::type>()); break;
....
default: break;
}
 
Максимальное значение для макроса STATIC_SWITCH = 256. Это означает, что visitor будет работать с variant'ами у которых число шаблонных параметров не превышает 256.  
В бусте использован аналогичный подход..

Осталось написать внешнюю (дружественную) функцию apply_visitor:
Код
C++ (Qt)
template <class R>
struct static_visitor
{
   typedef R result_type;
};
 
 
template <class Visitor, class Visitable>
typename Visitor::result_type apply_visitor(Visitor visitor, Visitable & v)
{
   return v.apply_visitor(visitor);
}
 

Всё, мы закончили) Теперь чтоб создать своего визитёра, нам нужно отнаследоваться от static_visitor и определить необходимые операторы:
Код
C++ (Qt)
struct my_visitor : public static_visitor<int>
{
   int operator()(int val) const
   {
       std::cout << val << std::endl;
       return val;
   }
 
   int operator()(const double & val) const
   {
       std::cout << val << std::endl;
       return val;
   }
};
 
 
typedef variant<int, double> variant_t;
 
...
 
variant_t v1 = 10;
variant_t v2 = 3.14;
 
apply_visitor(my_visitor(), v1);
apply_visitor(my_visitor(), v2);
 
   
Мы добились полной аналогии с boost аналогом.

Ещё раз отмечу, что паттерн static_visitor, позволяет легко написать тот самый вожделенный variant_cast:
Код
C++ (Qt)
   variant_t v1 = 3.14;  // double
   variant_t v2 = 10;  // int
   variant_t v3 = 23234L; // long
 
   double dval = variant_cast<double>(v1);
   int ival = variant_cast<int>(v3);
   ...
 
И это несомненно лучше бесконечной if-else простыни.  

Conclusions
В заключении отмечу, что  концепт связки variant + static_visitor основывается на возможности (в компил тайм) получать id типа и сопряжённой функции: вытаскивать тип по id.
Примечательно, что всё это можно реализовать в компил тайме).

По сути, в функции apply_visitor используется банальный switch, но его удаётся элегантно скрыть и он, в общем то, не вызывает никаких неприятностей.      

Несомненным плюсом этого паттерна static_visitor - является полное разделение данных от операций над ними (данные ничего не знают о визитёре, а визитёр может быть применён к вариантам с различными списками типов).
Более того, в отличии от классической реализации, здесь не задействован полиморфизм, а это тоже плюс к производительности.

Ну и наконец, не могу не сказать, что не раз говорил:  boost - это просто кладесь архитектурных решений и их реализаций.
Не бойтесь его, пользуйтесь им)  Вы только выиграете)    

PS
Исходники с проектом прилагаются..
    


Название: Re: Паттерны Variant и Visitor. Тонкости реализации
Отправлено: Igors от Февраль 23, 2015, 16:53
Ну "адепт" пока "ни асилил" :) Не, ну чижело, правда. Ладно, не все сразу. Пока приведу пример "от жизни" (подобное мы в прошлом обсуждали).

Есть у нас простейшие структуры для которых определены операторы арифметики  + - * /
Код
C++ (Qt)
struct Point3d { double x, y, z; }
struct Point3f { float x, y, z; }
struct Color3u { uchar r, g, b; }
struct Color4u { uchar a, r, g, b; }
Пусть контейнеры этих структур принадлежат классу Model. Действуем прямолинейно
Код
C++ (Qt)
struct Model {
vector <Point3d> mCoord;
vector <Point3f> mUV;
vector <Color3u> mColor;
...
};
Однако выяснятся что Model может иметь какие-то данные или нет. Напр mUV и/или mColor могут отсутствовать. Также mCoord хотя и есть всегда но может быть vector <Point3d> или vector <Point3f>. Тоже и для mColor (контейнер Point3f или Color3u или Color4u). Поэтому отделаться указателями на конкретные контейнеры не удается. Напрашивается создать универсальный класс Container
Код
C++ (Qt)
struct Model {
Container * mCoord;
vector <Container *>  mAttribute;
};
 
struct Container {
virtual size_t size( void ) const = 0;
...
}
 
template <class T>
struct TypedContainer : public Container {
virtual size_t size( void ) const { return mData.size(); }
 
// data
 vector <T> mData;
};
 
Теперь с Model все прекрасно - она может хранить данные любых форматов в любом кол-ве, напр
Код
C++ (Qt)
if (data_double)
model.mCoord = new TypedContainer <Point3d>;
else  
model.mCoord = new TypedContainer <Point3f>;
if (hasUV)
model.mAttribute.push_back(new TypedContainer <Point3f>);
 
Но как организовать доступ к элементам "обобщенного" контейнера (грубо говоря оператор [])? Напр я хочу сделать метод общий для всех
Код
C++ (Qt)
template <class T>
void Model::Interpolate( vector <T> & vec, size_t index1, size_t index2 )
{
vec.push_back((vec[index1] + vec[index2]) / 2);
}
 
Но беда в том что нужного "T" я не имею, а значит и позвать этот метод из класса Model мне нечем
Код
C++ (Qt)
void Model::Interpolate( Container & vec, size_t index1, size_t index2 )
{
 ?????
}
 
Остается мучительно "приводить" Container к TypedContainer, что явно плохо



Название: Re: Паттерны Variant и Visitor. Тонкости реализации
Отправлено: m_ax от Февраль 23, 2015, 23:30
Цитировать
Напрашивается создать универсальный класс Container
Напрашивается создать (если в будущем не всплывут какие-либо шокирующие умалчиваемые сейчас условия) контейнер, по сути своей аналогичный варианту (не путать с контейнером вариантов или вариантом от различных контейнеров)
Т.е. примерно такое:
Код
C++ (Qt)
template <class ...Args>
class variant_container
{
...
};
 
...
 
typedef variant_container<Point3d, Point3f, Color3u, Color4u> my_variant_container_type;
 
И уже его использовать в Model'и..
Если понятно как реализован variant+static_visitor, то с реализацией vector_variant и соответствующего визитёра проблем не должно возникнуть..

Но это, всего лишь один из возможных путей.. Может там элегантнее всё иначе решается..


Название: Re: Паттерны Variant и Visitor. Тонкости реализации
Отправлено: Igors от Февраль 24, 2015, 06:45
Код
C++ (Qt)
template <class ...Args>
class variant_container
{
...
};
 
...
 
typedef variant_container<Point3d, Point3f, Color3u, Color4u> my_variant_container_type;
 
И уже его использовать в Model'и..
Если понятно как реализован variant+static_visitor, то с реализацией vector_variant и соответствующего визитёра проблем не должно возникнуть..
Ну пока не очень понятно. Мне нужен "вариант контейнера" (а не "вариант элемента"), поэтому наверно
Код:
typedef variant_container<vector<Point3d>, vector<Point3f>, vector<Color3u>, vector<Color4u> > my_variant_container_type;
Хорошо, имею экземпляр my_variant_container_type, теперь мне надо как-то соскочить на конкретный тип что в нем сидит. Есть много действий/методов которые совершенно одинаковы для всех контейнеров (см пример Interpolate выше). И что, для каждого надо заводить класс визитора и.т.п.? Хмм... это можно пережить, но как-то не очень. Или я неправильно понял?


Название: Re: Паттерны Variant и Visitor. Тонкости реализации
Отправлено: m_ax от Февраль 24, 2015, 09:40
Цитировать
Ну пока не очень понятно. Мне нужен "вариант контейнера" (а не "вариант элемента"), поэтому наверно
Нет, не вариант контейнеров, а контейнер, который совмещает в своём функционале черты обычного контейнера и variant'а:
Код
C++ (Qt)
template <class ...Args>
class variant_container
{
public:
   size_t size() const { ... }
   template <class T>
   const T& operator[](size_t i) const { ... }
...
private:
struct holder_base
   {
       holder_base(int _id) : id(_id) {}
       virtual ~holder_base() {}
       int id;
   };
 
   template <class T>
   struct holder : holder_base
   {
       holder(const std::vector<T> & _data, int _id) : holder_base(_id), data(_data) {}
       std::vector<T> data;
   };
 
   std::shared_ptr<holder_base> _holder;
};
 
Этот контейнер содержит в себе вектор для какого либо типа из списка:
Код
C++ (Qt)
typedef variant_container<Point3d, Point3f, Color3u, Color4u> my_variant_container_type;
 
Реализуется это аналогично variant'у..


Или, в принципе, можно и просто variant векторов.
Цитировать
Есть много действий/методов которые совершенно одинаковы для всех контейнеров (см пример Interpolate выше). И что, для каждого надо заводить класс визитора и.т.п.? Хмм... это можно пережить, но как-то не очень. Или я неправильно понял?
Наверное не правильно.. Для этого достаточно написать только один метод:
Код
C++ (Qt)
struct interpolate : public static_visitor<void>
{
   interpolate(size_t _index1, size_t _index2) : index1(_index1), index2(_index) {}
 
   template <class Container>
   void operator()(Container & vec) const
   {
        vec.push_back((vec[index1] + vec[index2]) / 2);)
   }
 
private:
  size_t index1, index2;
};
 
typedef variant_container<vector<Point3d>, vector<Point3f>, vector<Color3u>, vector<Color4u> > my_variant_container_type;
 


Название: Re: Паттерны Variant и Visitor. Тонкости реализации
Отправлено: Igors от Февраль 24, 2015, 10:22
Наверное не правильно.. Для этого достаточно написать только один метод:
Код
C++ (Qt)
struct interpolate : public static_visitor<void>
{
   interpolate(size_t _index1, size_t _index2) : index1(_index1), index2(_index) {}
 
   template <class Container>
   void operator()(Container & vec) const
   {
        vec.push_back((vec[index1] + vec[index2]) / 2);)
   }
 
private:
  size_t index1, index2;
};
 
typedef variant_container<vector<Point3d>, vector<Point3f>, vector<Color3u>, vector<Color4u> > my_variant_container_type;
 
Ну так елы-палы, у меня таких ф-ций много десятков (если не сотни), что же, каждую оборачивать в визитора?  :'( :'(

И еще, а как если их 2?, напр
Код
C++ (Qt)
void DoCopy( const my_variant_container_type & src, my_variant_container_type & dst )
{
for (size_t i = 0; i < dst.size(); ++i)
 dst[i] = src[i];
}
 
Эл-ты src и dst могут быть одного типа или нет, но в любом случае могут присваиваться друг другу.


Название: Re: Паттерны Variant и Visitor. Тонкости реализации
Отправлено: m_ax от Февраль 24, 2015, 10:48
Цитировать
Ну так елы-палы, у меня таких ф-ций много десятков (если не сотни), что же, каждую оборачивать в визитора?
Ну тогда первый вариант: пишите контейнер, который совмещает в своём функционале черты обычного контейнера и variant'а

Цитировать
Эл-ты src и dst могут быть одного типа или нет, но в любом случае могут присваиваться друг другу.
В boost'е и для двух элементов есть реализация визитёра.. Вы документацию читаете, вообще?)