Switch语句可变参数模板扩展 [英] Switch statement variadic template expansion
问题描述
让我考虑以下综合示例：
Let me please consider the following synthetic example:
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));
}
}
问题是我应该如何将其扩展到一般case
The question is how should I expand this to the general case
template<class... Args> int fun(const std::tuple<Args...>& t, std::size_t i) {
// ?
}
保证这一点
- fun2可以内嵌到乐趣中
- 搜索复杂度不比O（log（i））（对于大i）差。
众所周知，优化器通常会在扩展足够大的开关时使用查找跳转表或编译时二进制搜索树。因此，我想保持该属性影响大量项目的性能。
It is known that optimizer usually uses lookup jump table or compile-time binary search tree when large enough switch expanded. So, I would like to keep this property affecting performance for large number of items.
更新＃3：我用统一的随机索引重新测量了性能值：
Update #3: I remeasured performance with uniform random index value:
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：似乎clang可以内联@TartanLlama解决方案中的函数，而gcc总是生成函数调用。
Update #2: It seems that clang is able to inline functions in @TartanLlama solution whereas gcc always generates function call.
推荐答案
好，我重写了答案。这为TartanLlama以及我之前建议的方法提供了不同的方法。满足您的复杂性要求，并且不使用函数指针，因此所有内容都是可内联的。
Ok, I rewrote my answer. This gives a different approach to what TartanLlama and also what I suggested before. This meets your complexity requirement and doesn't use function pointers so everything is inlineable.
编辑：非常感谢Yakk指出了相当重要的优化（对于注释中需要的编译时模板递归深度）
基本上，我使用模板制作类型/函数处理程序的二进制树，并实现二进制搜索
Basically I make a binary tree of the types / function handlers using templates, and implement the binary search manually.
使用mpl或boost :: fusion可能更干净地执行此操作，但是该实现还是自包含的。
It might be possible to do this more cleanly using either mpl or boost::fusion, but this implementation is self-contained anyways.
它绝对满足您的要求，该函数是可内联的，并且运行时查找的元组中的类型数目为O（log n）。
It definitely meets your requirements, that the functions are inlineable and runtime look up is O(log n) in the number of types in the tuple.
这是完整的清单：
#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
Live on Coliru: http://coliru.stacked-crooked.com/a/3cfbd4d9ebd3bb3a
这篇关于Switch语句可变参数模板扩展的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
