Features of c ++ tuples implementation

Impressed by the excellent article on Variadic Templates from the respected FlexFerrum, he decided to practice metaprogramming and write his own implementation of a data structure called Tuple (Tuple) using templates with a variable number of arguments. For those who are not familiar, a tuple is a data structure that stores data of different types simultaneously. In our particular case, this will be a template class that stores data of the types that were passed to it as template parameters (taking into account the order).



It is assumed that the reader is already familiar with the above article, when describing the development process, I will build on it.

Data storage

The first problem we face is the principle of data storage. The FlexFerrum article proposed a class implementation, which is essentially a superposition of functions that are passed as template parameters. To save pointers to functions, a model of multiple inheritance from the DataHolder class was DataHolder , which stores in itself what it was parameterized with:

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

')

We will go a little different way with you and build a chain of inheritance, and in the end we will look at what benefits we have from this.

 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; } 

The implementation of the constructors should be obvious: we initialize the field of the current class and call the base class constructor with the remaining arguments.

Set / Get methods

The next step is the implementation of setters and getters for class data fields. Methods that receive and record at once all fields are simple to implement and are not given here. Much more interesting is the situation, say, with a getter that takes a numeric index of a field as a template argument. To implement it, we need some auxiliary class that will allow us to index Tuple types in our inheritance chain as follows: type with index 0 is the lowest descendant, with index 1 is its immediate ancestor, etc. by induction. When transferring too many numbers, we should receive an error at compile time. You can make such a class by defining a terminating specialization for index 0, and a more general definition for index N by specifying with index N is 1. We will define the tuple itself as using (or typedef ) in the inside of our “indexer”. Let's call our class plainly 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 ...>; }; 

Further we will use the fact that we did not use multiple inheritance, but built a chain of classes. We will bring the current class Tuple to Tuple , calculated by index through static_cast . To calculate the return value from the Get method, we will create a synonym for the left-most field in our Tuple and retrieve it from the Tuple obtained by the index.

 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; } 

The setter implementation is not shown because it is identical to the getter. Unfortunately, a full-fledged iteration over the index in this tuple is impossible (is it necessary?), Since we need to know the type of the return value.

Subuple

The next stage that I would like to describe is the addition of the possibility of creating a tuple from some combination of other fields. The simplest option is a template method that accepts a variable number of indices by which the fields will be taken and transferred to the constructor of the new 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>() ...); } // ... }; 

But this is not enough for us. We implement a template method that accepts a range of indices and returns Tuple specific types with indices from a specified range. Those:

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

As you might have guessed, we need another auxiliary class that will allow us to calculate the type of Tuple returned by a range, not by an index. To do this, we use a technique similar to the method from the FlexFerrum article. Let's create a class that takes a range as template parameters (A and B) and stores a synonym for a certain class specified by indices from A to B. That class, in turn, will calculate for us the Tuple type. Names for our classes will choose Range and Indices accordingly.



An implementation of the Indices class that stores the appropriate type of Tuple template:

 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: }; 

The implementation of the actual range:

 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: }; 

In this case, the terminating branch is a range with equal beginning and end (length = 0). The range with the length N determines the IndicesExtendable pattern through the IndicesExtendable pattern from the range with the length N - 1. Speaking in simpler language, we gradually tighten the range to a point with a step of one. If you observe the type inference process in the opposite direction, then at each iteration of the range expansion a new synonym for the IndicesExtendable template IndicesExtendable added by adding a new template parameter — another index to the synonym IndicesExtendable template from the previous iteration. Thus Range<1, 4> will contain Indices = Indices<1, 2, 3, 4> . This range class also works for the opposite case - Range<4, 1> . This will give the type Indices<4, 3, 2, 1> .



Another detail is connected with the fact that in the MakeSubTuple method we need to somehow call the constructor call with the correct fields as arguments. You can do this by adding another MakeTuple method that takes Indices as a parameter. This is another way to specify the template method.

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

The implementation of this method is similar to the first. In the body of the method, the parameter is simply ignored. Now we can make a call without passing template parameters:

 t.MakeTuple(Indices<1, 2, 3>) //  ,   t.MakeTuple<1, 2, 3>() 

Now we are ready and we can go directly to the implementation of the MakeSubTuple method. Simply we get the Indices we need from the Range, instantiate it on the stack or as a static variable and pass it to the advanced 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()); } // ... }; 

There are thoughts about implementing another MakeTuple method that accepts a variable number of template parameter types (specified Indices or Range , otherwise it is an error at the compilation stage). The returned values ​​of this method are clearer by example:



Tuple<char, int, double, float>::MakeTuple<Indices<3, 3>, Range<0, 1>, Indices<2>> will return Tuple<float, float, char, int, double>



Two methods MakeTuple can be combined into one, giving the parameter a default value. Hardly instantiating an empty class on the stack gives at least some significant overhead, so you should not worry about performance in this case.

Bonus

In addition, I would like to describe another quite interesting method - Invoke . It takes as a parameter everything to which you can apply the function call operator with the parameters corresponding to the fields of our Tuple . Our apparatus for working with Tuple already sufficiently developed to implement such a method without entering additional entities. One BUT - in order not to concretize the method with field indexes to pass to the function / functor / lambda / etc, we will have to use the same trick again as in the case of 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()); } 

What is remarkable about this method? And the fact that with it our Tuple class turns into a kind of core for the Bind class. We give his announcement for completeness:

 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; }; 

Of course, it does not take into account that CALLABLE may have a return type, but the solution to this problem is beyond the scope of this article.

Summary

In summary, I would like to note that all the methods of the Tuple class turned out to be quite fast, because no calculations are used in runtime.



Variadic Templates allow you to implement a tuple in a very compressed number of lines of code. The only problem with duplication of code arises in the termination specialization of the Tuple - Tuple. , , , . Get . Get . .



. Get<2> Tuple<int, char> , , Tuple . "" , , , static_assert .



Tuple , Tuple<char, double, member1, member2> , Get , . , .. C , . Tuple . , compile time , , Serialize . Tuple .



. Tuple<int, char, double> Tuple<char, double> Tuple. . Tuple , , , , , - , , .



Tuple github .



readme, .

- , , append , etc.

.



main.cpp , .



:

en.wikipedia.org/wiki/Variadic_template

habrahabr.ru/post/101430 class Tuple - Tuple. , , , . Get . Get . .



. Get<2> Tuple<int, char> , , Tuple . "" , , , static_assert .



Tuple , Tuple<char, double, member1, member2> , Get , . , .. C , . Tuple . , compile time , , Serialize . Tuple .



. Tuple<int, char, double> Tuple<char, double> Tuple. . Tuple , , , , , - , , .



Tuple github .



readme, .

- , , append , etc.

.



main.cpp , .



:

en.wikipedia.org/wiki/Variadic_template

habrahabr.ru/post/101430 Tuple - Tuple. , , , . Get . Get . .



. Get<2> Tuple<int, char> , , Tuple . "" , , , static_assert .



Tuple , Tuple<char, double, member1, member2> , Get , . , .. C , . Tuple . , compile time , , Serialize . Tuple .



. Tuple<int, char, double> Tuple<char, double> Tuple. . Tuple , , , , , - , , .



Tuple github .



readme, .

- , , append , etc.

.



main.cpp , .



:

en.wikipedia.org/wiki/Variadic_template

habrahabr.ru/post/101430