переключатель расширения оператор VARIADIC шаблон

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 exity не хуже 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, а также то, что я предложил раньше. Это соответствует вашему требованию сложности и не использует указатели на функции, чтобы все было встроено.

Edit: Большое спасибо 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), так как массив указателей только что был создан, а затем проиндексирован напрямую, что довольно хорошо. Я бы попробовал это, измерил и посмотрел, сработает ли это для вас.