In the previous installment we had the following definition of **tuple**, and were looking for a way of improving it so that the caller doesn’t have to provide the integer indices.

template <size_t... Indices, typename... Types> class tuple : tuple_element<Indices, Types>... { }; tuple<0, 1, int, string> tup;

Basically, we need to provide the indices ourselves. First, let’s decouple the **tuple** class from the indices — we don’t want the client to see the additional template parameters required:

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

So… how is the **tuple** class going to provide **tuple_impl** with all the indices? We’re going to have to introduce lots of supporting code first. Let’s start with something easy:

template <size_t... Indices> struct index_sequence { using type = index_sequence<Indices...>; };

This looks very silly, but it’s nothing more than a type that encapsulates a parameter pack of **size_t**‘s. By the way, this **index_sequence** and other supporting types are part of the C++ 14 standard library. We are still going to implement them from scratch. Because we can.

Anyway, how do we use it? How do we “extract” the indices from the sequence?

**Exercise 4:** How do you write a function that takes an **index_sequence** and prints all the integers in the sequence?

The following is one solution (there are many, of course):

void f(size_t s) { cout << s << '\n'; } template <size_t... Indices> void g(index_sequence<Indices...>) { int ignore[] { (f(Indices), 0)... }; (void) ignore; // silence compiler warnings about the unused local variable } g(index_sequence<1, 2, 3, 4, 5>{});

Whoa! Let’s break this thing down. First, we have the function **f**, which simply prints a single **size_t** element. That’s not hard. Next, we have the function **g**. It takes a sequence of indices. Notice that the parameter doesn’t have a name — we don’t really care about it. It’s merely a way of getting data into the function. The interesting data is in the parameter pack. Inside **g** we want to call **f** for each index. Unfortunately, naked expansion such as the following is not supported:

f(Indices)...;

That’s why we have to resort to weird workarounds. We’re declaring a local array initialized with the expansion of a comma expression **(f(Indices), 0)**. When **g** is called with Indices = [1, 2, 3], this expression expands to **(f(1), 0), (f(2), 0), (f(3), 0)**. And that comma-separated list of 0’s goes into the local array.

Finally, to call **g**, the client simply provides an **index_sequence** instantiation. The compiler deduces the **Indices** parameter pack from the instantiation, and all is well. But how do we use this technique to derive from **tuple_element** for each index?

Well, suppose we wanted a **tuple** of three types, T0, T1, T2. We could use our current infrastructure as follows:

template <typename T0, typename T1, typename T2> class tuple : tuple_impl<0, 1, 2, T0, T1, T2> { };

That’s great for three types, but how do we make indices appear in the list when given a type parameter pack (**typename… Types**)? Let’s try integrating **index_sequence** into the story. We’re rewriting **tuple_impl** a bit:

template <typename Sequence, typename... Types> struct tuple_impl; // undefined base; parameters are named for clarity only template <size_t... Indices, typename... Types> struct tuple_impl<index_sequence<Indices...>, Types...> : tuple_element<Indices, Types>... { };

This is another “whoa” moment. The second definition (which is the interesting one) is a class template specialization. The specialization’s template parameters are 1) a parameter pack **…Indices**, and 2) a type parameter pack **…Types**. The specialization matches the case when Sequence = **index_sequence**, which is the only way we intend to use it anyway. The base template exists only so that we can specialize it.

Now suppose again we wanted a **tuple** of three types, T0, T1, T2. We could do the following now:

template <typename T0, typename T1, typename T2> class tuple : tuple_impl<index_sequence<0, 1, 2>, T0, T1, T2> { };

Are we getting any closer? I think so. Now, instead of having to come up with an arbitrary sequence of indices, we just need to come with **index_sequence<0, …, n-1>** when the **tuple** is instantiated with *n* types. Let’s call this thing **make_index_sequence**. It’s a metafunction. That is, I would like **make_index_sequence::type** to be an alias for **index_sequence<0, …, n-1>**.

**Exercise 5**: Implement **make_index_sequence**.

I’m going to go with an approach that is not particularly efficient, short, or pretty, but is easy to understand and instructive. Let’s go:

template <size_t I, typename Sequence> struct cat_index_sequence; template <size_t I, size_t... Indices> struct cat_index_sequence<I, index_sequence<Indices...>> : index_sequence<Indices..., I> { }; template <size_t N> struct make_index_sequence : cat_index_sequence<N-1, typename make_index_sequence<N-1>::type>::type { }; template <> struct make_index_sequence<1> : index_sequence<0> {};

It takes a little while to digest, but there is nothing particularly complicated here. The **cat_index_sequence** template is a metafunction that appends an index to the end of an existing index sequence. The **make_index_sequence** metafunction is then defined by recursively appending elements to the end of a growing index sequence. The base case to terminate the recursion is reached at **make_index_sequence<1>**, which is defined as **index_sequence<0>**.

We are now ready to implement the **tuple** class. I’m going to repeat the definitions for **tuple_element** and **tuple_impl** here, just to make the whole thing a bit clearer:

template <size_t, typename T> struct tuple_element { T value_; }; template <typename Sequences, typename... Types> struct tuple_impl; // undefined base; parameters are named for clarity only template <size_t... Indices, typename... Types> struct tuple_impl<index_sequence<Indices...>, Types...> : tuple_element<Indices, Types>... { }; template <typename... Types> class tuple : tuple_impl<typename make_index_sequence<sizeof...(Types)>::type, Types...> { };

Done! **sizeof…(Types)** is the number of elements in the **tuple** (let’s call it *n*), **make_index_sequence** produces **index_sequence<0, 1, …, n-1>**, and that’s what we use to instantiate **tuple_impl** with the appropriate indices so that it can derive from **tuple_element** for each index.

At this point, when we say **tuple<int, string, float>** we get a type that derives from **tuple_impl<index_sequence<0, 1, 2>, int, string, float>**, which in turn derives from **tuple_element<0, int>**, **tuple_element<1, string>**, and **tuple_element<2, float>**. And that’s definitely enough for today. Next time, we’re going to tackle the construction of tuple objects.

Are you just doodling in an attempt to show us what might not work or do you expect things like:

template

struct tuple_impl { };

to compile?

Because most compilers complain that if a class template has a template parameter pack then it must appear at the end of a template parameter list.

I can’t believe you missed it, so I am assuming you were just thinking out aloud?

The comment editor swallowed your template parameters, so I’m assuming you’re objecting to the idea of two template parameter packs: size_t… Indices and typename… Types. Indeed, I am presenting the idea gradually. The code at the beginning of the post does not compile, and is not intended to compile. At the end of the post, we have a fully functioning version, however. The tuple_impl struct is declared with typename Sequence, typename… Types and then specialized for index_sequence. You can experiment with it here: http://ideone.com/sgQmYV

Then please write it explicitly, that the code does not compile.

template

class tuple : tuple_element...

{

};

`tuple tup;`

You write in a way that it sound like the code above is legal c++.

Thank you for your feedback. I am going to leave this post as is, but I will keep your suggestion in mind for future installments.

Pingback: Implementing std::tuple - Part 3: Constructing Tuples