Паттерны Variant и Visitor. Тонкости реализации Abstract & IntroductionНаписание данной заметки было мотивировано недавней темой
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. Там же мной была приведена простая реализация аналога boost::variant
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/).
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/). Так, специализация
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
Исходники с проектом прилагаются..
