switch語句可變參數模板擴展

Question

讓我請考慮以下合成例子：

inline int fun2(int x) { 
    return x; 
} 
inline int fun2(double x) { 
    return 0; 
} 
inline int fun2(float x) { 
    return -1; 
} 

int fun(const std::tuple<int,double,float>& t, std::size_t i) { 
    switch(i) { 
     case 0: return fun2(std::get<0>(t)); 
     case 1: return fun2(std::get<1>(t)); 
     case 2: return fun2(std::get<2>(t)); 
    }  
} 

的問題是我如何把這個擴大到一般情況下

template<class... Args> int fun(const std::tuple<Args...>& t, std::size_t i) { 
// ? 
} 

低保

1. fun2可以內聯成樂趣
2. search compl不超過O（log（i））（對於大i）。

已知當擴展足夠大的開關時，優化器通常使用查找跳轉表或編譯時二進制搜索樹。所以，我想保留這個屬性影響大量項目的性能。

更新＃3：我重新測量與均勻隨機索引值性能：

     1  10  20  100 
@TartanLlama 
    gcc    ~0  42.9235 44.7900 46.5233 
    clang    10.2046 38.7656 40.4316 41.7557 
@chris-beck 
    gcc    ~0  37.564 51.3653 81.552 
    clang    ~0  38.0361 51.6968 83.7704 
naive tail recursion 
    gcc    3.0798 40.6061 48.6744 118.171 
    clang    11.5907 40.6197 42.8172 137.066 
manual switch statement 
    gcc      41.7236 
    clang      7.3768 

更新＃2：似乎鐺能夠內聯函數在@TartanLlama溶液而GCC總是生成功能呼叫。

Answer 1

好的，我重寫了我的答案。這給了什麼TartanLlama和我之前建議的不同方法。這符合您的複雜性要求，並且不使用函數指針，因此所有內容都可以嵌套。

編輯：許多感謝Yakk的指出了意見相當顯著優化（所需的編譯時模板遞歸深度）

基本上我讓使用模板類型/功能處理器的二叉樹，並手動執行二進制搜索。

可能使用mpl或boost :: fusion更乾淨地做到這一點，但是這個實現是自包含的。

它絕對符合你的要求，函數是可以嵌套的，運行時查找的元組數量是O（log n）。

以下是完整列表：

#include <cassert> 
#include <cstdint> 
#include <tuple> 
#include <iostream> 

using std::size_t; 

// Basic typelist object 
template<typename... TL> 
struct TypeList{ 
    static const int size = sizeof...(TL); 
}; 

// Metafunction Concat: Concatenate two typelists 
template<typename L, typename R> 
struct Concat; 

template<typename... TL, typename... TR> 
struct Concat <TypeList<TL...>, TypeList<TR...>> { 
    typedef TypeList<TL..., TR...> type; 
}; 

template<typename L, typename R> 
using Concat_t = typename Concat<L,R>::type; 

// Metafunction First: Get first type from a typelist 
template<typename T> 
struct First; 

template<typename T, typename... TL> 
struct First <TypeList<T, TL...>> { 
    typedef T type; 
}; 

template<typename T> 
using First_t = typename First<T>::type; 


// Metafunction Split: Split a typelist at a particular index 
template<int i, typename TL> 
struct Split; 

template<int k, typename... TL> 
struct Split<k, TypeList<TL...>> { 
private: 
    typedef Split<k/2, TypeList<TL...>> FirstSplit; 
    typedef Split<k-k/2, typename FirstSplit::R> SecondSplit; 
public: 
    typedef Concat_t<typename FirstSplit::L, typename SecondSplit::L> L; 
    typedef typename SecondSplit::R R; 
}; 

template<typename T, typename... TL> 
struct Split<0, TypeList<T, TL...>> { 
    typedef TypeList<> L; 
    typedef TypeList<T, TL...> R; 
}; 

template<typename T, typename... TL> 
struct Split<1, TypeList<T, TL...>> { 
    typedef TypeList<T> L; 
    typedef TypeList<TL...> R; 
}; 

template<int k> 
struct Split<k, TypeList<>> { 
    typedef TypeList<> L; 
    typedef TypeList<> R; 
}; 


// Metafunction Subdivide: Split a typelist into two roughly equal typelists 
template<typename TL> 
struct Subdivide : Split<TL::size/2, TL> {}; 

// Metafunction MakeTree: Make a tree from a typelist 
template<typename T> 
struct MakeTree; 

/* 
template<> 
struct MakeTree<TypeList<>> { 
    typedef TypeList<> L; 
    typedef TypeList<> R; 
    static const int size = 0; 
};*/ 

template<typename T> 
struct MakeTree<TypeList<T>> { 
    typedef TypeList<> L; 
    typedef TypeList<T> R; 
    static const int size = R::size; 
}; 

template<typename T1, typename T2, typename... TL> 
struct MakeTree<TypeList<T1, T2, TL...>> { 
private: 
    typedef TypeList<T1, T2, TL...> MyList; 
    typedef Subdivide<MyList> MySubdivide; 
public: 
    typedef MakeTree<typename MySubdivide::L> L; 
    typedef MakeTree<typename MySubdivide::R> R; 
    static const int size = L::size + R::size; 
}; 

// Typehandler: What our lists will be made of 
template<typename T> 
struct type_handler_helper { 
    typedef int result_type; 
    typedef T input_type; 
    typedef result_type (*func_ptr_type)(const input_type &); 
}; 

template<typename T, typename type_handler_helper<T>::func_ptr_type me> 
struct type_handler { 
    typedef type_handler_helper<T> base; 
    typedef typename base::func_ptr_type func_ptr_type; 
    typedef typename base::result_type result_type; 
    typedef typename base::input_type input_type; 

    static constexpr func_ptr_type my_func = me; 
    static result_type apply(const input_type & t) { 
     return me(t); 
    } 
}; 

// Binary search implementation 
template <typename T, bool b = (T::L::size != 0)> 
struct apply_helper; 

template <typename T> 
struct apply_helper<T, false> { 
    template<typename V> 
    static int apply(const V & v, size_t index) { 
     assert(index == 0); 
     return First_t<typename T::R>::apply(v); 
    } 
}; 

template <typename T> 
struct apply_helper<T, true> { 
    template<typename V> 
    static int apply(const V & v, size_t index) { 
     if(index >= T::L::size) { 
      return apply_helper<typename T::R>::apply(v, index - T::L::size); 
     } else { 
      return apply_helper<typename T::L>::apply(v, index); 
     } 
    } 
}; 

// Original functions 

inline int fun2(int x) { 
    return x; 
} 
inline int fun2(double x) { 
    return 0; 
} 
inline int fun2(float x) { 
    return -1; 
} 

// Adapted functions 
typedef std::tuple<int, double, float> tup; 

inline int g0(const tup & t) { return fun2(std::get<0>(t)); } 
inline int g1(const tup & t) { return fun2(std::get<1>(t)); } 
inline int g2(const tup & t) { return fun2(std::get<2>(t)); } 

// Registry 

typedef TypeList< 
    type_handler<tup, &g0>, 
    type_handler<tup, &g1>, 
    type_handler<tup, &g2> 
> registry; 

typedef MakeTree<registry> jump_table; 

int apply(const tup & t, size_t index) { 
    return apply_helper<jump_table>::apply(t, index); 
} 

// Demo 

int main() { 
    { 
     tup t{5, 1.5, 15.5f}; 

     std::cout << apply(t, 0) << std::endl; 
     std::cout << apply(t, 1) << std::endl; 
     std::cout << apply(t, 2) << std::endl; 
    } 

    { 
     tup t{10, 1.5, 15.5f}; 

     std::cout << apply(t, 0) << std::endl; 
     std::cout << apply(t, 1) << std::endl; 
     std::cout << apply(t, 2) << std::endl; 
    } 

    { 
     tup t{15, 1.5, 15.5f}; 

     std::cout << apply(t, 0) << std::endl; 
     std::cout << apply(t, 1) << std::endl; 
     std::cout << apply(t, 2) << std::endl; 
    } 

    { 
     tup t{20, 1.5, 15.5f}; 

     std::cout << apply(t, 0) << std::endl; 
     std::cout << apply(t, 1) << std::endl; 
     std::cout << apply(t, 2) << std::endl; 
    } 
} 

住在Coliru： http://coliru.stacked-crooked.com/a/3cfbd4d9ebd3bb3a

Answer 2

如果您fun2成類重載operator()：

struct fun2 { 
    inline int operator()(int x) { 
     return x; 
    } 
    inline int operator()(double x) { 
     return 0; 
    } 
    inline int operator()(float x) { 
     return -1; 
    } 
}; 

那麼我們可以修改DYP的答案從here爲我們工作。

請注意，這在C++ 14中會看起來很整齊，因爲我們可以推導出所有返回類型並使用std::index_sequence。

//call the function with the tuple element at the given index 
template<class Ret, int N, class T, class Func> 
auto apply_one(T&& p, Func func) -> Ret 
{ 
    return func(std::get<N>(std::forward<T>(p))); 
} 

//call with runtime index 
template<class Ret, class T, class Func, int... Is> 
auto apply(T&& p, int index, Func func, seq<Is...>) -> Ret 
{ 
    using FT = Ret(T&&, Func); 
    //build up a constexpr array of function pointers to index 
    static constexpr FT* arr[] = { &apply_one<Ret, Is, T&&, Func>... }; 
    //call the function pointer at the specified index 
    return arr[index](std::forward<T>(p), func); 
} 

//tag dispatcher 
template<class Ret, class T, class Func> 
auto apply(T&& p, int index, Func func) -> Ret 
{ 
    return apply<Ret>(std::forward<T>(p), index, func, 
         gen_seq<std::tuple_size<typename std::decay<T>::type>::value>{}); 
} 

我們然後調用apply，並通過返回類型爲模板參數（你可以推斷出這一點使用decltype或C++ 14）：

auto t = std::make_tuple(1,1.0,1.0f); 
std::cout << apply<int>(t, 0, fun2{}) << std::endl; 
std::cout << apply<int>(t, 1, fun2{}) << std::endl; 
std::cout << apply<int>(t, 2, fun2{}) << std::endl; 

Live Demo

我不是確定這是否會完全滿足您的要求，因爲使用了函數指針，但編譯器可以非常積極地優化這種事情。搜索將是O(1)，因爲指針數組只是構建一次，然後直接索引，這非常好。我會嘗試一下，衡量一下，看看它是否適合你。