Возможно ли реализовать нерекурсивную реализацию 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)...)) 

Он использует простой факт, что данный тип в VARIADIC X... компилятор может нерекурсивно создать другой тип T целых X s там.

Итак, я хочу знать, есть ли способ расширить его для реализации функции at_c или nth с постоянным количеством экземпляров шаблонов (независимо от количества элементов).

Он также может быть сформулирован, как, дают VARIADIC тип X... и некоторое целое число N, можно ли нерекурсивно генерировать подпоследовательность X..., состоящую из элементов N?

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

Основная идея заключается в том, для любого 'я' и 0,1,2, ... n- 1 (где n> i) (0^i), (1^i), ... (j^i) ..., ((n-1)^i) - единственная последовательность, и только значение позиция в точке «i» равна нулю.

Это решение не O (1), решение O (log (n)). Но он основан на C++ 14 make_index_sequence. Компилятор Iff компилирует make_index_sequence в O (1), поэтому мое решение также стало 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; 
}