std::tuple_element need deep template instantinati

问题:

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

回答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.

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

回答3:

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

   // GCC couldn't optimize sizeof..(i) , 
   //see http://stackoverflow.com/questions/19783205/why-sizeof-t-so-slow-implement-c14-make-index-sequence-without-sizeof
   //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;
};