Implementing std::tuple in C++ 17
In this post we are going to try to implement std::tuple using C++17. It’s not going to be a full implementation, but we will implement what the main features, so at the end of the post we should be able to run this code:
#include "tuple.hpp" // our own implementation of std::tuple
#include <string>
#include <iostream>int main(int argc, char **argv)
{
tuple t{1, 2.0, std::string(“hello”), std::string(“world”)}; std::cout << get<0>(t) << “, “ << get<1>(t) << “, “ << get<2>(t) << “, “ << get<3>(t2) << ‘\n’; // This prints: 1, 2.0, hello, world tuple t2{1, 2.0, std::string(“hello”), std::string(“world”)}; std::cout << std::boolalpha << “tuples are equal: “ << (t2 == t3) << ‘\n’; // This prints: tuples are equal: true return 0;
}
If you want you can skip the explanation and go directly to the code that we will be writing in this post: tuple implementation.
Let’s start: our first goal is to write an implementation of tuple that allows us to write the following code:
tuple<int, double> t{3, 5.0};For this, we need a class that is able to hold different variables of different types. One of the ways of doing is is using inheritance. We’ll see how in a moment, but first let’s write the basic implementation of a class that holds the value of a given type. This class has a method that returns a reference to the current value it holds . I’m calling this class _tuple_impl:
template <typename T>
class _tuple_impl
{
public:
_tuple_impl(T const &v)
{
val = v;
}_tuple_impl(T &&v)
{
val = std::move(v);
} T &get()
{
return val;
}private:
T val;
};
Now, let’s see how we can use inheritance to create a class, tuple, that holds values of many different types.
Let’s start with a non-generic example: let’s say that we want to create an object of type: tuple<int, double>: we could use inheritance to accomplish this (let’s omit constructors for the moment):
class tuple_int_double : public _tuple_impl<int>,
public _tuple_impl<double>
{
};This class holds an int and a double, and we can get the values just by casting to the correspondent _tuple_impl base class:
tuple_int_double t;
int &int_v = static_cast<_tuple_impl<int>&>(t).get();This works, but this solution has a problem: a tuple created this way cannot hold different values for the same type: for example, we can’t have a tuple that holds two ints, as there can be only one base class _tuple_impl<int> that holds the int value.
We can fix this issue if, somehow, we inherit from different _tuple_impl classes, even if the type is the same. In order to do this we can add a new template parameter, std::size_t, that we use to create different _tuple_impl types:
template <std::size_t _index, typename T>
class _tuple_impl
{
public:
_tuple_impl(T const &v)
{
val = v;
}_tuple_impl(T &&v)
{
val = std::move(v);
} T &get()
{
return val;
}private:
T val;
};
With this implementation for _tuple_impl, we can now write a tuple class that holds more than one value for the same type. We use the _index template parameter as an index:
class tuple_int_int : public _tuple_impl<0, int>,
public _tuple_impl<1, int>
{
};tuple_int_int t;
int &int_v = static_cast<_tuple_impl<0, int>&>(t).get();
Great! now that we understand the basis of how our implementation of tuple will work, we need to write a generic version of the code we’ve just written.
Our goal is that if we write and compile this:
tuple<int, double, float> tuple_instance;the following type (which is the type of the variable tuple_instance) is generated by the compiler (the compiler will mangle the type names):
tuple : public _tuple_impl<0, int>,
public _tuple_impl<1, double>,
public _tuple_impl<2, float>Using recursion we can achieve exactly that. Let’s see how.
I’m going to write a class, _tuple_recurr_base that does this, and then I’ll explain how it works:
/*
This class inherits from _tuple_impl, and itself
*/template <std::size_t _index,
typename L,
typename… types>
class
_tuple_recurr_base : public _tuple_impl<_index, typename std::remove_reference<L>::type>,
public _tuple_recurr_base<_index + 1, types…>
{
};
This is a templated class that takes three parameters: an index, _index, and a type L, which are used to define the base class _tuple_impl, and a variadic template, types, which covers the rest of the types passed.
_tuple_recurr_base inherits from _tuple_impl, and from itself (hence the recursion). Notice this important detail: in the recursion we increment the index. We also use std::remove_reference, as we are interested in the type without the references, e.g. if the L is an int&, we want the base _tuple_impl to hold a type int, but not a reference to int.
Let’s see how it works with an example:
_tuple_recurr_base<0, int, double, float> l;If we write that code, this is how the generic code that we wrote is expanded:
/*
This is how "_tuple_recurr_base<0, int, double, float>" is expanded.
L is int, types... is double, float
*/
class _tuple_recurr_base<0, int, double,float> :
public _tuple_impl<0, int>,
public _tuple_recurr_base<1, double, float> /* Now this is expanded */
/*
this is how the previous base class, _tuple_recurr_base<1, double,float> is expanded
L is double, types... is float
*/
class _tuple_recurr_base<1, double, float> :
public _tuple_impl<1, double>,
public _tuple_recurr_base<2, float> /* Now this is expanded */
/*
This is how _tuple_recurr_base<2, float> is expanded
L is float, there is no types...
*/
class _tuple_recurr_base<2, float, > :
public _tuple_recurr_base<2> /* Ops, no candidates found, template argument "L" missing */
As stated in the last comment, now we’ve run into a problem and the compiler complains: _tuple_recurr_base<2> cannot be expanded, because our declaration of _tuple_recurr_base requires at least two template parameters, the index, _index, and the type, L, (the number of variadic template arguments can be zero) but only _index was provided. Remember the definition of _tuple_recurr_base:
/*
Our current definition of _tuple_recurr_base. It needs at least two template parameters: the index and a type L (the variadic template argument, types, can be empty)
*/template <std::size_t _index, typename L, typename… types>
class _tuple_recurr_base : public _tuple_impl<_index, L>,
public _tuple_recurr_base<_index + 1, types…>
{
};
How can we work around this issue? We can define a generic _tuple_recurr_base class that only takes the index and a variadic template argument. If we do this, the original declaration of _tuple_recurr_base that takes the index, _index, a type, L, and the variadic template argument, types, becomes a specialization of that class, and, as long as there is at least one template argument (apart from the index), this specialization would be always preferred by the compiler.
This would be now the full definition of _tuple_recurr_base:
/*
General template class declaration.
*/
template <std::size_t _index, typename… types>
class _tuple_recurr_base
{
};/*
This is a partial specialization, so as long as there is at least one template argument, apart from the index, this specialization is preferred to the previously defined _tuple_recurr_base<std::size_t, typename …types>
*/
template <std::size_t _index, typename L, typename… types>
class _tuple_recurr_base<_index, L, types…> :
public _tuple_impl<_index, typename std::remove_reference<L>::type>,
public _tuple_recurr_base<_index + 1, types…>
{
};
With this code, the previous example would expand like this:
/*
This is how _tuple_recurr_base<0, int, double, float> is expanded
*/
class _tuple_recurr_base<0, int, double,float> :
public _tuple_impl<0, int>,
public _tuple_recurr_base<1, double, float> /* Now this is expanded *//*
this is how the previous base class, _tuple_recurr_base<1, double, float> is expanded
*/
class _tuple_recurr_base<1, double, float> :
public _tuple_impl<1, double>,
public _tuple_recurr_base<2, float> // Now this is expanded/*
This is how _tuple_recurr_base<2, float> is expanded
*/
class _tuple_recurr_base<2, float> :
public _tuple_impl<1, double>,
public _tuple_recurr_base<2>/*
Now, _tuple_recurr_base<2> is missing the "L" template argument, so the more generic
template <std::size_t _index, typename… types> _tuple_recurr_base class is picked by the compiler
*/
template<2>
_tuple_recurr_base
{};
So, in essence, this:
_tuple_recurr_base<0, int, double, float> l;creates a type with the following definition:
_tuple_recurr_base<0, int, double, float> :
public _tuple_impl<0, int>,
public _tuple_impl<1, double>,
public _tuple_impl<2, float>,
public _tuple_recurr_base<3>;Now we have all the ingredients that we need to create our tuple class: the implementation for a type, _tuple_impl, and the class that recursively inherits from _tuple_impl for each provided type. We can now define our tuple class like this:
template <typename L, typename… types>
class tuple : public _tuple_recurr_base<0, L, types…>We can now write and compile this code (we will deal with the constructors later):
tuple<int, double, float> t;Nice! Now we need to work on the other piece of the puzzle: how to get values out of the tuple.
Let’s say that we want to get the value of the second type out of the previous tuple, how could we do it?
First, notice that this would be the inheritance tree of the tuple from the previous code:
tuple<int, double, float> :
public _tuple_impl<0, int>,
public _tuple_impl<1, double>,
public _tuple_impl<2, float>,
public _tuple_recurr_base<3>To get values out of the tuple, we could static_cast the tuple to the base _tuple_impl class that holds that value, and then call the get() method of _tuple_impl.
This is how the code would look like for the previous example if we wanted to get the double value out of the tuple :
tuple<int, double, float> t;
double &double_val = (static_cast<_tuple_impl<1, double> &>(t)).get();If we were to encapsulate this cast to a function, the function would need two template parameters: the index and the type. However, as we know from the std::tuple API, there is a method, std::get, that takes a template parameter of type std::size_t, I, and the tuple, t, and extracts the Ith element from the tuple.
We should be able to write a similar get method that only takes the tuple and the index.
As we saw before, in order to do the static_cast to the right _tuple_impl class, we needed not only the index and the tuple, but also the type at that index.
If we are going to write a function that only takes the tuple and the index, like std::get does, we first need to write some code that, given an index and a tuple, gives us the type corresponding to that index in the tuple.
This can be done using recursion in a similar way that we did for the definition of _tuple_recurr_base.
What we will do is to create a template class, extract_index_at, that takes an index, _index, a template argument, L, and a variadic template argument, Args…. If _index is zero (we can detect this via a specialization of the class), we define the type as the template argument, L,and if _index is not zero, we define the type in a recursive way, subtracting one to _index and passing the variadic template argument. Let’s see the code with some comments:
/*
extract_type_at is a class that, given a list of types and an index, defines a member class "type"
with the type of the index given from the list (zero based index).
E.g. extract<1, int, double, float>::type == double
For this we define ::type recursively, until we hit index zero, at that point there is a specialization
that defines the member ::type, and stops the recursion
*/
template <std::size_t index, typename L, typename… Args>
struct extract_type_at
{
using type = typename extract_type_at<index — 1, Args…>::type;
};
/*
This is the stop specialization. If the index is zero, we define the member type to be the template argument, L, ignoring the variadic template argument
*/
template <typename L, typename… Args>
struct extract_type_at<0, L, Args…>
{
using type = L;
};
Let’s see how this works with an example:
/*
Let's see how the compiler solves the following example:
extract_type_at<2, int, double, float>::type*//*
The compiler needs to resolve: extract_type_at<2, int, double, float>::type
Because the index is not zero, the specialization is not a candidate, so the non-specialized version of extract_type_at is used.
Here, L = int, Args... = double, float
*/
struct extract_type_at<2, int, double, float>
{
using type = typename extract_type_at<1, double, float>::type;
};/*
Now the compiler needs to resolve: extract_type_at<1, double, float>::type
Again, index is not zero, so specialization is not considered.
Here, L = double, Args... = float
*/
struct extract_type_at<1, double, float>
{
using type = typename extract_type_at<0, float>::type;
};/*
Finally, the compiler needs to resolve: extract_type_at<0, float>::type;
Now we've hit the specialization where index is zero.
Here, L = float
*/
struct extract_type_at<0, float>
{
using type = float;
};/*
So,
extract_type_at<2, int, double, float>::type =
extract_type_at<1, double, float>::type =
extract_type_at<0, float>::type =
float
*/
Perfect! With this code, given a list of types, we can extract the type at a certain index. Now we have all we need to write our own get function, which will perform the static_cast that we saw before (I’m using return type deduction):
/*
Method to get the value of a tuple, given an index.
We cast the tuple to the base class that corresponds to the index
and type for that index
*/
template <std::size_t index, typename… Args>
auto &get(tuple<Args…> &t)
{
return (static_cast<_tuple_impl<index, typename extract_type_at<index, Args…>::type> &>(t)).get();
}We are almost done! We are still missing the constructors for _tuple_recurr_base and tuple, so let’s write them:
template <std::size_t _index, typename L, typename... types>
class _tuple_recurr_base<_index, L, types...> : public _tuple_impl<_index, typename std::remove_reference<L>::type>,
public _tuple_recurr_base<_index + 1, types...>
{
public:
template <typename CL, typename... CArgs>
_tuple_recurr_base(CL &&arg, CArgs &&... args) : _tuple_impl<_index, typename std::remove_reference<CL>::type>(std::forward<CL>(arg)),
_tuple_recurr_base<_index + 1, types...>(std::forward<CArgs (args)...)
{
}
};template <typename L, typename… types>
class tuple : public _tuple_recurr_base<0, L, types…>
{
public:
/*
The constructor uses the same recursion as the inheritance
*/
template <typename… CArgs>
tuple(CArgs &&… args) : /* Call base ctors */
_tuple_recurr_base<0, L, types…>(std::forward<CArgs>(args)…)
{
}
};
There is something else missing: the equality operator==. This operator will compare each element of the given tuples (using the get method that we wrote earlier), in a recursive way.
Now that we’ve written almost the full implementation of our tuple, I think it could be a good exercise for the reader to think about how we could implement operator==, before looking at my implementation.
This is my implementation (I’m using if constexpr):
template <std::size_t index, typename… Args>
bool compare_tuple(tuple<Args…> &t1, tuple<Args…> &t2)
{
if constexpr (index == 0)
{
return get<0>(t1) == get<0>(t2);
}
else
{
return get<index>(t1) == get<index>(t2) &&
compare_tuple<index — 1>(t1, t2);
}
}template <typename… Args>
bool operator==(tuple<Args…> &t1, tuple<Args…> &t2)
{
return compare_tuple<sizeof…(Args) — 1>(t1, t2);
}
Finally, we can write our own “template argument deduction guide” so we can create a tuple without explicitly writing the template types (they will be deduced from the types passed in the constructor):
// template deduction guideline
template <typename… CArgs>
tuple(CArgs… args)->tuple<CArgs…>;And that was the last thing! Now we can compile and run the code from the beginning of the post.
There are still things missing: there are no copy/move constructors, there are some operators missing, and some helper classes too (like std::tuple_size).
Hopefully, after reading this post you understand how std::tuple can be implemented in C++17, and you can implement your own and add all the things that are missing here. I actually think that taking this code and implementing all the missing bits is a good exercise for the reader :).