How to split a tuple?

Question

Given a

   template<typename First, typename... Tail>
   struct something
   {
       std::tuple<First, Tail...> t;
   };

How can I get a std::tuple<Tail...> that contains all elements from t except for the first one?

---

I think this is an interesting question in general, but here is my motivation for context:

I'd like to implement a hash for tuples. I used this answer as a basis. I found that there was an error in it, namely not calling operator() of the hash object with a value:

return left() ^ right();

Should be:

return left(std::get<0>(e)) ^ right(???);

The ??? would be the remaining elements of the tuple to continue the recursive instantiation of the template. Here is the complete code including the termination part:

#include <functional>
#include <utility>

namespace std
{

template<typename First, typename... Tail>
struct hash<std::tuple<First, Tail...>>
{
    typedef size_t result_type;
    typedef std::tuple<First, Tail...> argument_type;

    result_type operator()(argument_type const& e) const
    {
        std::hash<First> left;
        std::hash<std::tuple<Tail...>> right;
        return left(std::get<0>(e)) ^ right(???);
    }
};

template<>
struct hash<std::tuple<>>
{
    typedef size_t result_type;
    typedef std::tuple<> argument_type;

    result_type operator()(argument_type const& e) const
    {
        return 1;
    }
};

}

Answer 1

I was searching for the same thing and came up with this rather straight forward C++14 solution:

#include <iostream>
#include <tuple>
#include <utility>

template < typename T , typename... Ts >
auto head( std::tuple<T,Ts...> t )
{
   return  std::get<0>(t);
}

template < std::size_t... Ns , typename... Ts >
auto tail_impl( std::index_sequence<Ns...> , std::tuple<Ts...> t )
{
   return  std::make_tuple( std::get<Ns+1u>(t)... );
}

template < typename... Ts >
auto tail( std::tuple<Ts...> t )
{
   return  tail_impl( std::make_index_sequence<sizeof...(Ts) - 1u>() , t );
}

int main()
{
   auto t = std::make_tuple( 2, 3.14 , 'c' );
   std::cout << head(t) << std::endl;
   std::cout << std::get<0>( tail(t) ) << std::endl;
   std::cout << std::get<1>( tail(t) ) << std::endl;
}

So, head(.) returns the first element of a tuple and tail(.) returns a new tuple containing only the last N-1 elements.

Answer 2

Using an "index tuple" to unpack the tuple without recursion:

#include <redi/index_tuple.h>

template<typename T, typename... U, unsigned... I>
  inline std::tuple<U...>
  cdr_impl(const std::tuple<T, U...>& t, redi::index_tuple<I...>)
  { return std::tuple<U...>{ std::get<I+1>(t)... }; }

template<typename T, typename... U>
  inline std::tuple<U...>
  cdr(const std::tuple<T, U...>& t)
  { return cdr_impl(t, redi::to_index_tuple<U...>()); }

See https://gitlab.com/redistd/redistd/blob/master/include/redi/index_tuple.h for make_index_tuple and index_tuple which are IMHO essential utilities for working with tuples and similar variadic class templates. (A similar utility was standardised as std::index_sequence in C++14, see index_seq.h for a standalone C++11 implementation).

Alternatively, a non-copying version using std::tie to get a tuple of references to the tail, instead of making copies of each element:

#include <redi/index_tuple.h>

template<typename T, typename... U, unsigned... I>
  inline std::tuple<const U&...>
  cdr_impl(const std::tuple<T, U...>& t, redi::index_tuple<I...>)
  { return std::tie( std::get<I+1>(t)... ); }

template<typename T, typename... U>
  inline std::tuple<const U&...>
  cdr(const std::tuple<T, U...>& t)
  { return cdr_impl(t, redi::to_index_tuple<U...>()); }

Answer 3

This is what I could hammer out first try. Probable something better:

#include <tuple>

template < typename Target, typename Tuple, int N, bool end >
struct builder
{
    template < typename ... Args >
    static Target create(Tuple const& t, Args && ... args)
    {
        return builder<Target,Tuple, N+1, std::tuple_size<Tuple>::value == N+1>::create(t, std::forward<Args>(args)..., std::get<N>(t));
    }
};

template < typename Target, typename Tuple, int N >
struct builder<Target,Tuple,N,true>
{
    template < typename ... Args >
    static Target create(Tuple const& t, Args && ... args) { return Target(std::forward<Args>(args)...); }
};

template < typename Head, typename ... Tail >
std::tuple<Tail...> cdr(std::tuple<Head,Tail...> const& tpl)
{
    return builder<std::tuple<Tail...>, std::tuple<Head,Tail...>, 1, std::tuple_size<std::tuple<Head,Tail...>>::value == 1>::create(tpl);
}

#include <iostream>
int main() {
    std::tuple<int,char,double> t1(42,'e',16.7);
    std::tuple<char,double> t2 = cdr(t1);

    std::cout << std::get<0>(t2) << std::endl;
}

One thing of note is that if you used your own type instead of std::tuple you'd probably be much better off. The reason this is so hard is that it seems the standard doesn't specify how this tuple works in that it's not given that it inherits from itself. The boost version uses a cons thingy that you can dig through. Here's something that might be more in line with what you want that would make doing all of the above as simple as a cast:

template < typename ... Args > struct my_tuple;

template < typename Head, typename ... Tail >
struct my_tuple<Head,Tail...> : my_tuple<Tail...>
{
    Head val;
    template < typename T, typename ... Args >
    my_tuple(T && t, Args && ... args) 
        : my_tuple<Tail...>(std::forward<Args>(args)...)
        , val(std::forward<T>(t)) 
    {}
};

template < >
struct my_tuple <>
{
};

That's untested, but it should illustrate the point enough to play with until it works. Now to get an object of type "tail" you simply do:

template < typename Head, typename ... Tail >
my_tuple<Tail...> cdr(my_tuple<Head,Tail...> const& mtpl) { return mtpl; }

Answer 4

Crazy Eddie found a way to unpack the tuple, which does answer the question. However, for the specific question that you asked (i.e. tuple hashing), why not avoid all of the tuple copies and instead use template recursion to hash each element in turn?

#include <utility>
#include <iostream>

template< typename T >
size_t left( T const & ) {
  return 1;
}

template< int N, typename Head, typename... Tail >
struct _hash {
  typedef size_t result_type;
  typedef std::tuple< Head, Tail... > argument_type;

  result_type operator ()( argument_type const &e ) const {
    return left(std::get<N>(e)) ^ _hash<N-1, Head, Tail... >()(e);
  }
}; // end struct _hash

template< typename Head, typename... Tail >
struct _hash< 0, Head, Tail... > {
  typedef size_t result_type;
  typedef std::tuple< Head, Tail... > argument_type;

  result_type operator ()( argument_type const &e ) const {
    return left(std::get<0>(e));
  }
}; // end struct _hash< 0 >

template< typename Head, typename... Tail >
size_t hash( std::tuple< Head, Tail... > const &e ) {
  return _hash< sizeof...(Tail), Head, Tail... >()( e );
}

int main( ) {
  std::tuple< int > l_tuple( 5 );
  std::cout << hash( l_tuple ) << std::endl;
}

This does the hashing in reverse order, but xors are commutative so it doesn't matter.

Answer 5

Something like this:

#include <tuple>

template <bool, typename T, unsigned int ...N> struct tail_impl;

template <typename T, typename ...Args, unsigned int ...N>
struct tail_impl<false, std::tuple<T, Args...>, N...>
{
    static std::tuple<Args...> go(std::tuple<T, Args...> const & x)
    {
        return tail_impl<sizeof...(N) + 1 == sizeof...(Args), std::tuple<T, Args...>, N..., sizeof...(N)>::go(x);
    }
};

template <typename T, typename ...Args, unsigned int ...N>
struct tail_impl<true, std::tuple<T, Args...>, N...>
{
    static std::tuple<Args...> go(std::tuple<T, Args...> const & x)
    {
        return std::tuple<Args...>(std::get<N>(x)...);
    }
};

template <typename T, typename ...Args>
std::tuple<Args...> tail(std::tuple<T, Args...> const & x)
{
    return tail_impl<sizeof...(Args) == 1, std::tuple<T, Args...>, 0>::go(x);
}

Test:

#include <demangle.hpp>
#include <iostream>

typedef std::tuple<int, char, bool> TType;

int main()
{
    std::cout << demangle<TType>() << std::endl;
    std::cout << demangle<decltype(tail(std::declval<TType>()))>() << std::endl;
}

Prints:

std::tuple<int, char, bool>
std::tuple<char, bool>