Особенности реализации кортежей на c++

Под впечатлением от прочтения замечательной статьи о Variadic Templates от уважаемого FlexFerrum решил поупражняться в метапрограммировании и написать свою реализацию структуры данных, называемой Tuple (Кортеж), с использованием шаблонов с переменным количеством аргументов. Для тех кто не знаком, кортеж — структура данных, которая хранит в себе одновременно данные различных типов. У нас же в данном конкретном случае это будет шаблонный класс, который хранит в себе данные тех типов, которые были переданы ему как шаблонные параметры (с учетом порядка).

Предполагается что читатель уже ознакомлен с вышеуказанной статьей, при описании процесса разработки я буду отталкиваться от нее.

Хранение данных

Первой стоящей перед нами проблемой является принцип хранения данных. В статье FlexFerrum’a была предложена реализация класса, который по сути своей является суперпозицией функций, переданных как шаблонные параметры. Для сохранения указателей на функции была предложена модель множественного наследования от класса DataHolder, который хранит в себе то, чем его параметризовали:

template<typename T> struct DataHolder {     T m_data; };   template<typename Op, typename … F> class Composer : public DataHolder<F> … {     // ... }; 

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

template <class T, class ... REST> class Tuple : public Tuple<REST ...> { public: 		Tuple(); 		Tuple(const T & _p1, const REST & ... _rest);  		/// returns elements count 		inline constexpr static unsigned int Count() { return mIndex + 1; }  		// ... protected: private: 		T mMember = T(); 		static constexpr unsigned int mIndex = TupleSuper::Count(); }  // терминирующая специализация template <class T> class Tuple { public: 		Tuple(); 		Tuple(const T & _p1);  		/// returns elements count 		inline constexpr static unsigned int Count() { return mIndex + 1; }  		// ... protected: private: 		T mMember = T(); 		static constexpr unsigned int mIndex = 0; } 

Реализация конструторов должна быть очевидна: инциализируем поле текущего класса и вызываем коструктор базового класса с оставшимися аргументами.

Set/Get методы

Следующий шаг — реализация сеттеров и геттеров для полей данных класса. Методы, которые получают и записывают сразу все поля просты в реализации и здесь не приводятся. Куда более интересной является ситуация, скажем, с геттером, принимающим числовой индекс поля, как шаблонный аргумент. Для его реализации нам понадобится некий вспомогательный класс, который позволит нам проиндексировать типы Tuple в нашей цепочке наследования следующим образом: тип с индексом 0 самый нижний потомок, с индексом 1 — его непосредственный предок, и т.д. по индукции. При передаче слишком большого числа мы должны получать ошибку на этапе компиляции. Сделать такой класс можно, определив терминирующую специализацию для индекса 0, а более общее определение для индекса N через конкретизацию индексом N — 1. Сам тип tuple мы будем определять как using (или typedef) в нутри нашего «индексатора». Назовем наш класс незамысловато TupleIndexer.

template <class T, class ... REST> class Tuple;  template <unsigned int INDEX, class T, class ... REST> class TupleIndexer { public: 		using TupleIndexerDeeper = TupleIndexer<INDEX - 1, REST ...>;  		using TupleType = typename TupleIndexerDeeper::TupleType; };  template <class T, class ... REST> class TupleIndexer<0, T, REST ...> { public: 		using TupleType = Tuple<T, REST ...>; }; 

Дальше мы воспользуемся тем, что мы не использовали множественное наследование, а выстроили цепочку классов. Будем приводить текущий класс Tuple к Tuple, вычисленному по индексу через static_cast. Для вычисления возращаемого значения из метода Get заведем в нашем Tuple синоним для самого левостоящего поля и будем доставать его из Tuple, полученного по индексу.

template <class T, class ... REST> class Tuple : public Tuple<REST ...> { public: 		using LeftMemberType = T;  		template <unsigned int INDEX> 		using MemberTypeIndexed = typename tuple::TupleIndexer<INDEX, T, REST ...>::TupleType::LeftMemberType; 		template <unsigned int INDEX> 		using TupleTypeIndexed = typename tuple::TupleIndexer<INDEX, T, REST ...>::TupleType;  		template <unsigned int INDEX> 		inline const MemberTypeIndexed<INDEX> & Get() const;  		// ... };  template <class T, class ... REST> template <unsigned int INDEX> inline const typename Tuple<T, REST ...>::template MemberTypeIndexed<INDEX> & Tuple<T, REST ...>::Get() const { 		return static_cast<const TupleTypeIndexed<INDEX> *>(this)->mMember; } 

Реализация сеттера не приведена, т.к. она идентична геттеру. К сожалению полноценная итерация по индексу в этом кортеже невозможна (а нужна ли?), т.к. нам нужно знать тип возвращаемого значения.

SubTuple

Следущий этап который хотелось бы описать — добавление возможности создания кортежа из некоторой комбинации полей другого. Самый простой вариант — шаблонный метод, принимающий переменное число индексов, по которым будут взяты поля и переданы в конструктор нового Tuple.

template <class T, class ... REST> class Tuple : public Tuple<REST ...> { public: 		using LeftMemberType = T; 		template <unsigned int INDEX> 		using MemberTypeIndexed = typename tuple::TupleIndexer<INDEX, T, REST ...>::TupleType::LeftMemberType;  		template <unsigned int ... INDICES> 		using SubTupleTypeIndexed = Tuple<MemberTypeIndexed<INDICES> ...>;  		template <unsigned int ... INDICES> 		inline SubTupleTypeIndexed<INDICES ...> MakeTuple() const 		{ 				return Tuple<MemberTypeIndexed<INDICES> ...>(Get<INDICES>() ...); 		}  		// ... }; 

Но этого нам не достаточно. Реализуем шаблонный метод, принимающий диапазон индексов и возращающий Tuple конкретизиованный типами с индексами из заданного диапазона. Т.е:

template <unsigned int A, unsigned int B> inline SubTupleTypeRanged<A, B> MakeSubTuple() const; 

Как вы могли догадаться нам нужен еще один вспомогательный класс, который позволит нам вычислить тип возвращаемого Tuple по диапазону, а не по индексу. Для этого воспользуемся приемом, похожим на способ из статьи FlexFerrum’a. Создадим класс, принимающий диапазон в качестве шаблонных параметров (A и B) и хранящий в себе синоним некого класса, конкретизированного индексами от A до B. Тот класс в свою очередь будет вычислять для нас тип Tuple. Имена для наших классов выберем Range и Indices соотвественно.

Реализация класса Indices, хранящего в себе соответсвующий тип шаблона Tuple:

template <class T, class ... REST> class Tuple;  template <unsigned int ... INDICES> class Indices { public: 		template <class T, class ... REST> 		using SubTupleType = Tuple<typename Tuple<T, REST ...>::template MemberTypeIndexed<INDICES> ...>;  protected: private: }; 

Реализация собственно диапазона:

template <unsigned int A, unsigned int B> class Range { public: 		using RangeLesser = Range<A, B + (A < B ? - 1 : 1)>; 		template <unsigned int ... INDICES> 		using IndicesExtendable = typename RangeLesser::template IndicesExtendable<B, INDICES ...>; 		using Indices = IndicesExtendable<>;  protected: private: };  template <unsigned int INDEX> class Range<INDEX, INDEX> { public: 		template <unsigned int ... INDICES> 		using IndicesExtendable = tuple::Indices<INDEX, INDICES ...>; 		using Indices = IndicesExtendable<>;  protected: private: }; 

В данном случае терминиующей веткой является диапазон с равным началом и концом (длина = 0). Диапазон с длиной N определяет в себе шаблон IndicesExtendable через шаблон IndicesExtendable из диапазона с длинной N — 1. Говоря более простым языком, мы постепенно с шагом в единицу стягиваем диапазон в точку. Если наблюдать за процессом вывода типов в обратном направлении, то на каждой итерации расширения диапазона определяется новый синоним шаблона IndicesExtendable добавлением нового шаблонного параметра — еще одного индекса к синониму шаблона IndicesExtendable из предыдущей итерации. Таким образом Range<1, 4> будет содержать в себе Indices = Indices<1, 2, 3, 4>. Данный класс диапазона работает и для обратного случая — Range<4, 1>. Это даст тип Indices<4, 3, 2, 1>.

Еще одна деталь связана с тем, что в методе MakeSubTuple нам нужно каким то образом выполнить вызов конструкотра с правильными полями в качестве аргументов. Сделать это можно добавив еще один метод MakeTuple, принимающий в качестве параметра Indices. Этакий еще один способ конкретизировать шаблонный метод.

template <unsigned int ... INDICES> inline SubTupleTypeIndexed<INDICES ...> MakeTuple(const Indices<INDICES ...> &) const; 

Реализация этого метода аналогична первому. В теле метода параметр просто игнорируется. Теперь мы можем делать вызов без передачи шаблонных параметров:

t.MakeTuple(Indices<1, 2, 3>) // то же, что и t.MakeTuple<1, 2, 3>() 

Теперь у нас все готово и мы можем перейти непосредственно к реализации метода MakeSubTuple. Просто достаем нужный нам Indices из Range, инстанцируем его на стеке или как статическую переменную и передаем в расширенный MakeTuple

template <class T, class ... REST> class Tuple : public Tuple<REST ...> { public: 		template <unsigned int A, unsigned int B> 		using SubTupleTypeRanged = typename Range<A, B>::Indices::template SubTupleType<T, REST ...>;  		template <unsigned int A, unsigned int B> 		inline SubTupleTypeRanged<A, B> MakeSubTuple() const 		{ 				return MakeTuple(typename Range<A, B>::Indices()); 		}  		// ... }; 

Есть мысли о том, чтобы реализовать еще один метод MakeTuple, принимающий переменное количество шаблонных параметров-типов (конкретизированные Indices или Range, иначе ошибка на этапе компиляции). Возвращаемые значения такого метода более понятны на примере:

Tuple<char, int, double, float>::MakeTuple<Indices<3, 3>, Range<0, 1>, Indices<2>> вернет Tuple<float, float, char, int, double>

Два метода MakeTuple можно совместить в один, дав параметру значение по умолчанию. Врядли инстанцирование пустого класса на стеке дает хоть сколько нибудь значимый оверхед, поэтому о производительности в данном случае можно не беспокоиться.

Бонус

В дополнение хотелось бы описать еще один достаточно интересный метод — Invoke. Он принимает в качестве параметра все, к чему можно применить оператор вызова функции с параметрами, соответсвующими полям нашего Tuple. Наш аппарат для работы с Tuple уже достаточно развит, чтобы реализовать такой метод без ввода дополнительных сущностей. Одно НО — чтобы не конкретизировать метод индексами полей для передачи в функцию/функтор/лямбду/etc нам придется снова воспользоваться тем же трюком, что и в случае MakeSubTuple.

template <class CALLABLE, unsigned int ... INDICES> inline void Invoke(CALLABLE & _function, const Indices<INDICES ...> &) { 		_function(Get<INDICES>()...); }  template <class CALLABLE> inline void Invoke(CALLABLE & _function) { 		Invoke(_function, typename Range<0, mIndex>::Indices()); } 

Что же примечательно в этом методе? А то, что с ним наш класс Tuple превращается в некое ядро для самописного класса Bind. Приведем его объявление для полноты изложения:

template <class ... ARGS> class Bind { public: 		using Function = std::function<void (ARGS ...)>; 		using Tuple = tuple::Tuple<ARGS ...>;  		Bind(Function _function, const ARGS & ... _args): 				mFunction(_function), 				mTuple(_args ...) 		{ 		}  		void operator() () 		{ 				mTuple.Invoke(mFunction); 		}  private: 		Function mFunction; 		Tuple mTuple; }; 

Конечно здесь не учтено, что у CALLABLE может быть возвращаемый тип, но решение этой проблемы выходит за пределы предметной области данной статьи.

Резюме

Резюмируя хочется отметить что все методы класса Tuple получились достаточно быстрыми, т.к. не используется никаких вычислений в рантайме.

Variadic Templates позволяют реализовать кортеж в очень сжатом количестве строк кода. Единственная проблема с дублированием кода возникает в терминирующей специализации класса Tuple - Tuple<T>. Приходится копировать код методов из более общего шаблона, а также следить за различным аспектами, учитывая, что терминирующая шаблонная специализация конкретизирована одним типом. Например мы не нуждаемся в шаблонном методе Get по индексу. Гораздо удобнее иметь простой метод Get. Хотя для однородности использования в других более высокоуровневых шаблонах индексный вариант также можно оставить.

Насчет ошибок с индексацией нужно сказать что вообще никаких телодвижений для их отлова делать не нужно. При попытке вызывать Get<2> у Tuple<int, char>, мы получим ошибку во время компиляции естественным путем, так как в индексаторе закончатся типы для передачи в Tuple. Единственная проблема заключается в «многоэтажности» ошибок, которые выдает компилятор, когда мы промахиваемся с индексом, но такие вещи легко решаются с помощью static_assert.

Как альтернативу индексации можно придумать способ дать имена полям которые мы храним в Tuple, конкретизируя в стиле Tuple<char, double, member1, member2>, а затем вызывая метод Get<member1> получать поле, соответсвующее переданному имени. Эта идея довольно интересна, т.к. мы получаем некую альтернативу простым структурам из языка C, ведь мы не теряем удобности доступа к структуре. Одно из применений Tuple с таким способом конкретизации могло бы быть создание автоматически сериализуемых классов. Достаточно просто хранить все сериализуемые поля класса в кортеже, это дает нам возможность писать compile time обходы по всем полям и вызывать, например, некоторую функцию Serialize для каждого. Также можно попытаться интегрировать каркас такой функциональности в сам Tuple.

Напоследок можно отметить интересный эффект от использования цепочки наследования. Определив Tuple<int, char, double> мы сможем передавать его в функции которые ожидают Tuple<char, double> или Tuple<double>. Иногда это может пригодиться для написания более изящного кода. Более удобной была бы возможность безопасно преобразовывать типы Tuple, отбрасывая данные не сначала, а с конца, но, к сожалению, из-за того, что пакеты параметров должны идти в конце списка параметров, это скорее всего не возможно без особо хитрых изощрений и вообще не стоит того.

Исходный код Tuple доступен на github.

К сожалению пока не было времени добавить документацию в readme, но сам код хорошо прокомментирован.
Также пока не реализовано множество приятных вещей — таких как конструктор перемещения, различные операторы, метод append, etc.
Все это планируется добавить в ближайшем будущем в порядке приоритетов.

В корне проекта есть файл main.cpp содержащий немного кода, тестирующего основной функционал кортежа.

Использованные материалы:
en.wikipedia.org/wiki/Variadic_template
habrahabr.ru/post/101430/