c++ - 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 可以内嵌到 fun 中
2. 搜索复杂度不低于 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:似乎 clang 能够在@TartanLlama 解决方案中内联函数，而 gcc 总是生成函数调用。

Answer 1

好的，我重写了我的答案。这为 TartanLlama 以及我之前的建议提供了不同的方法。这满足了您的复杂性要求，并且不使用函数指针，因此一切都是可内联的。

编辑:非常感谢 Yakk 在评论中指出了一个相当重要的优化(对于所需的编译时模板递归深度)

基本上，我使用模板制作类型/函数处理程序的二叉树，并手动实现二分搜索。

使用 mpl 或 boost::fusion 可能更干净地完成此操作，但无论如何此实现都是独立的。

它绝对满足您的要求，函数是可内联的，并且运行时查找在元组中的类型数量是 O(log n)。

这是完整的 list :

#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