让我考虑下列合成例子：
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) {
// ?
}
保证
> fun2可以嵌入乐趣
>搜索复杂度不逊于O(log(i))(对于大i).
众所周知,当足够大的开关扩展时,优化器通常使用查找跳转表或编译时二叉搜索树.所以,我想保持这个属性影响大量项目的性能.
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
解决方法
好的,我重写了我的答案.这给了什么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,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,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,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>,&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,2) << std::endl;
}
{
tup t{15,2) << std::endl;
}
{
tup t{20,2) << std::endl;
}
}
住在Coliru：
http://coliru.stacked-crooked.com/a/3cfbd4d9ebd3bb3a
