Intro
Довелось мне столкнуться со странной структурой данных (похожей на JSON). Она представляет собой гетерогенное дерево, каждый узел которого содержит некоторые данные и множество дочерних узлов. Особенность заключается в том, что это множество может быть как простым контейнером (std::vector) так и ассоциативным (std::map). Получается, если узел хранит дочерние узлы в мапе - это JSON Object, а если вектор - JSON Array.
В реализации этой структуры данных меня смущала сложная иерархия классов и то, что класс, который должен храниться в этом контейнере, обязательно должен реализовывать некий интерфейс.
В этой статье я представлю альтернативу описанному выше.
Реализация
Узел будет хранить данные как std::variant от допустимых данных.
class node
{
public:
using value_type = std::variant<int, double...>
value_type payload;
};
Будем использовать данный класс для узлов не имеющих дочерних узлов.
class node_object : public node
{
using children_type = std::variant<node_object, node_array, node>;
std::map<children_type> children;
};
class node_array : public node
{
using children_type = std::variant<node_object, node_array, node>;
std::vector<children_type> children;
};
В реализации node_object и node_array возникают проблемы с рекурсивным определением типов (один содержит другой). Конечно, можно использовать указатели, но это не наш путь. Для объявления зависимых типов будем использовать шаблон:
template <typename Settings>
class node_object { using children_type = typename Settings::children_type; ... };
template <typename Settings>
class node_array { using children_type = typename Settings::children_type; ... };
Чтобы специализировать типы узлов в одном типе - специализируем узлы этим же типом:
template < // Каждый аргумент шаблона - шаблонный тип с одним аргументом.
template <typename> typename Map,
template <typename> typename Array,
template <typename> typename Variant
>
struct __node_settings
{
// Нам не нужно специализировать тип структуры внутри самой себя.
using map_type = Map < __node_settings>;
using array_type = Array < __node_settings>;
using children_type = Variant< __node_settings>;
};
Осталось вывести children_type, который должен быть std::variant<node, node_object, node_array>. node нам известен изначально, а два оставшихся типов определены в __node_settings. Если шаблонизировать последний тип аналогично типам узлов, задача легко решается:
template <typename Settings>
using __node_variant =
std::variant<
typename Settings::map_type,
typename Settings::array_type,
node
>;
Если переименовать шаблонные типы узлов, в результате получаем:
using __settings_helper = __node_settings<__node_map, __node_array, __node_variant>;
using node_map = __settings_helper::map_type;
using node_array = __settings_helper::map_array;
Таким образом каждый узел может хранить по значению любой другой тип узла (включая себя самого).
Пример использования
В случае использования приведенных выше классов, получение узла выглядит достаточно громоздко и нужно знать тип каждого узла. Для определения типа std::variant имеет метод index() (возвращает индекс хранимого типа в порядке определения шаблона варианта) и std::get_if<> (возвращает тип std::add_pointer_t<>).
Если это мешает, всегда можно обернуть это в API.
node_map m;
m.children["primitive"] = node{};
m.children["array"] = node_array{};
std::get<node_array>(m.children["array"])
.children.push_back(node{});
std::get<node_array>(m.children["array"])
.children.push_back(node_map{});
std::get<node_map>(std::get<node_array>(m.children["array"])
.children[1]).children["primitive"] = node{};
Как это работает
Стандарт гласит:
3 Unless a member of a class template or a member template has been explicitly instantiated or explicitly specialized, the specialization of the member is implicitly instantiated when the specialization is referenced in a context that requires the member definition to exist or if the existence of the definition of the member affects the semantics of the program; in particular, the initialization (and any associated side effects) of a static data member does not occur unless the static data member is itself used in a way that requires the definition of the static data member to exist. 4 Unless a function template specialization has been explicitly instantiated or explicitly specialized, the function template specialization is implicitly instantiated when the specialization is referenced in a context that requires a function definition to exist or if the existence of the definition affects the semantics of the program. A function whose declaration was instantiated from a friend function definition is implicitly instantiated when it is referenced in a context that requires a function definition to exist or if the existence of the definition affects the semantics of the program. Unless a call is to a function template explicit specialization or to a member function of an explicitly specialized class template, a default argument for a function template or a member function of a class template is implicitly instantiated when the function is called in a context that requires the value of the default argument. 5 [Example:
template<class T> struct Z { void f(); void g(); }; void h() { Z<int> a; // instantiation of class Z<int> required Z<char>* p; // instantiation of class Z<char> not required Z<double>* q; // instantiation of class Z<double> not required a.f(); // instantiation of Z<int>::f() required p->g(); // instantiation of class Z<char> required, and // instantiation of Z<char>::g() required }Nothing in this example requires class Z
, Z ::g(), or Z ::f() to be implicitly instantiated. —end example]
Другими словами, внутри объявления узла мы знаем тип самого узла и нам нужен только тип другого, который содержится в параметре шаблона. Каждый узел использует только часть типов определенных в настройках (получаемых через шаблон), что позволяет нам специализировать все типы, а в момент использования, компилятору остается лишь определить тип.
Схема для наглядности:
Код примера можно найти по ссылке.
Эпилог
В общем, данную технику можно использовать в любых ситуациях, когда нужно получить тип, зависимый от текущего типа. Это могут быть шаблонные интерфейсы, структуры данных с зависимыми типами, любые случаи когда хочется избежать виртуальных вызовов (который достаточно дорог относительно прямого вызова или вызова по указателю).
С другой стороны, такой код дольше компилируется (а если переборщить с шаблонами, компилятор будет сжирать огромное количество памяти). Это можно как-то оптимизировать, но это дополнительные усилия. В большинстве случаев, такая реализация - попытка обойти стандартные механизмы языка (наследование и виртуальные методы), что усложняет понимание программы (а программы читают намного чаще, нежели пишут их). Я не стану рекомендовать эту технику повсеместно, но иногда она бывает полезной.