Implementing std::tuple From The Ground Up: Part 6, tuple_cat Take 1

February 13, 2015

tags: ,
one comment

We are almost done. We have a pretty functional tuple that supports almost every operation mandated by the Standard. With one major exception: tuple_cat. First, let’s see what it does:

auto t1 = tuple_cat(make_tuple(1), make_tuple(2)); // tuple<int, int>(1, 2)
auto t2 = tuple_cat(t1, make_tuple(3), make_tuple(4));
auto t3 = tuple_cat(t1, t1, t2, t2);
// t3 is a tuple of 12 ints: 1, 2, 1, 2, 1, 2, 3, 4, 1, 2, 3, 4

Hmpf. Obviously, tuple_cat is a variadic function template. tuple is itself a variadic class template, and we’re now trying to build a variadic function template that takes any number of variadic class templates? That’s a pretty crazy proposition… but it’s doable. We will in fact see two different ways to implement tuple_cat: a simple one which is a bit slow for large tuples, and a more complex one which is much faster. If your standard library implementers haven’t gone to great lengths to implement tuple_cat efficiently, our second implementation might actually beat the std::tuple on your machine!

Let’s try to solve a simpler problem first. Given a tuple, how do we call a function that accepts all the tuple‘s elements? In other words, how do we “explode” a tuple?

Exercise 13: Write a function explode that takes a tuple of arbitrary length and passes all its elements to another function f.

The basic idea is to use our good friend index_sequence. For a tuple of size n, we need to produce index_sequence<0, 1, …, n-1>. The indices of this index_sequence can then be used with the get<I> function to extract the tuple‘s elements. We don’t ever need access to the tuple‘s types, so we can simply use a universal reference, which simplifies the code and means we correctly forward rvalue tuples:

template <typename Tuple, size_t... Indices>
void explode1(Tuple&& tup, index_sequence<Indices...>)
{
  f(get<Indices>(std::forward<Tuple>(tup))...);
}

template <typename Tuple>
void explode(Tuple&& tup)
{
  explode1(
    std::forward<Tuple>(tup),
    make_index_sequence<tuple_size<std::decay_t<Tuple>>::value>{}
  );
}

index_sequence strikes again! The key is calling get<Indices>(tup)…, which expands to multiple invocations of get: get<0>(tup), get<1>(tup), …, get<n-1>(tup) where n is the size of the tuple. Now, what if we had two tuples, and f was called make_tuple?

Exercise 14: Write a simplified version of tuple_cat that concatenates two tuples.

Solution:

template <typename Tuple1, size_t... Indices1, typename Tuple2, size_t... Indices2>
auto tuple_cat1(Tuple1&& tup1, Tuple2&& tup2,
                index_sequence<Indices1...>, index_sequence<Indices2...>)
{
  return make_tuple(
    get<Indices1>(std::forward<Tuple1>(tup1))...,
    get<Indices2>(std::forward<Tuple2>(tup2))...
  );
}

template <typename Tuple1, typename Tuple2>
auto tuple_cat(Tuple1&& tup1, Tuple2&& tup2)
{
  tuple_cat1(
   std::forward<Tuple1>(tup1),
   std::forward<Tuple2>(tup2),
   make_index_sequence<tuple_size<std::decay_t<Tuple1>>::value>{},
   make_index_sequence<tuple_size<std::decay_t<Tuple2>>::value>{}
  );
}

So, the basic idea is that we call make_tuple and expand both tuples’ elements as its parameters. The two parameters packs …Indices1 and …Indices2 help expand each individual tuple.

I’m using return type deduction from C++ 14 to avoid having to specify the return type, which is pretty nasty. Still, there’s no technical problem specifying it — it’s basically an expansion of the tuple‘s types. A lot of technical work, but nothing particularly new; something like this:

template <size_t, typename>
struct type_at_tuple; // undefined base template

template <size_t I, typename... Types>
struct type_at_tuple<I, tuple<Types...>> : type_at_index<I, Types...>
{
};

template <typename, typename, typename, typename>
struct cat1_t; // undefined base template

template <typename Tuple1, size_t... Indices1, typename Tuple2, size_t... Indices2>
struct cat1_t<
  Tuple1, index_sequence<Indices1...>,
  Tuple2, index_sequence<Indices2...>
>
{
  using type = tuple<
    typename type_at_tuple<Indices1, Tuple1>::type...,
    typename type_at_tuple<Indices2, Tuple2>::type...
  >;
};

template <typename Tuple1, typename Tuple2>
struct cat_t
{
  static constexpr size_t Size1 = tuple_size<std::decay_t<Tuple1>>::value;
  static constexpr size_t Size2 = tuple_size<std::decay_t<Tuple2>>::value;
  using Seq1 = typename make_index_sequence<Size1>::type;
  using Seq2 = typename make_index_sequence<Size2>::type;
  using type = typename cat1_t<Tuple1, Seq1, Tuple2, Seq2>::type;
};

Now you can replace tuple_cat‘s return type with typename cat_t<Tuple1, Tuple2>::type if your compiler doesn’t support C++ 14.

Let’s tackle the variadic tuple_cat, which accepts any number of tuples. It’s a recursion that relies on what already have.

Exercise 15: Generalize tuple_cat for any number of tuples.

Assuming that tuple_cat from the previous example is still present and concatenates two tuples, rename it to tuple_cat2 and use it recursively:

template <typename HeadTuple>
HeadTuple&& tuple_cat(HeadTuple&& tup)
{
  return std::forward<HeadTuple>(tup);
}

template <typename Head1Tuple, typename Head2Tuple, typename... TailTuples>
auto tuple_cat(Head1Tuple&& tup1, Head2Tuple&& tup2, TailTuples&&... tail)
{
  return tuple_cat(
    tuple_cat2(
      std::forward<Head1Tuple>(tup1),
      std::forward<Head2Tuple>(tup2)
    ),
    std::forward<TailTuples>(tail)...
  );
}

What about that nasty return type? Again, I’m deferring to C++ 14’s return type deduction, but you can generalize the cat_t template to support an arbitrary number of tuples if you don’t have access to a C++ 14 compiler. It’s again purely technical:

template <typename, typename>
struct cat_two_t; // undefined base template

template <typename... Types1, typename... Types2>
struct cat_two_t<tuple<Types1...>, tuple<Types2...>>
{
  using type = tuple<Types1..., Types2...>;
};

template <typename...>
struct cat_many_t; // undefined base template

template <typename Tuple>
struct cat_many_t<Tuple>
{
  using type = Tuple;
};

template <typename Tuple1, typename Tuple2, typename... Tuples>
struct cat_many_t<Tuple1, Tuple2, Tuples...>
{
  using two_t = typename cat_two_t<Tuple1, Tuple2>::type;
  using type = typename cat_many_t<two_t, Tuples...>::type;
};

The approach shown in this post works very well. We can now concatenate any number of tuples. The only problem is that we’re creating quite a few temporaries. Each “recursive” invocation in tuple_cat creates temporary tuple objects. If we have a lot of tuples and their elements are expensive to copy, this can be bad. In the next and final installment we will see how to implement tuple_cat even more efficiently, making only a single copy of each element.

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>

*

one comment

  1. Pingback: Implementing std::tuple - Part 6: tuple_cat, Take 2