Có thể triển khai at_c không đệ quy không?

Question

Thời gian dài trở lại tôi đã thấy một triển khai không đệ quy để lấy giá trị/loại cuối cùng từ chuỗi thứ tự/giá trị kiểu. Nó có một thuộc tính tốt đẹp, rằng số lượng khuôn mẫu được khởi tạo là độc lập (và không đổi) của số phần tử mà trình tự chứa.

Việc thực hiện rất đơn giản, như sau

// 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)...)) 

Nó sử dụng một thực tế đơn giản mà đưa ra một loại variadic X... trình biên dịch không đệ quy có thể tạo ra một loại T càng nhiều càng X s ở đó. Vì vậy, tôi muốn biết là có một cách để mở rộng nó để thực hiện at_c hoặc nth chức năng với số lượng không đổi của các mẫu instantiated (độc lập với số lượng các phần tử).

Nó cũng có thể được phrased như, cung cấp cho một loại variadic X... và một số nguyên N, là nó có thể không đệ quy tạo ra một tiểu chuỗi X... gồm N yếu tố?

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

Giải pháp của tôi :)) biên soạn với gcc 4.6.4 -std = C++ 0x

ý tưởng chính là, đối với bất kỳ 'i' và 0,1,2, ... n 1 (trong đó n> i) (0^i), (1^i), ... (j^i) ..., ((n-1)^i) - là chuỗi duy nhất và chỉ có giá trị vị trí tại 'i' là số không.

Nó không phải là giải pháp O (1), O (log (n)). Nhưng nó dựa trên C++ 14 make_index_sequence. Trình biên dịch Iff biên dịch make_index_sequence tại O (1), vì vậy giải pháp của tôi cũng trở thành 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; 
}