Implementing std::tuple in C++ 17

Image for post
Image for post

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:

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:

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:

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):

This class holds an int and a double, and we can get the values just by casting to the correspondent _tuple_impl base class:

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:

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:

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:

the following type (which is the type of the variable tuple_instance) is generated by the compiler (the compiler will mangle the type names):

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 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.
Let’s see how it works with an example:

If we write that code, this is how the generic code that we wrote is expanded:

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:

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:

With this code, the previous example would expand like this:

So, in essence, this:

creates a type with the following definition:

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:

We can now write and compile this code (we will deal with the constructors later):

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:

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 :

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:

Let’s see how this works with an example:

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):

We are almost done! We are still missing the constructors for _tuple_recurr_base and tuple, so let’s write them:

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):

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):

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 :).

Written by

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store