Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

C++ zip variadic templates

Here is a simple two-container zip function in C++:

template <typename A, typename B>
std::list<std::pair<A, B> > simple_zip(const std::list<A> & lhs,
                                       const std::list<B> & rhs)
{
  std::list<std::pair<A, B> >  result;
  for (std::pair<typename std::list<A>::const_iterator,
                 typename std::list<B>::const_iterator> iter
       =
       std::pair<typename std::list<A>::const_iterator,
                 typename std::list<B>::const_iterator>(lhs.cbegin(),
                                                        rhs.cbegin());
       iter.first != lhs.end() && iter.second != rhs.end();
       ++iter.first, ++iter.second)
  {
    result.push_back( std::pair<A, B>(*iter.first, *iter.second) );
  }
  return result;
}

How would I extend this to an arbitrary number of containers with variadic templates?

I'd like general_zip to accept a tuple of lists (each list can contain a different type) and return a list of tuples.

like image 215
user Avatar asked May 02 '12 19:05

user


2 Answers

It seems like this should work

std::list<std::tuple<>> simple_zip() {
  return {};
}

template <typename ...T>
std::list<std::tuple<T...>> simple_zip(std::list<T>... lst)
{
  std::list<std::tuple<T...>>  result;
  for (int i = 0, e = std::min({lst.size()...}); i != e; i++) {
    result.emplace_back(std::move(lst.front())...);
    [](...){} ((lst.pop_front(), 0)...);
  }
  return result;
}

@Potatoswatter had the good (IMO) remark that this may copy more than needed when the lists are of different size, and that using only iterators will be better since pop_front does more than actually needed. I think the following "fixes" the iterator one at the cost of more code.

template <typename ...T>
std::list<std::tuple<T...>> simple_zip(std::list<T>... lst)
{
  std::list<std::tuple<T...>>  result;
  struct {
    void operator()(std::list<std::tuple<T...>> &t, int c,
             typename std::list<T>::iterator ...it) {
      if(c == 0) return;
      t.emplace_back(std::move(*it++)...);
      (*this)(t, c-1, it...);
    }
  } zip;
  zip(result, std::min({lst.size()...}), lst.begin()...);
  return result;
}

std::list<std::tuple<>> simple_zip() {
  return {};
}
like image 195
Johannes Schaub - litb Avatar answered Oct 30 '22 16:10

Johannes Schaub - litb


This is an incremental improvement on Johannes' first answer. It avoids the dummy struct and avoids copying the entire input lists (although this doesn't matter much unless one list is shorter than the others). Also I made it generic over all containers.

But it requires a boilerplate pack-index generator, which is quite useful anyway

template< std::size_t n, typename ... acc >
struct make_index_tuple {
    typedef typename make_index_tuple<
        n - 1,
        std::integral_constant< std::size_t, n - 1 >, acc ...
    >::type type;
};

template< typename ... acc >
struct make_index_tuple< 0, acc ... >
    { typedef std::tuple< acc ... > type; };

The "real" implementation consists of a straightforward function which requires the output from the above utility, and an interface function which maps packs to tuples.

template< typename ret_t, std::size_t ... indexes, typename lst_tuple >
ret_t simple_zip( std::tuple< std::integral_constant< std::size_t, indexes > ... >,
    lst_tuple const &lst ) {
    ret_t ret;

    auto iters = std::make_tuple( std::get< indexes >( lst ).begin() ... );
    auto ends = std::make_tuple( std::get< indexes >( lst ).end() ... );

    while ( std::max< bool >({ std::get< indexes >( iters )
                            == std::get< indexes >( ends ) ... }) == false ) {
        ret.emplace_back( * std::get< indexes >( iters ) ++ ... );
    }
    return ret;
}

template< typename ... T >
std::list< std::tuple< typename T::value_type ... > >
simple_zip( T const & ... lst ) {
    return simple_zip
        < std::list< std::tuple< typename T::value_type ... > > > (
        typename make_index_tuple< sizeof ... lst >::type(),
        std::tie( lst ... )
    );
}

At the least, this puts into perspective what Johannes made look easy. This is what most variadic template algorithms look like, because there is no way to store type-variadic state without tuple, and there is no way to process a variadic tuple without a pack of indexes or a meta-recursive function. (Edit: ah, now Johannes used a tail-recursive local function to define local packs to do all that with no tuple at all. Awesome… if you can handle all the functional programming ;v) .)

like image 22
Potatoswatter Avatar answered Oct 30 '22 16:10

Potatoswatter