非再帰的なat_c実装が可能ですか？

Question

長い時間をかけて、タイプシーケンス/値シーケンスから最後の値/タイプを取得するために非再帰的な実装が見られました。インスタンス化されたテンプレートの数は、シーケンスに含まれる要素数の独立した（および一定の）数です。

// a struct that eats anything and everything 
struct eat { template<class T> eat(T&&) {} }; 
// generates V matching with U 
template<class U, class V> struct match { using type = V; }; 
template<class... X> struct back_ 
{ 
    template<class U> 
    static U&& get(typename match<X, eat>::type..., U&& u) 
    { 
     return static_cast<U&&>(u); // forward 
    } 
}; 
// simple macro to avoid repetition for trailing return type. 
#define RETURNS(exp) -> decltype(exp) { return exp; } 
// get the last value in meta O(1) 
template<class T, class... Ts> 
auto back(T&& t, Ts&&... ts) RETURNS(back_<Ts...>::get(static_cast<T&&>(t), static_cast<Ts&&>(ts)...)) 

それは可変引数タイプX...非再帰的Tなど、多くのXとしてsが存在し、別のタイプを生成できるコンパイラを与えられたという単純な事実を使用していますが、次のように

実装は、簡単です。

at_cまたはnthをインスタンス化された一定数のテンプレート（要素の数に関係なく）で実装する方法があることを知りたいと思います。

はまた、と言うこともできる

は、可変長型X...、いくつかの整数Nを与え、それは非再帰的N元素からなるX...のサブシーケンスを生成することができますか？

Answer 1

std::cout << back((int)(0), 
        (int*)(0), 
        (int**)(0), 
        (int***)(0), 
        (int****)(0), 
        (int*****)(0), 
        (int******)(0), 
        (int*******)(0), 
        1) << std::endl; 

====================================================== 
nm -C que | fgrep eat 
080489e2 W eat::eat<int*******>(int*******&&) 
080489dc W eat::eat<int******>(int******&&) 
080489d6 W eat::eat<int*****>(int*****&&) 
080489d0 W eat::eat<int****>(int****&&) 
080489ca W eat::eat<int***>(int***&&) 
080489c4 W eat::eat<int**>(int**&&) 
080489be W eat::eat<int*>(int*&&) 
080489b8 W eat::eat<int>(int&&) 
080489e2 W eat::eat<int*******>(int*******&&) 
080489dc W eat::eat<int******>(int******&&) 
080489d6 W eat::eat<int*****>(int*****&&) 
080489d0 W eat::eat<int****>(int****&&) 
080489ca W eat::eat<int***>(int***&&) 
080489c4 W eat::eat<int**>(int**&&) 
080489be W eat::eat<int*>(int*&&) 
080489b8 W eat::eat<int>(int&&) 
080489e7 W int&& back_<int*, int**, int***, int****, int*****, int******, int*******, int>::get<int>(eat, eat, eat, eat, eat, eat, eat, eat, int&&) 
080489e7 W _ZN5back_IJPiPS0_PS1_PS2_PS3_PS4_PS5_iEE3getIiEEOT_3eatSB_SB_SB_SB_SB_SB_SB_SA_ 

Answer 2

私のソリューション:)）のgcc 4.6.4 -std = C++ 0xの

主なアイデアは、任意の 'I' と0,1,2、... N-ため、あるとコンパイル（（n-1）^ i） - は一意のシーケンスであり、値'i'の位置はゼロです。

O（1）溶液、O（log（n））溶液ではありません。しかし、それはC++ 14 make_index_sequenceに基づいています。 IffコンパイラはO（1）でmake_index_sequenceをコンパイルするので、私の解決法もO（1）になりました。

#include <cstddef> 
#include <iostream> 
#include <type_traits> 

namespace mpl 
{ 
    // C++14 index_sequence struct 
    template< int ... i > 
    struct index_sequence 
    { 
     typedef index_sequence type; 
     typedef int value_type; 


     static constexpr std::size_t size()noexcept{ return sizeof...(i); } 
    }; 

    namespace details 
    { 

    #if 1 
     template< int s, typename T, typename U> struct concate_c; 

     template<int s, int ...i, int ...j> 
     struct concate_c< s, index_sequence<i...>, index_sequence<j...> > 
       : index_sequence<i..., (j + s) ... > {}; 


     template< int s, typename T, typename U> struct concate : concate_c< s, typename T::type, typename U::type > {}; 

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

    #else 

    template< typename T, typename U> struct concate_c; 

     template< int ...i, int ...j> 
     struct concate_c< index_sequence<i...>, index_sequence<j...> > 
       : index_sequence<i..., (j + sizeof...(i)) ... > {};  


     template< typename T, typename U> struct concate : concate_c< typename T::type, typename U::type > {}; 

     template< int n> 
     struct make_index_sequence : concate< 
               make_index_sequence<n/2>, 
               make_index_sequence< n - n/2 > 
              >{}; 
    #endif 
     template<> struct make_index_sequence<0> : index_sequence<>{}; 

     template<> struct make_index_sequence<1> : index_sequence<0>{}; 


    } // namespace details 


    template< int n> struct make_index_sequence : details::make_index_sequence<n> {}; 

    template< typename ...Args> 
    struct make_index_sequence_for : make_index_sequence< sizeof...(Args) > {}; 



    // helper for at_c, I - index_sequence, 
    template< typename I, typename ...p > 
    struct at_ch; 

    // only zero index have `type`. 
    template< int i, typename T> struct id{}; 
    template< typename T>struct id<0,T>{ typedef T type;}; 

    // based from all parameters. 
    template< typename ...T> struct base_all : T... {}; 

    template< int ... i, typename ...p> 
    struct at_ch< index_sequence<i...>, p... > 
    { 
     struct base : base_all< id<i,p> ... > {}; 

     typedef typename base::type type; 
    }; 

// 0 1 2 3 4 5 6 7 8 9 
// 0: 0 1 2 3 4 5 6 7 8 9 
// 1: 1 0 3 2 5 4 7 6 9 8 

    template< int i, typename I> 
    struct xor_index_sequence; 

    template< int i, int ...k> 
    struct xor_index_sequence< i, index_sequence<k...> > : index_sequence< (k xor i) ... > {}; 

    template< int i, typename ...T> 
    struct at_c: at_ch< 
        typename xor_index_sequence< i, 
          typename make_index_sequence< sizeof...(T)> ::type 
        >::type, 
        T... 
        > {}; 
} 



int main() 
{ 

    typedef mpl::at_c< 2, int, double , float >::type G; 
    static_assert(std::is_same<G, float>::value ,"!"); 

    return 0; 
}