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;
    }
};

}

score 16 · Answer 1 · answered Jun 04 '14 at 19:57

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.

Edward Strange · Answer 2 · 2012-05-16T22:29:37.917

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; }

Jonathan Wakely · Answer 3 · 2015-09-14T12:49:15.407

4

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...>()); }

edited Sep 14 '15 at 12:49

answered May 16 '12 at 23:03

Jonathan Wakely

166,810
27
341
521

2

You can match the indices pack with `redi::index_tuple<0, I...>` and `I` will start from index `1` on, i.e. just those indices we care about. – Luc Danton May 17 '12 at 00:07
You're still using recursion it's just in the index_tuple.h utilities you're using. – Edward Strange May 17 '12 at 00:26
@Luc Danton, good idea, but you need other changes too or the parameter pack I will not be the same size as U – Jonathan Wakely May 17 '12 at 01:13
2

@Crazy Eddie, yes, but that's a util you write once (or copy) and re-use instead of having to re-implement a recursive solultion every time you do anything with tuples. – Jonathan Wakely May 17 '12 at 01:13
A type based on `index_tuple` will be in C++14 :) – Jonathan Wakely Apr 21 '13 at 20:24

score 3 · Answer 4 · answered May 16 '12 at 22:48

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.

shouldn't it be `return _hash< sizeof...(Tail) - 1, Head, Tail... >()( e );`? std::get in the first depth of recursion will fail otherwise. — Tamás Szelei, May 17 '12 at 08:48
I don't think so. The size of the tail is one less than the number of elements in the tuple, so sizeof...(Tail) should be the index of the last element in the tail. In other words, indexes in the range [0, sizeof...(Tail)] should be valid here. — Chris Hayden, May 18 '12 at 00:03

Kerrek SB · Answer 5 · 2012-05-17T05:28:41.837

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>

My test: `int main() { std::tuple t1(42,'e',16.7); std::tuple t2 = tail(t1); std::cout << std::get<0>(t2) << std::endl; }` fails to compile: `error: cannot call member function 'std::tuple tail_impl, N ...>::go(const std::tuple&) [with T = int, Args = {char, double}, unsigned int ...N = {0u}]' without object` — Edward Strange, May 16 '12 at 22:02

score -1 · Answer 6 · edited May 23 '17 at 12:02

Using kgadek's answer to get part of std::tuple , and Andre Bergner's test code. This is nice and simple but I don't know whether it's portable.

// works using gcc 4.6.3
// g++ -std=c++0x -W -Wall -g main.cc -o main
#include <iostream>
#include <tuple>

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

template <typename T, typename... Ts>
const std::tuple<Ts...>& tail(const std::tuple<T, Ts...>& t)
{
   return (const std::tuple<Ts...>&)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;
}

It is UB as `std::tuple` and `std::tuple` are unrelated types (even if indeed some old implementations used inheritance, but that an implementation detail, so no portable). — Jarod42, Nov 27 '18 at 16:06

How to split a tuple?

6 Answers6

Linked