Variadic templates and switch statement?

Question

I have the following function which can take N arguments of different types, and forwards them to N functions templated on each individual type, in this manner (example with two arguments):

template <typename T1, typename T2> bool func(int& counter, T1 x1, T2 x2) {     switch (counter) {         case 0:             if (func2<T1>(x1)) {                 counter++;                 return true;             } else {                 return false;             }         case 1:             if (func2<T2>(x2)) {                 counter++;                 return true;             } else {                 return false;             }         default:             return true;     } } 

I want to write this function with variadic templates so that it can handle any number of arguments in a type-safe way. I can see a solution using recursive functions, passing along the counter and the variadic index and comparing them for equality, but this would seem to yield far less efficient code than the switch statement above (a sequence of if-checks compared to a jump table).

Can this be done efficiently using template metaprogramming or do I need to provide overloads for each arity?

Answer 1

Here's a solution similar to max's, but it: a) clearly separates out the generic parts from the parts specific to the solution, and b) I show that clang fully optimizes it. The basic idea is to build a switch case at compile time, from a contiguous integer sequence. We do that like this:

template <class T, T ... Is, class F> auto compile_switch(T i, std::integer_sequence<T, Is...>, F f) {   using return_type = std::common_type_t<decltype(f(std::integral_constant<T, Is>{}))...>;   return_type ret;   std::initializer_list<int> ({(i == Is ? (ret = f(std::integral_constant<T, Is>{})),0 : 0)...});   return ret; } 

The idea is that integer gets passed into the lambda as an integral constant type, so its usable in compile time contexts. To use this with the current problem, all we have to do is forward the variadic pack a tuple, and apply the usual tricks with index sequence:

template <class T, std::size_t ... Is> bool func_impl(std::size_t& counter, T&& t, std::index_sequence<Is...> is) {   auto b = compile_switch(counter, is, [&] (auto i) -> bool {     return func2(std::get<i>(std::move(t)));   });   if (b) ++counter;   return b; }  template <class ... Ts> bool func(std::size_t & counter, Ts&& ... ts) {   return func_impl(counter,       std::forward_as_tuple(std::forward<Ts>(ts)...),       std::index_sequence_for<Ts...>{}); } 

We'll use this definition of func2 to look at some assembly:

template <class T> bool func2(const T& t) { std::cerr << t; return std::is_trivial<T>::value; } 

Looking here: https://godbolt.org/g/6idVPS we notice the following instructions:

auto compile_switch<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul, bool func_impl<std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>(unsigned long&, std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>&&, std::integer_sequence<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>)::{lambda(auto:1)#1}>(unsigned long, std::integer_sequence<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>, bool func_impl<std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>(unsigned long&, std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>&&, std::integer_sequence<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>)::{lambda(auto:1)#1}): # @auto compile_switch<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul, bool func_impl<std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>(unsigned long&, std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>&&, std::integer_sequence<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>)::{lambda(auto:1)#1}>(unsigned long, std::integer_sequence<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>, bool func_impl<std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>(unsigned long&, std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>&&, std::integer_sequence<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>)::{lambda(auto:1)#1})         push    r14         push    rbx         push    rax         mov     bl, 1         cmp     rdi, 5         ja      .LBB2_11         jmp     qword ptr [8*rdi + .LJTI2_0] 

Looking down for that label, we find:

.LJTI2_0:         .quad   .LBB2_2         .quad   .LBB2_4         .quad   .LBB2_5         .quad   .LBB2_6         .quad   .LBB2_7         .quad   .LBB2_10 

In other words, clang has both turned this into a jump table, and inlined all the calls to func2. This is not possible using a table of function pointers as some have suggested (at least I've never seen a compiler do it), in fact the only way to get assembly this good is via switch case, or with this technique + clang. Sadly gcc will not generate assembly quite as good, but still decent.

Answer 2

Just for fun, I propose the following way

template <typename ... Ts> bool func (int & cnt, Ts ... xs)  {    using unused = int[];     int  i   { -1 };    bool ret { true };     (void)unused { 0, ((++i == cnt ? (ret = func<Ts>(xs)) : true), 0)... };     if ( ret && (cnt <= i) )       ++cnt;     return ret;  } 

but I don't think is a efficient way as the switch way.