14

很久以前，我看到过一种非递归实现，可以从类型序列/值序列中获取最后一个值/类型。它有一个很好的属性，即实例化的模板数量与序列包含的元素数量无关（并且是恒定的）。

实现很简单，如下

// 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...，编译器可以非递归地生成与 sT一样多的另一种类型X。

所以，我想知道有没有办法扩展它来实现at_c或nth使用恒定数量的实例化模板（与元素数量无关）。

它也可以表述为，给出一个可变参数类型X...和一些整数N，是否可以非递归地生成一个由元素X...组成的子序列N？

4

2 回答 2

0 
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_
于 2013-06-13T17:00:31.657 回答
0

我的解决方案:)) 用 gcc 4.6.4 -std=c++0x 编译

主要思想是，对于任何 'i' 和 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 编译器确实在 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;
}
于 2013-11-05T08:12:03.863 回答