std::tuple_element need deep template instantination

Question

in here http://en.cppreference.com/w/cpp/utility/tuple/tuple_element given possible implementation of std::tuple_element.

 template< std::size_t I, class T >
struct tuple_element;

// recursive case
template< std::size_t I, class Head, class... Tail >
struct tuple_element<I, std::tuple<Head, Tail...>>
    : std::tuple_element<I-1, std::tuple<Tail...>> { };

// base case
template< class Head, class... Tail >
struct tuple_element<0, std::tuple<Head, Tail...>> {
   typedef Head type;
};

But, this implementation need deep recursion instantiation, if tuple has a lot parameters ( more that 100 or 200 parameters).

Q1: Why C++11 was not added special operator for getting elements by index? like tuple[2] or tuple[0] ?

Q2: Is possible reduce the deep instantiation? For example in D language more template algorithms (in typetuple) needed O(log(N) ) deep instantiation.

EDIT: Q1: Why C++11 was not added special operator for getting elements by index from variadic templates? like template< class ...T> struct index{ typedef T[3] third_element;}

Guth

"more that 100 or 200 parameters" I'm fairly sure no compiler supports tuples with that many parameters anyway. – Travancore

@NicolBolas My g++4.8.1 compiles a 300-element tuple created via the indices trick; clang++3.2.1 segfaults somewhere between 150 and 200 arguments (might also be the indices trick, who knows). Had to raise template instantiation depth for both, though. – Koloski

@DyP: Fair enough. Though as you point out, it's not exactly the default case. – Travancore

Huh, I was sure there was a proposal for random access into parameter packs, but I can't find it. Which answers the question why it isn't there: because nobody proposed it. – Renayrenckens

@SebastianRedl: There was discussion about it on the mailing list, but there's no effective way to use such a feature without having some kind of compile-time "static for" construct. Even constexpr won't work, since pack[0] can have a different type from pack[1]. Whatever you use as an index must be a constant expression. And there is no way to loop over some number of things with an index that is a constant expression. – Travancore

@NicolBolas At the very least, it should enable a constant-time implementation of tuple_element, and a get that, while still technically linear in that the compiler has to run a linear overload algorithm, at least has a constant number of template instantiations. – Renayrenckens

Answer 1

Why C++11 was not added special operator for getting elements by index? like tuple2 or tuple[0] ?

First, because even if they did, it'd still work the same way: with recursion. Tuples are primarily a library feature. Though they piggy-back off of language features like variadic templates, they were more or less functional in C++98/03.

Second, that would not be possible. Not without a very difficult language change.

It's not clear what you mean by tuple[2].

If you mean that std::tuple<int, float, std::string>[2] should somehow resolve to the typename std::string, then that means you now need to explain why this works. Again, tuples are a library feature, not a language construct. So there would have to be some language construct whereby typename[integer] is a valid construct. What would that be and what would it mean?

If you mean that given:

std::tuple<int, float, std::string> tpl{...};

We should be able to get the string with tpl[2], that's several shades of "not going to happen". C++ is a statically typed language. The only reason std::get is able to get away with what it does is that the integer index is not a function parameter; it is a template parameter. That is what allows std::get<0> to return a completely different type from std::get<2>. That can't happen with operator[](int); that function must always return the same type.

So now you'd need to have something like template<class T, int i> ... operator[](). And that would be very confusing, because you can no longer do tpl[runtimeValue] on that type (since template parameters must be compile-time values). There is no such type where operator[] is restricted from being able to work on runtime values. So you'd be creating a very oddball type.

And even then... it would still have to do recursion to get the value.

Is possible reduce the deep instantiation?

Outside of compile times (which is not an unreasonable issue), what does it matter? A decent inliner will throw most of them away.

As for compile times, there are non-recursive implementations of various features of std::tuple. Whether they can do tuple_element non-recursively, I don't think so. This libc++ implementation seems to suggest that it can't, despite implementing the tuple itself non-recursively.

Travancore

Answer 2

I think this implementation has O(log(N)) instantiation depth; kudos to Xeo for the O(log(N)) indices trick (modified to use std::size_t instead of unsigned).

Edit: I realized there's a different, simpler and probably faster (compilation time) solution to get the nth type of a tuple.

// from https://stackoverflow.com/a/13073076
// indices trick in O(log(N)) instantiations, by Xeo

    // using aliases for cleaner syntax
    template<class T> using Invoke = typename T::type;

    template<std::size_t...> struct seq{ using type = seq; };

    template<class S1, class S2> struct concat;

    template<std::size_t... I1, std::size_t... I2>
    struct concat<seq<I1...>, seq<I2...>>
      : seq<I1..., (sizeof...(I1)+I2)...>{};

    template<class S1, class S2>
    using Concat = Invoke<concat<S1, S2>>;

    template<std::size_t N> struct gen_seq;
    template<std::size_t N> using GenSeq = Invoke<gen_seq<N>>;

    template<std::size_t N>
    struct gen_seq : Concat<GenSeq<N/2>, GenSeq<N - N/2>>{};

    template<> struct gen_seq<0> : seq<>{};
    template<> struct gen_seq<1> : seq<0>{};

Implementation of / similar to std::tuple_element:

namespace detail
{
    template<std::size_t>
    struct Any
    {
        Any(...) {}
    };

    template<typename T>
    struct wrapper { using type = T; };

    template<std::size_t... Is>
    struct get_nth_helper
    {
        template<typename T>
        static auto deduce(Any<Is>..., wrapper<T>, ...) -> wrapper<T>;
    };

    template<std::size_t... Is, typename... Ts>
    auto deduce_seq(seq<Is...>, wrapper<Ts>... pp)
    -> decltype( get_nth_helper<Is...>::deduce(pp...) );
}

#include <tuple>

template<std::size_t n, class Tuple>
struct tuple_element;

template<std::size_t n, class... Ts>
struct tuple_element<n, std::tuple<Ts...>>
{
    using wrapped_type = decltype( detail::deduce_seq(gen_seq<n>{},
                                                      detail::wrapper<Ts>()...) );
    using type = typename wrapped_type::type;
};

Usage example:

#include <typeinfo>
#include <iostream>

int main()
{
    std::tuple<int, double, bool, char> t;
    tuple_element<1, decltype(t)>::type x;
    std::cout << typeid(x).name() << std::endl;
}

Thanks to @Barry for pointing out an issue in an earlier version of this answer with function/array types, and providing a fix.

---

Original version: (Note: This version is simplified and doesn't add cv-qualifiers.)

#include <tuple>


namespace detail
{
    template < std::size_t Index, class Arg >
    struct s_get_one
    {
        // declare a function that links an Index with an Arg type
        friend Arg get(s_get_one, std::integral_constant<std::size_t, Index>);
    };

    template < typename... Bases >
    struct s_get : Bases... {};
}

template < std::size_t I, class T >
struct tuple_element;

template < std::size_t I, class... Args >
struct tuple_element < I, std::tuple<Args...> >
{
    template<class T>
    struct wrapper { using type = T; };

    // deduce indices from seq helper
    template < std::size_t... Is >
    static auto helper(seq<Is...>)
        -> detail::s_get< detail::s_get_one<Is, wrapper<Args>>... >;

    // generate indices in O(log(N)) and use name lookup to find the type
    using IC = std::integral_constant<std::size_t, I>;
    using wrapped_type = decltype( get(helper(gen_seq<sizeof...(Args)>{}), IC{}) );
    using type = typename wrapped_type::type;
};

Koloski

@KhurshidNormuradov Try the new version, it might need less resources. – Koloski

+1, but this won't work if the tuple contains an array or function type. get_nth_helper::deduce should return wrapper<T> instead, then tuple_element can pull out the T. – Inhaul

@Inhaul Fixed in both versions, thanks. What do you think about Kurshid's approach below? – Koloski

@Koloski Clever! I would've made the same comment as you (i.e. make it base<id<(j==i), T>...>). I wonder how that compares to the multiple inheritance approach from here (search for _at_index) – Inhaul

@Inhaul See ldionne.com/2015/11/29/efficient-parameter-pack-indexing My first version is, I think, similar to ldionne's void* implementation, though I'd guess that ldionne's implementation is more lightweight. – Koloski

Answer 3

    template< int ...i> struct seq{};

   // GCC couldn't optimize sizeof..(i) , 
   //see https://mcmap.net/q/17783/-why-sizeof-t-so-slow-implement-c-14-make_index_sequence-without-sizeof-t
   //so I use direct variable `s` instead of it.
   // i.e.  s == number of variadic arguments in `I`.
    template< int s, typename I, typename J > struct concate;

    template< int s, int ...i, int ...j>
    struct concate<s, seq<i...>, seq<j...> >
    { 
        typedef seq<i..., (s  + j)...> type;
    };

    template<int n> struct make_seq_impl;
    template< int n> using make_seq = typename make_seq_impl<n>::type;

    template<> struct make_seq_impl<0>{ typedef seq<> type;};
    template<> struct make_seq_impl<1>{ typedef seq<0> type;};

    template<int n> struct make_seq_impl: concate< n/2, make_seq<n/2>, make_seq<n-n/2>>{};

    template< typename ...T> using seq_for = make_seq< sizeof...(T) > ;

//----------------------------------
template< int i, typename T> struct id{};
template< typename T> struct id<0,T>{ typedef T type;};
template< typename ...T> struct base : T ... {};

template< typename ...T> struct tuple{};

template< std::size_t i, typename Tuple> struct tuple_element;

template< std::size_t i, typename ...T>
struct tuple_element< i, tuple<T...> >
{
      template< typename Seq > struct apply;
      template< int ...j > struct apply< seq<j...> >
      {
         // j xor i ==> ( 0 xor i), (1 xor i), (2 xor i ),...(i xor i) ...
         //    =>  i0, i1, ..., 0 (at pos i) ...
         // and only id<0,T> has `type`.
          typedef base< id< (j xor i), T> ... > base_t;
          typedef typename base_t::type type;
       };

     typedef typename apply< seq_for<T...> >::type type;
};

Worn

I think you could as well use template<bool b, typename> struct id{};, specialize on b == true, and then replace the xor with a j == i. By the way: Really nice solution! – Koloski

Thanks, for improving the solution. Really, If I use bool instead of int - it will more nice solution. – Worn