Implementing std::tuple From The Ground Up – Part 1: Introduction and Basic Structure

std::tuple is a very nice facility originally introduced in C++ TR1. It is a heterogenous container of elements that has a statically known size. In C++ 11, std::tuple can be implemented using variadic templates; a single std::tuple class can support an arbitrary number of template type arguments. In this series of blog posts we will implementstd::tuple from first principles. The purpose of this exercise is not to provide the best-performing or most-conformant tuple implementation, but rather to see what foundational concepts are required to implement it.

NOTE: This blog series relies on good familiarity with variadic templates and basic template metaprogramming techniques. Consider yourself warned, or, even better, check out a gentle introduction to variadic templates and a great book with a thorough overview of template metaprogramming techniques.

Before we start implementing std::tuple, let’s take a look at some of its functionality first. Here are a few things you can do with a tuple:

tuple<int, char> t1(42, 'a');
tuple<int, char> t2(t1);
get<0>(t1) = 43;
get<1>(t2) = get<1>(t1) + 1;
get<int>(t2) = 43; // get<T> added in C++ 14
set<tuple<int, string>> tuples; // OK, tuple has operator<
cout << tuple_size<tuple<int, char>>::value; // prints '2'

OK, so a tuple looks like any other container, except it has this weird syntax for accessing elements, with the get non-member function template. There are also some rather obvious operations like copy construction, move construction, assignment from another tuple, and so forth. There are also some slightly more complicated operations:

tuple t3 = make_tuple("Hello", 42);
tuple<string, int> t4 = t3; // OK, heterogenous copy construction
tuple t5 = tuple_cat(t3, t4);
int x;
string s;
tie(x, s) = make_tuple(42, "hello"); // initialize both x and s
tie(ignore, s) = make_tuple(-1, "goodbye"); // initialize only s

So, let’s get started. The first challenge in implementing a tuple is figuring out its class declaration. What should it look like? It’s obviously a variadic class template, because you can create a tuple with an arbitrary number of types. Something like this, then?

template <typename... Types>
class tuple;

Looks good. The next question is: how do we represent the tuple’s elements? That is, what members should the tuple class have? Think about it. One tempting option is to have tuple derive from all its constituent types:

template <typename... Types>
class tuple : Types...
{
};

Exercise 1: Why is that a bad idea?

Well, it’s a bad idea for many reasons. Two obvious ones that come to mind: 1) you can’t derive from many types, like int and char and any sealed type; 2) you can’t derive from the same type multiple times, so you can’t have a tuple<string, string> with this approach. What’s more, you’d end up polluting tuple’s interface with publicly accessible member functions from each of the constituent types. So, this is obviously not going to work.

We are going to derive tuple of T1, …, Tn from n types, but they aren’t going to be T1, …, Tn themselves. Instead, we will need a wrapper type, which we’ll call tuple_element; tuple will derive from tuple_element n times. How should we declare tuple_element? How about this?

template <typename T>
struct tuple_element
{
  T value_;
};

And then we can have tuple derive from tuple_elementn times, as follows:

template <typename... Types>
class tuple : tuple_element<Types>...
{
};

Exercise 2: This is better than deriving from T1, …, Tn directly, but is still broken. Why?

This is a nice attempt, but it still doesn’t work if some of the types are the same. Again, we if we instantiate a tuple<int, int>, it can’t derive from tuple_element<int> twice. Bummer. We obviously need some way to disambiguate the tuple_element base classes. How about adding an index?

template <size_t I, typename T>
struct tuple_element
{
  T value_;
};

Now, tuple_element<0, int> isn’t the same type as tuple_element<1, int>, so we can derive from both of them at once. The question is just how to do that. How can tuple derive from each of the tuple_elements with types T1, …, Tn and the appropriate indices 0, …, n-1? That is, what do we put in the following class definition?

template <typename... Types>
class tuple : tuple_element<???, Types>...
{
};

This is an interesting problem. We need to replace the ??? placeholder with a parameter pack of size_ts. If we already had this kind of pack provided by the user, we could do the following:

template <size_t... Indices, typename... Types>
class tuple : tuple_element<Indices, Types>...
{
};

Exercise 3: What if Indices and Types are parameter packs of different lengths?

Answer: It’s a compilation error. However, if both parameter packs have the same length, the pack expansion operator (…) successfully expands each tuple_element base with an index and a type. Kind of like the functional ‘zip’ operator for two sequences. Clients can use this class as follows:

tuple<0, 1, int, string> tup;

Needless to say, it’s not very convenient. We want the client to provide only the types. We will have to generate the indices ourselves, somehow. Until next time.