Implementing std::tuple From The Ground Up – Part 2: Index Sequences

January 16, 2015

tags: ,
5 comments

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.

Add comment
facebook linkedin twitter email

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

5 comments

  1. DilipJanuary 22, 2015 ב 12:28 AM

    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?

    Reply
    1. Sasha Goldshtein
      Sasha GoldshteinJanuary 22, 2015 ב 7:35 AM

      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

      Reply
      1. icepicJanuary 24, 2015 ב 3:07 PM

        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++.

        Reply
        1. Sasha Goldshtein
          Sasha GoldshteinJanuary 28, 2015 ב 11:26 AM

          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.

          Reply
  2. Pingback: Implementing std::tuple - Part 3: Constructing Tuples