Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?!"));
like image 619
user Avatar asked Jul 04 '12 03:07

user


2 Answers

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;
}
like image 156
user Avatar answered Oct 21 '22 22:10

user


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.

like image 43
Maarten Avatar answered Oct 21 '22 22:10

Maarten