क्या एक गैर रिकर्सिव 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 के रूप में देखते हैं उत्पन्न कर सकते हैं को देखते हुए का उपयोग करता है इस प्रकार है।

तो, मैं जानना चाहता हूं कि at_c या nth कार्यान्वित करने के लिए इसे बढ़ाने का कोई तरीका है तत्काल टेम्पलेट्स (तत्वों की संख्या से स्वतंत्र) के साथ फ़ंक्शन।

यह भी रूप में phrased जा सकता है, एक variadic प्रकार 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

मेरे समाधान :)) जीसीसी के साथ संकलित 4.6.4 -std = C++ 0x

मुख्य विचार है, किसी भी 'i' के लिए और 0,1,2, ... n- 1 (जहां n> i) (0^i), (1^i), ... (j^i) ..., ((n-1)^i) - अद्वितीय अनुक्रम है, और केवल मूल्य 'i' पर स्थिति शून्य है।

यह ओ (1) समाधान, ओ (लॉग (एन)) समाधान नहीं है। लेकिन यह सी ++ 14 make_index_sequence पर आधारित है। Iff संकलक O (1) पर make_index_sequence संकलित करता है, इसलिए मेरा समाधान भी ओ (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; 
}