How to make a function that zips two tuples in C++11 (STL)?

Question

I recently ran across this puzzle, was finally able to struggle out a hacky answer (using index arrays), and wanted to share it (answer below). I am sure there are answers that use template recursion and answers that use boost; if you're interested, please share other ways to do this. I think having these all in one place may benefit others and be useful for learning some of the cool C++11 template metaprogramming tricks.

Problem: Given two tuples of equal length:

auto tup1 = std::make_tuple(1, 'b', -10);
auto tup2 = std::make_tuple(2.5, 2, std::string("even strings?!"));

How do you create a function that will "zip" the two tuples into a heterogeneous tuple of pairs?

std::tuple<
    std::pair<int, double>,
    std::pair<char, int>,
    std::pair<int, std::string> > result =
    tuple_zip( tup1, tup2 );

Where

std::get<0>(result) == std::make_pair(1, 2.5);
std::get<1>(result) == std::make_pair('b', 2);
std::get<2>(result) == std::make_pair(-10, std::string("even strings?!"));

Barrada

And now for the bonus: 1/ Can you make it work even for tuples of unequal lengths (padding with nullptr_t for example) ? and more involved 2/ Can you make it work with an arbitrary number of tuples ? – Kokanee

What do you mean with zip two tuples? Can you post expected result? – Roccoroch

@BЈовић I've added the desired output of the final main routine to the answer below. By zip, I mean take the two tuples above (tup1 and tup2) and create a tuple of 3 elements in this case, where the first is make_pair(1, 2.5), etc. – Barrada

@MatthieuM. Voila! Edit below has padding for tuples of different sizes. :) – Barrada

Answer 1

First, a quick overview of index arrays:

template<std::size_t ...S>
struct seq { };

// And now an example of how index arrays are used to print a tuple:
template <typename ...T, std::size_t ...S>
void print_helper(std::tuple<T...> tup, seq<S...> s) {
  // this trick is exceptionally useful:
  // ((std::cout << std::get<S>(tup) << " "), 0) executes the cout
  // and returns 0.
  // { 0... } expands (because the expression has an S in it),
  // returning an array of length sizeof...(S) full of zeros.
  // The array isn't used, but it's a great hack to do one operation
  // for each std::size_t in S.
  int garbage[] = { ((std::cout << std::get<S>(tup) << " "), 0)... };
  std::cout << std::endl;
}

And now to use our print_helper function:

int main() {
  print_helper(std::make_tuple(10, 0.66, 'h'), seq<0,1,2>() );
  return 0;
}

Typing seq<0,1,2> can be a bit of a pain, though. So we can use template recursion to create a class to generate seqs, so that gens<3>::type is the same as seq<0,1,2>:

template<std::size_t N, std::size_t ...S>
struct gens : gens<N-1, N-1, S...> { };

template<std::size_t ...S>
struct gens<0, S...> {
  typedef seq<S...> type;
};

int main() {
  print_helper(std::make_tuple(10, 0.66, 'h'), gens<3>::type() );
  return 0;
}

Since the N in gens<N>::type will always be the number of elements in the tuple, you can wrap print_helper to make it easier:

template <typename ...T>
void print(std::tuple<T...> tup) {
  print_helper(tup, typename gens<sizeof...(T)>::type() );
}

int main() {
  print(std::make_tuple(10, 0.66, 'h'));
  return 0;
}

Note that the template arguments can be deduced automatically (typing all of that out would be a pain wouldn't it?).

Now, the tuple_zip function:

As before, start with the helper function:

template <template <typename ...> class Tup1,
    template <typename ...> class Tup2,
    typename ...A, typename ...B,
    std::size_t ...S>
auto tuple_zip_helper(Tup1<A...> t1, Tup2<B...> t2, seq<S...> s) ->
decltype(std::make_tuple(std::make_pair(std::get<S>(t1),std::get<S>(t2))...)) {
  return std::make_tuple( std::make_pair( std::get<S>(t1), std::get<S>(t2) )...);
}

The code is a little tricky, particularly the trailing return type (the return type is declared as auto and provided with -> after the parameters are defined). This lets us avoid the problem of even defining what the return type will be, by simply declaring it returns the expression used in the function body (if x and y are ints, delctype(x+y) is resolved at compile time as int).

Now wrap it in a function that provides the appropriate seq<0, 1...N> using gens<N>::type:

template <template <typename ...> class Tup1,
  template <typename ...> class Tup2,
  typename ...A, typename ...B>
auto tuple_zip(Tup1<A...> t1, Tup2<B...> t2) ->
decltype(tuple_zip_helper(t1, t2, typename gens<sizeof...(A)>::type() )) {
  static_assert(sizeof...(A) == sizeof...(B), "The tuple sizes must be the same");
  return tuple_zip_helper( t1, t2, typename gens<sizeof...(A)>::type() );
}

Now you can use it as specified in the question:

int main() {
  auto tup1 = std::make_tuple(1, 'b', -10);
  auto tup2 = std::make_tuple(2.5, 2, std::string("even strings?!"));
  std::tuple<
    std::pair<int, double>,
    std::pair<char, int>,
    std::pair<int, std::string> > x = tuple_zip( tup1, tup2 );

  // this is also equivalent:
  //  auto x = tuple_zip( tup1, tup2 );

  return 0;
}

And finally, if you provide a << operator for std::pair you can use the print function we defined above to print the zipped result:

template <typename A, typename B>
std::ostream & operator << (std::ostream & os, const std::pair<A, B> & pair) {
  os << "pair("<< pair.first << "," << pair.second << ")";
  return os;
}

int main() {
  auto tup1 = std::make_tuple(1, 'b', -10);
  auto tup2 = std::make_tuple(2.5, 2, std::string("even strings?!"));
  auto x = tuple_zip( tup1, tup2 );

  std::cout << "zipping: ";
  print(tup1);
  std::cout << "with   : ";
  print(tup2);

  std::cout << "yields : ";
  print(x);

  return 0;
}

The output is:

zipping: 1 b 10
with : 2.5 2 even strings?!
yields : pair(1,2.5) pair(b,2) pair(10,even strings?!)

Like std::array, std::tuple is defined at compile time, and so it can be used to generate more optimizable code (more information is known at compile time compared to containers like std::vector and std::list). So even though it's sometimes a bit of work, you can sometimes use it to make fast and clever code. Happy hacking!

---

Edit:

As requested, allowing tuples of different sizes and padding with null pointers:

template <typename T, std::size_t N, std::size_t ...S>
auto array_to_tuple_helper(const std::array<T, N> & arr, seq<S...> s) -> decltype(std::make_tuple(arr[S]...)) {
  return std::make_tuple(arr[S]...);
}

template <typename T, std::size_t N>
auto array_to_tuple(const std::array<T, N> & arr) -> decltype( array_to_tuple_helper(arr, typename gens<N>::type()) ) {
  return array_to_tuple_helper(arr, typename gens<N>::type());
}

template <std::size_t N, template <typename ...> class Tup, typename ...A>
auto pad(Tup<A...> tup) -> decltype(tuple_cat(tup, array_to_tuple(std::array<std::nullptr_t, N>()) )) {
  return tuple_cat(tup, array_to_tuple(std::array<std::nullptr_t, N>()) );
}

#define EXTENSION_TO_FIRST(first,second) ((first)>(second) ? (first)-(second) : 0)

template <template <typename ...> class Tup1, template <typename ...> class Tup2, typename ...A, typename ...B>
auto pad_first(Tup1<A...> t1, Tup2<B...> t2) -> decltype( pad<EXTENSION_TO_FIRST(sizeof...(B), sizeof...(A)), Tup1, A...>(t1) ) {
  return pad<EXTENSION_TO_FIRST(sizeof...(B), sizeof...(A)), Tup1, A...>(t1);
}

template <template <typename ...> class Tup1, template <typename ...> class Tup2, typename ...A, typename ...B>
auto diff_size_tuple_zip(Tup1<A...> t1, Tup2<B...> t2) ->
  decltype( tuple_zip( pad_first(t1, t2), pad_first(t2, t1) ) ) {
  return tuple_zip( pad_first(t1, t2), pad_first(t2, t1) );
}

And BTW, you're going to need this now to use our handy print function:

std::ostream & operator << (std::ostream & os, std::nullptr_t) {
  os << "null_ptr";
  return os;
}

Barrada

Nice overall solution. I'll only have a couple of remarks. 1/ I would use unsigned as indexes (at the very least), because you don't expect negatives indexes, do you ? 2/ A static_assert instead of the assert would be welcome. 3/ The pair should probably be taken by const& in the operator<< overload. – Kokanee

Generalizing tuple_zip to operate on an arbitrary number of tuples left as an exercise to the reader ? :) – Assailant

For the unequal ones, I think I'd use decltype(std::ignore) instead of std::nullptr_t, because I think it plays nicer: it allows distinction from an actual tuple with std::nullptr_t, and still works ok with tuples of references. Also, it's a pity that the standard tuple_cat is not required to work with arrays (even when std::get overloads exist for them) forcing extra copies :( I had to resort to implementing my own tuple_cat. – Prather

@R.MartinhoFernandes Fingers crossed the compiler takes them out with copy propagation... – Barrada

Your print_helper cannot print zero-size tuples (zero-size automatic arrays are not allowed). – Newmown

Answer 2

It isn't extremely difficult to do this for an arbitrary amount of tuples.

One way is to make a function that collects all elements at a specific index from N tuples into a new tuple. Then have another function which collects those tuples into a new tuple for each index in the original tuples.

All of that can be done relatively simply by expanding expressions with parameter packs, without any recursive functions.

#include <cstddef>
#include <tuple>

namespace detail {
    // Describe the type of a tuple with element I from each input tuple.
    // Needed to preserve the exact types from the input tuples.
    template<std::size_t I, typename... Tuples>
    using zip_tuple_at_index_t = std::tuple<std::tuple_element_t<I, std::decay_t<Tuples>>...>;

    // Collect all elements at index I from all input tuples as a new tuple.
    template<std::size_t I, typename... Tuples>
    zip_tuple_at_index_t<I, Tuples...> zip_tuple_at_index(Tuples && ...tuples) {
        return {std::get<I>(std::forward<Tuples>(tuples))...};
    }

    // Create a tuple with the result of zip_tuple_at_index for each index.
    // The explicit return type prevents flattening into a single tuple
    // when sizeof...(Tuples) == 1 or sizeof...(I) == 1 .
    template<typename... Tuples, std::size_t... I>
    std::tuple<zip_tuple_at_index_t<I, Tuples...>...> tuple_zip_impl(Tuples && ...tuples, std::index_sequence<I...>) {
        return {zip_tuple_at_index<I>(std::forward<Tuples>(tuples)...)...};
    }

}

// Zip a number of tuples together into a tuple of tuples.
// Take the first tuple separately so we can easily get its size.
template<typename Head, typename... Tail>
auto tuple_zip(Head && head, Tail && ...tail) {
    constexpr std::size_t size = std::tuple_size_v<std::decay_t<Head>>;

    static_assert(
        ((std::tuple_size_v<std::decay_t<Tail>> == size) && ...),
        "Tuple size mismatch, can not zip."
    );

    return detail::tuple_zip_impl<Head, Tail...>(
        std::forward<Head>(head),
        std::forward<Tail>(tail)...,
        std::make_index_sequence<size>()
    );
}

See it in action here: https://wandbox.org/permlink/EQhvLPyRfDrtjDMw

I used some C++14/17 features, but nothing essential. The most difficult part to replace would be the fold expression for checking the tuple sizes. That would probably have to become a recursive check.

Akihito